Premium
Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries
Author(s) -
Anily Shoshana,
Bramel Julien
Publication year - 1999
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199909)46:6<654::aid-nav4>3.0.co;2-a
Subject(s) - travelling salesman problem , pickup , traveling purchaser problem , point (geometry) , set (abstract data type) , 2 opt , mathematical optimization , computer science , bottleneck traveling salesman problem , vehicle routing problem , product (mathematics) , approximation algorithm , algorithm , branch and cut , mathematics , routing (electronic design automation) , integer programming , artificial intelligence , computer network , geometry , image (mathematics) , programming language
We consider the Capacitated Traveling Salesman Problem with Pickups and Deliveries (CTSPPD). This problem is characterized by a set of n pickup points and a set of n delivery points. A single product is available at the pickup points which must be brought to the delivery points. A vehicle of limited capacity is available to perform this task. The problem is to determine the tour the vehicle should follow so that the total distance traveled is minimized, each load at a pickup point is picked up, each delivery point receives its shipment and the vehicle capacity is not violated. We present two polynomial‐time approximation algorithms for this problem and analyze their worst‐case bounds. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 654–670, 1999