Minisum location of a travelling salesman on simple networks (Q1107451)

The authors study the problem to find the optimal home location of a travelling salesman on simple networks. The number of customers and their location can change from day to day. A typical objective function is to minimize the expected distance trevelled. The authors regard (1) unicycle networks: connected networks where the degree of each node is two; (2) 1-tree networks: tree on the nodes 2,3,...,n together with two arcs incident with node 1; (3) simple networks (cactus networks): each link belongs to at most one cycle. The paper includes an O(n) algorithm for the problem on a unicycle network. From this algorithm an algorithm for a 1-tree network is developed. For a simple network that may include several cycles an algorithm for tree networks and an algorithm for unicycle networks are used.