Methodology for Stochastic Graph Completion-Time Problems

Assume a completion time T0 and a graph having edges with randomly chosen weights are specified. Each time an edge is traversed, the weight is selected at random, according to a fixed probability law indexed by that edge. Successive observations are independent, and independent of realizations at other edges. We consider the stochastic shortest path and traveling salesman problems of finding paths which maximize the probability of completion by the specified time. The methodology combines techniques of machine learning with the “k-opt” heuristic. The algorithm is supported by convergence analysis, and is also shown in computational experiments to be successful for randomized versions of TSP problems already in the literature and having from 10 to 57 vertices. To our knowledge, this success is well beyond other computational stochastic traveling salesman studies reported elsewhere. A feature of the algorithm is that the distributions of the random edge weights need not be specified, and so the technique is suited to on-line operation.