The Capacitated Traveling Salesman Location Problem

David Simchi-Levi
Additional contact information
David Simchi-Levi: Columbia University, New York, New York

Transportation Science, 1991, vol. 25, issue 1, 9-18

Abstract: The capacitated traveling salesmen location problem is the problem of locating one service station with servers, each having a limited capacity, q . The service units must visit each day all the calls that are registered in a service list. Each call is generated with a given probability and the service list contains at most n calls. In the paper we present an O ( n 3 ) time heuristic for the problem on networks. This heuristic finds a solution whose relative worst-case error equals 3 /2−3/(2 q ). We also show how one can use this heuristic to solve the problem on the plane with rectilinear or Euclidean distances with the same worst-case error. In the latter case the heuristic is proved to be asymptotically optimal.

Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.25.1.9 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:25:y:1991:i:1:p:9-18

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().