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

Abstract

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 amixed-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 wellknown benchmark problems compared to those reported in the literature and reasonably good solutions for the remaining test problems. © 2014 Elsevier B.V. All rights reserved.