Applications of estimation-based SLS algorithms to stochastic routing problems
P. Balaprakash, Mauro Birattari, Thomas Stuetzle, and Marco Dorigo
IRIDIA-CoDE, Universit´e Libre de Bruxelles (ULB), Brussels, Belgium
{pbalapra,mbiro,stuetzle,mdorigo}@ulb.ac.be
In a number of combinatorial optimization problems, some of the information
for when generating solutions is only available in a stochastic form. Two examples
of such problems are the probabilistic traveling salesman problem
(PTSP) and the vehicle routing problem with stochastic customers
and demands (VRPSCD). For example, in the PTSP each node requires a visit
only with a certain probability. The PTSP is commonly tackled using the a priori
optimization approach: find a solution that visits all nodes before actually
knowing which nodes are to be visited. From this a priori solution the associated
a posteriori solution is computed after knowing which nodes need to be visited.
It is obtained by skipping the nodes that do not require a visit and visiting the
others in the order in which they appear in the a priori solution. The goal in
the PTSP is to find an a priori solution that minimizes the expected cost of the
a posteriori solution.
In our research on stochastic routing problems, we have developed new iterative
improvement algorithms that use estimation-based techniques in the delta
evaluation for the PTSP [1]. Additional developments include the adoption of
the adaptive determination of the appropriate sample size and the usage of importance
sampling to improve the iterative improvement algorithms for cases [2],
where the probability that a node requires visit is very low.
In this presentation, we will give an overview of the estimation-based iterative
improvement algorithms we implemented for the PTSP. Next, we present
computational results for stochastic local search methods that make use of these
iterative improvement algorithms and we show that our best performing algorithms
are new state-of-the-art methods for the PTSP. Finally, we also consider
the extension of the estimation-based delta evaluation to the VRPSCD and
compare the initial computational results for our methods to the previously best
algorithms.