A branch-and-cut algorithm for flexible vehicle scheduling problem in scenic areas

This paper studies a flexible vehicle scheduling (FVS) problem in scenic areas. The FVS problem allows a vehicle to carry multiple groups of tourists within the capacity limit and a vehicle can leave the tourists while they are visiting at a spot. This mode has great potential to improve vehicle utilization but has not been extensively studied. We formulate the FVS problem based on graph description as a mixed-integer linear programming model. To further strengthen the model, we propose two families of valid inequalities. Based on valid inequalities, a branch-and-cut algorithm is proposed to solve the FVS problem. The computational results based on randomly generated instances show the superiority of the branch-and-cut algorithm.