Methodology for stochastic graph completion-time problems

Methodology for stochastic graph completion-time problems

0.00 Avg rating0 Votes
Article ID: iaor19982965
Country: United States
Volume: 8
Issue: 4
Start Page Number: 331
End Page Number: 343
Publication Date: Sep 1996
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: graphs
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.