The Traveling Salesman Location Problem

The problem of locating a single new facility relative to m existing facilities has been studied extensively under the assumption that trips are always made between the new facility and a single existing facility each time a trip occurs. A variation of the problem is the traveling salesman location problem, which involves a traveling salesman who services m customers. Each time a trip occurs the salesman visits one or more customers during the trip. Thus, 2^m − 1 different itineraries can be formed, each occurring with a given probability. The new facility, which is the starting and ending point of each itinerary, is to be located such that the expected distance traveled per unit time is minimized. An iterative procedure is presented for solving the traveling salesman location problem; computational experience with the procedure is provided.