Secomandi, Nicola Analysis of a rollout approach to sequencing problems with stochastic routing applications. (English) Zbl 1043.90032 J. Heuristics 9, No. 4, 321-352 (2003). Summary: The paper considers sequencing problems, the traveling salesman problem being their natural representative. It studies a rollout approach that employs a cyclic heuristic as its main base algorithm. The theoretical analysis establishes that it is guaranteed to improve (at least in a weak sense) the quality of any feasible solution to a given sequencing problem. Besides other applications, the paper shows that it is well suited for applications that are embedded in dynamic and stochastic environments. The computational performance of the approach is investigated with applications to two stochastic routing problems. The dynamic version of the heuristic appears to be the first algorithm available in the literature to approximately solve a variant of one of these problems. Cited in 17 Documents MSC: 90B35 Deterministic scheduling theory in operations research 90B36 Stochastic scheduling theory in operations research 90B20 Traffic problems in operations research Keywords:rollout algorithms and policies; filter and fan and sequential fan candidate list strategies; dynamic and stochastic sequencing problems; stochastic shortest path problems; traveling salesman problem with stochastic travel times; vehicle routing problem with stochastic demands PDFBibTeX XMLCite \textit{N. Secomandi}, J. Heuristics 9, No. 4, 321--352 (2003; Zbl 1043.90032) Full Text: DOI