Heuristic procedures for the capacitated vehicle routing problem

被引：22

作者：

Campos, V ^{[1
]}

Mota, E ^{[1
]}

机构：

[1] Univ Valencia, Dept Estadist & Invest Operat, E-46003 Valencia, Spain

来源：

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS | 2000年 / 16卷 / 03期

关键词：

vehicle routing; heuristics; tabu search; combinatorial optimization;

D O I：

10.1023/A:1008768313174

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper we present two new heuristic procedures for the Capacitated Vehicle Routing Problem (CVRP). The first one solves the problem from scratch, while the second one uses the information provided by a strong linear relaxation of the original problem. This second algorithm is designed to be used in a branch and cut approach to solve to optimality CVRP instances. In both heuristics, the initial solution is improved using tabu search techniques. Computational results over a set of known instances, most of them with a proved optimal solution, are given.

引用

页码：265 / 277

页数：13

共 18 条

[1]

AUGERAT P, 1995, RR949M U J FOUR I IM

[2]

BALL M, 1995, HDB OPERATIONS RES M, V8

[3] AN ALGORITHM FOR VEHICLE-DISPATCHING PROBLEM [J].

CHRISTOF.N ;

EILON, S .

OPERATIONAL RESEARCH QUARTERLY, 1969, 20 (03) :309-&

[4]

Christofides N., 1979, Combinatorial optimization, P315

[5]

CHRISTOFIDES N, 1994, EURO 13 GLASG JUL

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

CLARKE, G ;

WRIGHT, JW .

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

[7] POLYHEDRAL STUDY OF THE CAPACITATED VEHICLE-ROUTING PROBLEM [J].

CORNUEJOLS, G ;

HARCHE, F .

MATHEMATICAL PROGRAMMING, 1993, 60 (01) :21-52

[8]

Fischer M.L., 1995, HDBK OPER R, P1

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

FISHER, ML .

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

[10] A GENERALIZED ASSIGNMENT HEURISTIC FOR VEHICLE-ROUTING [J].

FISHER, ML ;

JAIKUMAR, R .

NETWORKS, 1981, 11 (02) :109-124

← 1 2 →