An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits

作者：Liu, Ran; Tao, Yangyi; Xie, Xiaolei^*

来源：Computers & Operations Research, 2019, 101: 250-262.

DOI：10.1016/j.cor.2018.08.002

• Vehicle routing
• Synchronized-services
• Time windows
• Adaptive large neighborhood search

This paper addresses a special vehicle routing problem, which extends the classical problem by considering the time window and synchronized-services constraints. A time window is associated with each client service and some services require simultaneous visits from different vehicles to be accomplished. This problem has many practical applications such as caregiver scheduling problem encountered in the home health care industry. The synchronization constraints in this problem interconnect various vehicles' routes, making the problem more challenging than standard vehicle routing problem with time windows, especially in designing neighborhood search-based methods. A mixed-integer programming model is proposed for the problem. Motivated by the challenge of computational time, an efficient Adaptive Large Neighborhood Search heuristic is proposed to solve the problem. The approach is evaluated on benchmark instances acquired from the literature and new large-scale test instances first generated in this paper. The numerical results indicate that our solution method is able to outperform existing approaches.

• 出版日期2019-1
• 单位清华大学; 上海交通大学