Analysis of a rollout approach to sequencing problems with stochastic routing applications
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.
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