A simheuristic algorithm for solving the arc routing problem with stochastic demands

摘要

This paper proposes a simheuristic algorithm for solving the Arc Routing Problem with Stochastic Demands. Our approach combines Monte Carlo Simulation (MCS) with the RandSHARP metaheuristic, which was originally designed for solving the Capacitated Arc Routing Problem with deterministic demands (CARP). The RandSHARP metaheuristic is a biased-randomised version of a savings-based heuristic for the CARP, which allows it to obtain competitive results for this problem in low computational times. The RandSHARP is then combined with MCS to cope with the stochastic variant of the problem in a natural and efficient way. Our work is based on the use of a safety stock during the route-design stage. This safety stock can then be used during the delivery stage to satisfy unexpected demands. A reliability index is also defined to evaluate the robustness of each solution with respect to possible route failures caused by random demands. Some numerical experiments contribute to validate our approach and to illustrate its potential benefits.