A hybrid genetic algorithm for the vehicle routing problem with simultaneous pickup and delivery

The vehicle routing problem with simultaneous pickup and delivery is an important variation of VRP where customers require simultaneous pickup and delivery service. In this paper, we proposed a hybrid genetic algorithm to solve this problem. In the proposed algorithm, we proposed a pheromone-based crossover operator that utilizes both the local and global information to construct offspring. The local information used in crossover operator includes edge lengths and adjacency relations, while the global information is stored as pheromone trails. To improve the performance of genetic algorithm, a local search procedure is integrated into GA, and acts as the mutation operator. Our hybrid algorithm was tested on benchmark instances, and experimental results are conclusively in favor of our algorithm.