This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Laporte, G. Articles by Vocaturo, F.

An Adaptive Large Neighbourhood Search Heuristic for the Capacitated Arc-Routing Problem with Stochastic Demands

HEC Montréal, Monteal, Quebec, Canada H3T 2A7
Dipartimento di Elettronica, Informatica e Sistemistica, Università della Calabria, 87036 Arcavacata di Rende (CS), Italy
Dipartimento di Economia e Statistica, Università della Calabria, 87036 Arcavacata di Rende (CS), Italy
gilbert{at}crt.umontreal.ca
musmanno{at}unical.it
vocaturo{at}unical.it

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.

Key Words: capacitated arc-routing problem; stochastic programming with recourse; a priori optimization; adaptive large neighbourhood search
History: Received: March 2009; revised: July 2009; accepted: July 2009.