Traveling salesman facility location problems

Traveling salesman facility location problems

0.00 Avg rating0 Votes
Article ID: iaor1989624
Country: United States
Volume: 23
Issue: 3
Start Page Number: 184
End Page Number: 191
Publication Date: Aug 1989
Journal: Transportation Science
Authors:
Keywords: location, programming: travelling salesman
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 two polynomial time heuristics one for networks and one for Euclidean problems which are at most a factor of O(logn) from both the optimal TSFLP and the PTSFLP. A by-product of our analysis is an O(n2) 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 behaviour 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.

Reviews

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