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

• The Vehicle Routing Problem with Simultaneous Pickup and Delivery with Time Limit is presented and the literature is summarized.
• A mixed-integer linear programming formulation of the problem is proposed.
• Designed small sized test instances with time limit and no time limit are solved with the CPLEX solver.
• A perturbation based variable neighborhood search heuristic based on classic savings heuristic, variable neighborhood search, and perturbation mechanism is developed.
• A number of well-known benchmark problems with time limit and no time limit are solved and the solutions are compared.
• A perturbation based variable neighborhood search heuristic proposed new best and robust solutions for benchmark problem instances.

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.