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 [J].