A perturbation based variable neighborhood search heuristic for solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery with Time Limit

作者：Polat Olcay^*; Kalayci Can B; Kulak Osman; Guenther Hans Otto

来源：European Journal of Operational Research, 2015, 242(2): 369-382.

DOI：10.1016/j.ejor.2014.10.010

• Vehicle routing with simultaneous pickup and delivery
• Meta-heuristics
• Perturbation based neighborhood search

The Vehicle Routing Problem with Simultaneous Pickup and Delivery with Time Limit (VRPSPDTL) is a variant of the basic Vehicle Routing Problem where the vehicles serve delivery as well as pick up operations of the clients under time limit restrictions. The VRPSPDTL determines a set of vehicle routes originating and terminating at a central depot such that the total travel distance is minimized. For this problem, we propose a mixed-integer mathematical optimization model and a perturbation based neighborhood search algorithm combined with the classic savings heuristic, variable neighborhood search and a perturbation mechanism. The numerical results show that the proposed method produces superior solutions for a number of well-known benchmark problems compared to those reported in the literature and reasonably good solutions for the remaining test problems.

• 出版日期2015-4-16