Lower and upper bounds for the mixed capacitated arc routing problem

被引：75

作者：

Belenguer, Jose-Manuel

Benavent, Enrique

Lacomme, Philippe

Prins, Christian

机构：

[1] Univ Technol Troyes, ISTIT, F-10010 Troyes, France

[2] Univ Blaise Pascal, LIMOS, F-63173 Aubiere, France

[3] Univ Valencia, Dept Estadist & Invest Operat, E-46100 Burjassot, Valencia, Spain

来源：

COMPUTERS & OPERATIONS RESEARCH | 2006年 / 33卷 / 12期

关键词：

capacitated arc routing problem; mixed graph; lower bound; cutting plane; heuristic; memetic algorithm; waste collection;

D O I：

10.1016/j.cor.2005.02.009

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This paper presents a linear formulation, valid inequalities, and a lower bounding procedure for the mixed capacitated arc routing problem (MCARP). Moreover, three constructive heuristics and a memetic algorithm are described. Lower and upper bounds have been compared on two sets of randomly generated instances. Computational results show that the average gaps between lower and upper bounds are 0.51% and 0.33%, respectively. (c) 2005 Elsevier Ltd. All rights reserved.

引用

页码：3363 / 3383

页数：21

共 24 条

[1] Assad A. A., 1995, HDBK OPER R, P375, DOI 10.1016/S0927-0507(05)80109-4
[2] A cutting plane algorithm for the capacitated arc routing problem
Belenguer, JM
Benavent, E
[J]. COMPUTERS & OPERATIONS RESEARCH, 2003, 30 (05) : 705 - 728
[3] BELENGUER JM, 1997, DIRECTORY UCARP INST
[4] BELENGUER JM, 2003, DICT MCARP INSTANCES
[5] THE CAPACITATED ARC ROUTING PROBLEM - LOWER BOUNDS
BENAVENT, E
CAMPOS, V
CORBERAN, A
MOTA, E
[J]. NETWORKS, 1992, 22 (07) : 669 - 690
[6] The directed rural postman problem with turn penalties
Benavent, E
Soler, D
[J]. TRANSPORTATION SCIENCE, 1999, 33 (04) : 408 - 418
[7] Benavent E., 2000, Arc Routing: Theory, Solutions and Applications, P231
[8] A guided local search heuristic for the capacitated arc routing problem
Beullens, P
Muyldermans, L
Cattrysse, D
Van Oudheusden, D
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 147 (03) : 629 - 643
[9] The mixed general routing polyhedron
Corberán, A
Romero, A
Sanchis, JM
[J]. MATHEMATICAL PROGRAMMING, 2003, 96 (01) : 103 - 137
[10] Cormen T. H., 2001, Introduction to Algorithms, V2nd

← 1 2 3 →