A new two-stage heuristic for the recreational vehicle scheduling problem. (March 2018) - Kulkarni, Sarang; Patil, Rahul; Krishnamoorthy, Mohan; Ernst, Andreas; Ranade, Abhiram
Highlights: A new mathematical formulation is proposed for solving the recreational vehicle scheduling problem. A two-stage heuristic is proposed to reduce the solution time further. The performance is evaluated using the large-sized real-life instances. The new formulation outperforms existing formulations in the literature. The two-stage heuristic outperforms the existing heuristic in the literature. Abstract: In this paper, we address the problem of vehicle scheduling in a recreational vehicle rental operation. Two mathematical formulations have been employed in the literature to model the recreational vehicle scheduling problem (RVSP): an assignment-problem-based formulation and a network-flow-based formulation. We propose a new formulation motivated by inventory planning to solve the RVSP. The inventory formulation uses the assignment arcs in a network structure, which is improved by aggregating nodes and arcs. Modifications that are based on node aggregation are also suggested to the existing assignment formulation to reduce the size of the formulation. We find that the inventory formulation outperforms the assignment formulations with and without the aggregation of nodes. We also propose a two-stage heuristic that is based on the inventory formulation and compare its performance with an existing heuristic from the literature. Computational results on real-life RVSP problem instances show that our new heuristic performs significantly better, in terms of the solution time, without compromising too much on the solution quality, for most of the instances.