AIS-based algorithm for solving vehicle routing problem with simultaneous pick-up and delivery (VRP-SPD)

Abstract

Vehicle Routing Problem with Simultaneous Pick-up and Delivery (VRP-SPD) is regarded as an NP-hard problem, which takes unacceptable time to use traditional algorithms to solve. This article presents an artificial immune systems or AIS-based algorithm to solve the problem and the results shows competitive performance. This algorithm is embedded with a sweep approach to generate random initial population. For the mutation operator, a variety of local search techniques are applied to realize the diversity. The algorithm is tested with examples which used by many of other works and compared with the results obtained by an exact algorithm. Experimental results suggest that the algorithm is a valuable alternative to other metaheuristics for solving VRP-SPD.