Perturbation heuristics for the pickup and delivery traveling salesman problem
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. In several distribution management contexts, it is necessary to construct a shortest tour starting at a depot and making several pickup and deliveries. In the Traveling Salesman Problem with Pickup and Delivery, to each pickup point is associated a delivery point later in the tour. Like several routing problems, the PDTSP is very hard to solve to optimality and local search heuristics often get trapped in local optima. Perturbation heuristics provide a means of escaping from local optima. This paper describes and compares three types of perturbation heuristic. It shows that the best scheme consistently yields high-quality solutions.
perturbation heuristics pickup and delivery traveling salesman problem