A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows

•A vehicle routing problem with simultaneous pickup–delivery and time windows is considered.•A parallel simulated annealing algorithm with local search techniques is proposed.•The effectiveness of the proposed algorithm is verified by test and comparison.

This paper addresses a variant of the vehicle routing problem in which customers require simultaneous pickup and delivery of goods during specific individual time windows (VRPSPDTW). A general mixed integer programming model is employed to minimize the routing cost due to: the cost of vehicles and the travel cost of vehicles. A parallel Simulated Annealing (p-SA) algorithm that includes a Residual Capacity and Radial Surcharge (RCRS) insertion-based heuristic is developed and applied to solve this NP-hard optimization problem. Computational results are reported for 65 test problems from Wang and Chen’s benchmark and compared with the results from a Genetic Algorithm (GA) that minimizes the number of vehicles (NV) as the primary objective. Experimental results demonstrate the effectiveness of the p-SA algorithm, which is able to achieve the same objective response as 100% of the Wang and Chen small-scale benchmarks (number of customers from 10 to 50). For the Wang and Chen medium-scale benchmarks (number of 100 customers), the p-SA algorithm obtains better NV solutions for 12 instances and the same NV solutions for the remaining 44 instances. For the 44 instances with the same NV solutions, a secondary objective, travel distance (TD), the p-SA provides better solutions than the GA for 16 instances, and equal solutions for 7 instances. In addition, solutions are found for 30 large-scale instances, with customers of 200, 400, 600, 800 and 1000, which may serve as a new benchmark for the VRPSPDTW problem.