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

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.