×

Analysis of a rollout approach to sequencing problems with stochastic routing applications. (English) Zbl 1043.90032

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.

MSC:

90B35 Deterministic scheduling theory in operations research
90B36 Stochastic scheduling theory in operations research
90B20 Traffic problems in operations research
PDFBibTeX XMLCite
Full Text: DOI