Probabilistic Sales-Delivery Man and Sales-Delivery Facility Location Problems on a Tree

Suppose that customers situated at nodes of a network generate calls for service with known probabilities. There is a server, who must perform a service tour that includes all customers requiring service. The order of providing service to customers for each potential list of calls is uniquely defined by some a priori fixed basic sequence of all the customers (a priori tour). The problems considered in this paper are to find an optimal home location for the server and (or) an optimal basic sequence so as to minimize the expected total waiting time or the expected maximal waiting time of customers, subject to the constraint that the expected total length of the tour is minimal. For these problems on a tree, polynomial algorithms are presented with complexity O ( n log n ) for general trees and O ( n ) for trees with bounded vertex degree. Reoptimization variants of these problems on a tree (when the server can reoptimize his tour for each list of calls) are also investigated.