Traveling Salesman Facility Location Problems

Dimitris J. Bertsimas
Additional contact information
Dimitris J. Bertsimas: Massachusetts Institute of Technology, Cambridge, Massachusetts

Transportation Science, 1989, vol. 23, issue 3, 184-191

Abstract: We consider two generic facility location problems, the traveling salesman facility location problem (TSFLP) and the probabilistic traveling salesman facility location problem (PTSFLP), both of which have been a subject of intensive investigation recently. Concerning the TSFLP, we first improve the worst-case bound of the best-known heuristic for the problem on networks and observe that it is optimal under the triangle inequality to locate the facility at a node, which always requires a visit. Concerning the PTSFLP, we reduce it to the solution of n probabilistic traveling salesman problems and moreover, we propose two polynomial time heuristics one for networks and one for Euclidean problems which are at most a factor of O (log n ) from both the optimal TSFLP and the PTSFLP. A by-product of our analysis is an O ( n 2 ) algorithm which solves the PTSFLP in a general network given an a priori probabilistic traveling salesman type of tour, thus improving the best-known algorithm by a factor of n . After the examination of the worst case behavior of the proposed heuristics we examine their average behavior. For Euclidean problems in which customer locations are random, we prove that the heuristic proposed above is asymptotically optimal, the PTSFLP is asymptotically very close to the TSFLP and the heuristic we are proposing is within 25% of the optimal TSFLP.

Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.23.3.184 (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:23:y:1989:i:3:p:184-191

Access Statistics for this article

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