Traveling Salesman Facility Location Problems

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²) 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.