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

被引：100

作者：

Laporte, Gilbert ^{[1
]}

Musmanno, Roberto ^{[2
]}

Vocaturo, Francesca ^{[3
]}

机构：

[1] HEC Montreal, Montreal, PQ H3T 2A7, Canada

[2] Univ Calabria, Dipartimento Elettr Informat & Sistemist, I-87036 Arcavacata Di Rende, CS, Italy

[3] Univ Calabria, Dipartimento Econ & Stat, I-87036 Arcavacata Di Rende, CS, Italy

来源：

TRANSPORTATION SCIENCE | 2010年 / 44卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

capacitated arc-routing problem; stochastic programming with recourse; a priori optimization; adaptive large neighbourhood search; TO-RECORD TRAVEL; INTERMEDIATE FACILITIES; LOWER BOUNDS; ALGORITHM; OPTIMIZATION;

D O I：

10.1287/trsc.1090.0290

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：125 / 135

页数：11

共 40 条

[1]

Ahr D., 2004, Ph.D. thesis

[2]

Amberg A., 2002, P 35 ANN HAW INT C S

[3]

Assad A. A., 1995, HDB OPERATIONS RES M, V8, P375

[4] Exact methods based on node-routing formulations for undirected Arc-Routing Problems [J].