A set-partitioning-based heuristic for the vehicle routing problem

被引：44

作者：

Kelly, JP ^{[1
]}

Xu, JF

机构：

[1] Univ Colorado, Grad Sch Business, Boulder, CO 80309 USA

[2] Delta Technol Inc, Atlanta, GA 30354 USA

来源：

INFORMS JOURNAL ON COMPUTING | 1999年 / 11卷 / 02期

关键词：

vehicle routing problem; set-partitioning; tabu search; heuristic;

D O I：

10.1287/ijoc.11.2.161

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We develop a generic tabu search heuristic for solving the well-known vehicle routing problem. This algorithm explores the advantages of simple local search and improvement heuristics as well as a complex meta-heuristic. The solutions generated by these heuristics are selected and assembled by a set-partitioning model to produce superior solutions. Computational experience on standard benchmark problems is discussed and comparisons with other up-to-date heuristic methods are provided.

引用

页码：161 / 172

页数：12

共 24 条

[1]

Christofides N., 1979, Combinatorial optimization, P315

[2] SCHEDULING OF VEHICLES FROM CENTRAL DEPOT TO NUMBER OF DELIVERY POINTS [J].

CLARKE, G ;

WRIGHT, JW .

OPERATIONS RESEARCH, 1964, 12 (04) :568-&

[3] SET PARTITIONING BASED HEURISTICS FOR INTERACTIVE ROUTING [J].

CULLEN, FH ;

JARVIS, JJ ;

RATLIFF, HD .

NETWORKS, 1981, 11 (02) :125-143

[4] OPTIMAL SOLUTION OF VEHICLE-ROUTING PROBLEMS USING MINIMUM K-TREES [J].

FISHER, ML .

OPERATIONS RESEARCH, 1994, 42 (04) :626-642

[5] BASES FOR VEHICLE FLEET SCHEDULING [J].

GASKELL, TJ .

OPERATIONAL RESEARCH QUARTERLY, 1967, 18 (03) :281-&

[6] A TABU SEARCH HEURISTIC FOR THE VEHICLE-ROUTING PROBLEM [J].

GENDREAU, M ;

HERTZ, A ;

LAPORTE, G .

MANAGEMENT SCIENCE, 1994, 40 (10) :1276-1290

[7] FUTURE PATHS FOR INTEGER PROGRAMMING AND LINKS TO ARTIFICIAL-INTELLIGENCE [J].

GLOVER, F .

COMPUTERS & OPERATIONS RESEARCH, 1986, 13 (05) :533-549

[8]

GLOVER F, 1996, IN PRESS INTERFACE C

[9]

GLOVER F, 1992, EJECTION CHAINS REFE

[10]

Glover F., 1995, TABU SEARCH FUNDAMEN

← 1 2 3 →