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

Sergio Gonzalez-Martin, Angel A. Juan, Daniel Riera, Monica G. Elizondo, Juan J. Ramos

Research output: Contribution to journalArticleResearchpeer-review

59 Citations (Scopus)


© 2018, © Operational Research Society 2018. 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.
Original languageEnglish
Pages (from-to)53-66
JournalJournal of Simulation
Issue number1
Publication statusPublished - 2 Jan 2018


  • Arc routing problem with stochastic demands
  • reliability indices
  • simheuristics
  • simulation-optimisation


Dive into the research topics of 'A simheuristic algorithm for solving the arc routing problem with stochastic demands'. Together they form a unique fingerprint.

Cite this