A deterministic tabu search algorithm for the capacitated arc routing problem

被引：118

作者：

Brandao, Jose ^{[1
]}

Eglese, Richard

机构：

[1] Univ Minho, Escola Econ & Gestao, Dept Gestao, P-4704553 Braga, Portugal

[2] Univ Lancaster, Sch Management, Dept Management Sci, Lancaster LA1 4YX, England

来源：

COMPUTERS & OPERATIONS RESEARCH | 2008年 / 35卷 / 04期

关键词：

heuristics; arc routing; tabu search;

D O I：

10.1016/j.cor.2006.07.007

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The capacitated arc routing problem (CARP) is a difficult optimisation problem in vehicle routing with applications where a service must be provided by a set of vehicles on specified roads. A heuristic algorithm based on tabu search is proposed and tested on various sets of benchmark instances. The computational results show that the proposed algorithm produces high quality results within a reasonable computing time. Some new best solutions are reported for a set of test problems used in the literature. (C) 2006 Elsevier Ltd. All rights reserved.

引用

页码：1112 / 1126

页数：15

共 26 条

[1]

Ahr D., 2004, Ph.D. Thesis

[2] Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees [J].

Amberg, A ;

Domschke, W ;

Voss, S .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 124 (02) :360-376

[3]

Baldacci R, 2006, NETWORKS, V47, P52, DOI [10.1002/net.20091, 10.1002/NET.20091]

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

Belenguer, JM ;

Benavent, E .

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

[5] THE CAPACITATED ARC ROUTING PROBLEM - LOWER BOUNDS [J].

BENAVENT, E ;

CAMPOS, V ;

CORBERAN, A ;

MOTA, E .

NETWORKS, 1992, 22 (07) :669-690

[6] 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

[7]

Christofides N., 1976, 388 C MELL U GRAD SC

[8]

DeArmon JS, 1981, THESIS U MARYLAND CO

[9]

Dror M., 2000, Arc routing : Theory, solutions and applications

[10]

Edmonds J., 1973, Mathematical Programming, V5, P88, DOI 10.1007/BF01580113

← 1 2 3 →