A new two-stage heuristic for the recreational vehicle scheduling problem

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.