A tutorial on column generation and branch-and-price for vehicle routing problems

被引：94

作者：

Feillet, Dominique ^{[1
]}

机构：

[1] Ecole Natl Super Mines, CMP Georges Charpak, F-13541 Gardanne, France

来源：

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH | 2010年 / 8卷 / 04期

关键词：

Column generation; Branch-and-price; Vehicle routing problem; DANTZIG-WOLFE DECOMPOSITION; SHORTEST-PATH PROBLEM; RESOURCE CONSTRAINTS; EXACT ALGORITHM; BUNDLE; INEQUALITIES; OPTIMIZATION;

D O I：

10.1007/s10288-010-0130-z

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper provides a tutorial on column generation and branch-and-price for vehicle routing problems. The main principles and the basic theory of the methods are first outlined. Some additional issues, including reinforcement of the relaxation or stabilization, complete the paper. For the sake of simplicity, this material is illustrated with the case of the vehicle routing problem with time windows.

引用

页码：407 / 424

页数：18

共 39 条

[1]

[Anonymous], TR9904 RIC U DEP COM

[2]

[Anonymous], IMMTR20019 TU DENM

[3] Recent advances in vehicle routing exact algorithms [J].

Baldacci, Roberto ;

Toth, Paolo ;

Vigo, Daniele .

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2007, 5 (04) :269-298

[4] A branch-and-cut procedure for the vehicle routing problem with time windows [J].

Bard, JF ;

Kontoravdis, G ;

Yu, G .

TRANSPORTATION SCIENCE, 2002, 36 (02) :250-269

[5] Accelerated label setting algorithms for the elementary resource constrained shortest path problem [J].

Boland, N ;

Dethridge, J ;

Dumitrescu, I .

OPERATIONS RESEARCH LETTERS, 2006, 34 (01) :58-68

[6] An exact algorithm for team orienteering problems [J].

Boussier, Sylvain ;

Feillet, Dominique ;

Gendreau, Michel .

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2007, 5 (03) :211-230

[7] Vehicle routing problem with time windows, part 1:: Route construction and local search algorithms [J].

Bräysy, I ;

Gendreau, M .

TRANSPORTATION SCIENCE, 2005, 39 (01) :104-118

[8] Vehicle routing problem with time windows, part II:: Metaheuristics [J].

Bräysy, I ;

Gendreau, M .

TRANSPORTATION SCIENCE, 2005, 39 (01) :119-139

[9] Comparison of bundle and classical column generation [J].

Briant, O. ;

Lemarechal, C. ;

Meurdesoif, Ph. ;

Michel, S. ;

Perrot, N. ;

Vanderbeck, F. .

MATHEMATICAL PROGRAMMING, 2008, 113 (02) :299-344

[10] Vehicle Routing Problem with elementary shortest path based column generation [J].

Chabrier, A .

COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (10) :2972-2990

← 1 2 3 4 →