Finding the Optimal a Priori Tour and Location of a Traveling Salesman with Nonhomogeneous Customers

This paper deals with the following routing problem: on any given day a subset of k out of n nodes of a network require a service visit (0 ≤ k ≤ n). Each node of the network can generate a request with a given probability. The problem is to find an a priori tour with a minimum expected length through the n nodes such that any k given nodes will be visited in the same order they appear in the a priori tour. In contrast to other work, the probabilities of placing a demand at the different nodes are allowed to differ one from the other. Also discussed is the problem of finding the optimal home location (origin) for the service unit.