SIM-Randsharp: A hybrid algorithm for solving the ARC routing problem with stochastic demands

Sergio Puig González, Daniel Riera, Ángel A. Juan, Mónica G. Elizondo

RECERCAT (Consorci de Serveis Universitaris de Catalunya) · 18 citations · 14 references

Full text

Open access

Concepts

Abstract

This paper proposes a new hybrid algorithm for solving the Arc Routing Problem with Stochastic Demands\n(ARPSD). Our approach combines Monte Carlo simulation (MCS) with the RandSHARP algorithm,\nwhich is designed for solving the Capacitated Arc Routing Problem (CARP) with deterministic\ndemands. The RandSHARP algorithm makes use of a CARP-adapted version of the Clarke and Wright\nSavings heuristic, which was originally designed for the Vehicle Routing Problem. The RandSHARP algorithm\nalso integrates a biased-randomized process, which allows it to obtain competitive results for the\nCARP in low computational times. The RandSHARP algorithm is then combined with MCS to solve the\nARPSD. Some numerical experiments contribute to illustrate the potential benefits of our approach.

References

14