The Travelling Salesman Problem with pick-up and delivery

The Travelling Salesman Problem with pick-up and delivery

0.00 Avg rating0 Votes
Article ID: iaor1998963
Country: Netherlands
Volume: 79
Issue: 2
Start Page Number: 299
End Page Number: 310
Publication Date: Dec 1994
Journal: European Journal of Operational Research
Authors:
Abstract:

Demand points for pick-up and delivery are located in the plane. A single vehicle of a given capacity performs both pick-ups and deliveries. The objective is to find the shortest feasible tour. A real life application is described. We compare this problem with the classic Travelling Salesman Problem. Based on their similarity we develop a simple heuristic consisting of pick-up and delivery along the travelling salesman tour. Asymptotic behavior and worst case analysis are provided. We then introduce an alternative solution method which is an extension of the well known Cheapest Insertion heuristic. Performance of both heuristics is tested on various-size simulated problems.

Reviews

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