Minisum location of a traveling salesman

In this article we deal with the problem of locating on a network a service unit that must visit all the calls that are registered in a service list. Each node can generate a call with a given probability and the service list contains the first b calls that have arrived b ≤ n ( n is the number of nodes). In our problem the optimal location minimizes the expected length of a traveling salesman tour (TST) traveled. For the problem (which requires 2 n calculations of probabilities), we develop an O(n) Algorithm when b = n . for a tree, and study the sensitivity of this optimal solution when b < n .