Title: Solving vehicle routing problem with simultaneous pickup and delivery using parallel simulated annealing algorithm

Authors: Dong Mu; Chao Wang; Fu Zhao; John W. Sutherland

Addresses: School of Economics and Management, Beijing Jiaotong University, SD 718, No. 3 Shang Yuan Cun, Hai Dian District Beijing, 100044, China ' School of Economics and Management, Beijing University of Technology, Jing A503, 100 Ping Le Yuan, Chaoyang District, Beijing 100124, China ' Environmental and Ecological Engineering; School of Mechanical Engineering, Purdue University, ME 2194, 585 Purdue Mall, West Lafayette, IN, 47907, USA ' Environmental and Ecological Engineering, Purdue University, Potter Engineering Center, Room 364, 500 Central Drive, West Lafayette, IN 47907, USA

Abstract: The vehicle routing problem with simultaneous pickup and delivery (VRPSPD) is an NP-hard combinatorial optimisation problem that has received considerable attention in the past few decades. A parallel simulated annealing (parallel-SA) algorithm that uses four different neighbourhood structures has been developed to solve this problem. The parallel-SA algorithm follows the traditional sequential SA algorithm with an integrated asynchronous and synchronous multiple Markov chains (MMC) approach and incorporates a master-slave structure in the algorithm. Computational results are reported for 72 test problems with 50 to 400 customers from Dethloff's medium-scale benchmark, Salhi and Nagy's medium-to-large-scale benchmark and Montane and Galvao's large-scale benchmark. Computational results indicate that the proposed parallel-SA algorithm is competitive with other well-known algorithms for VRPSPD from both quality of solution and computational time.

Keywords: simultaneous pickup and delivery; vehicle routing problem; VRP; parallel simulated annealing; combinatorial optimisation; multiple Markov chains; MMC.

DOI: 10.1504/IJSTL.2016.073323

International Journal of Shipping and Transport Logistics, 2016 Vol.8 No.1, pp.81 - 106

Received: 17 Mar 2014
Accepted: 30 Dec 2014

Published online: 30 Nov 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article