Heterogeneous vehicle scheduling with precedence constraints

Abstract

The problem of heterogeneous vehicle scheduling with precedence constraints is inspired by the transportation service in tourism areas. Tourists must take the shuttle vehicles provided by the areas because of the long distances between the scenic spots. The scheduling of vehicles in tourism areas is complicated because the transportation requests of tourists are precedence-constrained temporally and spatially. The problem optimises both the cost of using vehicles and the waiting time of tourists. A mixed-integer linear programming model is formulated according to the description of a graph. An adaptive large neighbourhood search algorithm with several specialised operators is designed to solve the problem. Experiments based on randomly generated instances validate the mathematical model and the algorithm. A real-size instance based on Qiandao Lake in China is also analysed. The results indicate that the algorithm outperforms the model. The sensitivities of key parameters are analysed with managerial insights presented.

KEYWORDS:

• Transportation
• heterogeneous vehicle scheduling
• precedence constraint
• adaptive large neighbourhood search
• tourism

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China under Grants 71971050 and 71831006. This work was also supported by the National Research Foundation of Korea (NRF) grant funded by the Korean government (Ministry of Science and ICT) [Grant No. RS-2023-00218913].