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

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

Journal of Simulation, 2018, vol. 12, issue 1, 53-66

Abstract: 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.

Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1057/jos.2016.11 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjsmxx:v:12:y:2018:i:1:p:53-66

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjsm20

DOI: 10.1057/jos.2016.11

Access Statistics for this article

Journal of Simulation is currently edited by Christine Currie

More articles in Journal of Simulation from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().