A Metaheuristic Approach for the Cumulative Capacitated Arc Routing Problem

被引：1

作者：

Andres Lenis, Sergio ^{[1
]}

Carlos Rivera, Juan ^{[1
]}

机构：

[1] Univ EAFIT, Dept Math Sci, Math Modeling Res Grp, Medellin, Colombia

来源：

APPLIED COMPUTER SCIENCES IN ENGINEERING, WEA 2018, PT II | 2018年 / 916卷

关键词：

Capacitated arc routing problem; Cumulative objective; GRASP; Set covering based post-optimization; VND; Hybrid metaheuristic; ALGORITHM;

D O I：

10.1007/978-3-030-00353-1_9

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this paper we propose a new variant of the capacitated arc routing problem (CARP). In this new problem the objective function becomes a cumulative objective computed as the traveled distance multiplied by the vehicle load. A metaheuristic approach is proposed which is based on the hybridization of three known procedures: GRASP, VND and Set covering model. The metaheuristic is tested with some benchmark instances from CARP. The results allow to evaluate the performance with the different metaheuristic components and to compare the solutions with the classical objective function.

引用

页码：96 / 107

页数：12

共 24 条

[1] A cutting plane algorithm for the capacitated arc routing problem [J].

Belenguer, JM ;

Benavent, E .

COMPUTERS & OPERATIONS RESEARCH, 2003, 30 (05) :705-728

[2] The capacitated arc routing problem: Valid inequalities and facets [J].

Belenguer, JM ;

Benavent, E .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 1998, 10 (02) :165-187

[3] A guided local search heuristic for the capacitated arc routing problem [J].

Beullens, P ;

Muyldermans, L ;

Cattrysse, D ;

Van Oudheusden, D .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 147 (03) :629-643

[4]

Blum A., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P163, DOI 10.1145/195058.195125

[5] A deterministic tabu search algorithm for the capacitated arc routing problem [J].

Brandao, Jose ;

Eglese, Richard .

COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (04) :1112-1126

[6] Routing for relief efforts [J].

Campbell, Ann Melissa ;

Vandenbussche, Dieter ;

Hermann, William .

TRANSPORTATION SCIENCE, 2008, 42 (02) :127-145

[7]

Corberan A., 2014, SIAM

[8]

Dror M., 2000, Arc routing: theory, solutions and applications, DOI DOI 10.1007/978-1-4615-4495-1

[9] THE DELIVERY MAN PROBLEM AND CUMULATIVE MATROIDS [J].

FISCHETTI, M ;

LAPORTE, G ;

MARTELLO, S .

OPERATIONS RESEARCH, 1993, 41 (06) :1055-1064

[10] COMPUTATIONAL EXPERIMENTS WITH ALGORITHMS FOR A CLASS OF ROUTING-PROBLEMS [J].

GOLDEN, BL ;

DEARMON, JS ;

BAKER, EK .

COMPUTERS & OPERATIONS RESEARCH, 1983, 10 (01) :47-59

← 1 2 3 →