Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries

Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries

0.00 Avg rating0 Votes
Article ID: iaor20002460
Country: United States
Volume: 46
Issue: 6
Start Page Number: 654
End Page Number: 670
Publication Date: Sep 1999
Journal: Naval Research Logistics
Authors: ,
Abstract:

We consider the Capacitated Traveling Salesman Problem with Pickups and Deliveries. 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.

Reviews

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