A hybrid genetic algorithm for the traveling salesman problem with pickup and delivery

• DOI: 10.1007/s11633-009-0097-4
• Publication Date: 2009-01-19T07:18:00Z
• Authors: Fang-Geng Zhao; Jiang-Sheng Sun; Su-Jian Li; Wei-Min Liu
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

In this paper, a hybrid genetic algorithm (GA) is proposed for the traveling salesman problem (TSP) with pickup and delivery (TSPPD). In our algorithm, a novel pheromone-based crossover operator is advanced that utilizes both local and global information to construct offspring. In addition, a local search procedure is integrated into the GA to accelerate convergence. The proposed GA has been tested on benchmark instances, and the computational results show that it gives better convergence than existing heuristics.