A heuristic for the pickup and delivery traveling salesman problem

A heuristic for the pickup and delivery traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20011337
Country: United Kingdom
Volume: 27
Issue: 9
Start Page Number: 905
End Page Number: 916
Publication Date: Aug 2000
Journal: Computers and Operations Research
Authors: , ,
Keywords: programming: travelling salesman, heuristics
Abstract:

This paper deals with the pickup and delivery traveling salesman problem. First we show how to adapt some classical traveling salesman heuristics to solve this problem, then we propose a new and efficient composite heuristic. The proposed heuristic is composed of two phases: a solution construction phase including a local optimization component and a deletion and re-insertion improvement phase. To evaluate its performance, the proposed heuristic was compared to the only available heuristic specially designed to solve this problem, to an adaptation of the most efficient heuristic designed to solve the traveling salesman problem with backhaul, to an adaptation of the farthest as well as to an adaptation of the cheapest insertion methods. Each of these heuristics was followed by our deletion and re-insertion procedure which considerably improved their performance. Results based on a new set of test problems show that the proposed heuristic outperforms all these reinforced heuristics.

Reviews

Required fields are marked *. Your email address will not be published.