Perturbation heuristics for the pickup and delivery traveling salesman problem

Perturbation heuristics for the pickup and delivery traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor2003226
Country: United Kingdom
Volume: 29
Issue: 9
Start Page Number: 1129
End Page Number: 1141
Publication Date: Aug 2002
Journal: Computers and Operations Research
Authors: , ,
Keywords: programming: travelling salesman, heuristics
Abstract:

This article describes and compares seven perturbation heuristics for the Pickup and Delivery Traveling Salesman Problem (PDTSP). In this problem, a shortest Hamiltonian cycle is sought through a depot and several pickup and delivery pairs. Perturbation heuristics are diversification schemes which help a local search process move away from a local optimum. Three such schemes have been implemented and compared: Instance Perturbation, Algorithmic Perturbation, and Solution Perturbation. Computational results on PDTSP instances indicate that the latter scheme yields the best results. On instances for which the optimum is known, it consistently produces optimal or near-optimal solutions.

Reviews

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