Sim-RandSHARP: A hybrid algorithm for solving the Arc Routing Problem with Stochastic Demands

This paper proposes a new hybrid algorithm for solving the Arc Routing Problem with Stochastic Demands (ARPSD). Our approach combines Monte Carlo simulation (MCS) with the RandSHARP algorithm, which is designed for solving the Capacitated Arc Routing Problem (CARP) with deterministic demands. The Ra...

Full description

Saved in:
Bibliographic Details
Main Authors: Gonzalez, S., Riera, D., Juan, A. A., Elizondo, M. G., Fonseca, P.
Format: Conference Proceeding
Language:English
Subjects:
Algorismes
Algorithm design and analysis
Algorithms
Algoritmos
Monte Carlo methods
mètodes Monte Carlo
métodos Monte Carlo
Probabilistic logic
Reliability
Routing
ruta para vehículos
ruta per a vehicles
Stochastic processes
vehicle routing
Vehicles
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper proposes a new hybrid algorithm for solving the Arc Routing Problem with Stochastic Demands (ARPSD). Our approach combines Monte Carlo simulation (MCS) with the RandSHARP algorithm, which is designed for solving the Capacitated Arc Routing Problem (CARP) with deterministic demands. The RandSHARP algorithm makes use of a CARP-adapted version of the Clarke and Wright Savings heuristic, which was originally designed for the Vehicle Routing Problem. The RandSHARP algorithm also integrates a biased-randomized process, which allows it to obtain competitive results for the CARP in low computational times. The RandSHARP algorithm is then combined with MCS to solve the ARPSD. Some numerical experiments contribute to illustrate the potential benefits of our approach.
ISSN:0891-7736
1558-4305
1558-4305
DOI:10.1109/WSC.2012.6465034