A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows. (May 2015)

• Record Type: Journal Article
• Authors: Wang, Chao; Mu, Dong; Zhao, Fu; Sutherland, John W.
• Is Part Of: Computers & industrial engineering. Volume 83(2015)
• Page Start: 111
• Page End: 122
• Publication Date: 2015-05
• Subjects: Parallel simulated annealing -- Simultaneous delivery and pickup -- Vehicle routing -- Time windows; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2015.02.005
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: 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. Abstract: 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.