An Adaptive Large Neighbourhood Search Heuristic for the Capacitated Arc-Routing Problem with Stochastic Demands
- 1 February 2010
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 44 (1) , 125-135
Abstract
The capacitated arc-routing problem with stochastic demands (CARPSD) is an extension of the well-known capacitated arc-routing problem (CARP) in which demands are stochastic. This leads to the possibility of route failures whenever the realized demand exceeds the vehicle capacity. This paper presents the CARPSD in the context of garbage collection. It describes an adaptive large-scale neighbourhood search heuristic for the problem. Computational results show the superiority of this algorithm over an alternative solution approach.Keywords
This publication has 30 references indexed in Scilit:
- A deterministic tabu search algorithm for the capacitated arc routing problemComputers & Operations Research, 2008
- Exact methods based on node‐routing formulations for undirected arc‐routing problemsNetworks, 2005
- Improving robustness of solutions to arc routing problemsJournal of the Operational Research Society, 2005
- A guided local search heuristic for the capacitated arc routing problemEuropean Journal of Operational Research, 2003
- A cutting plane algorithm for the capacitated arc routing problemComputers & Operations Research, 2003
- The capacitated arc routing problem with intermediate facilitiesNetworks, 2001
- New Optimization HeuristicsJournal of Computational Physics, 1993
- The Capacitated Arc Routing Problem: Lower boundsNetworks, 1992
- Capacitated arc routing problemsNetworks, 1981
- On general routing problemsNetworks, 1976