A note on branch-and-cut-and-price

被引：18

作者：

Feillet, Dominique ^{[1
]}

Gendreau, Michel ^{[2
,3
]}

Medaglia, Andres L. ^{[4
]}

Walteros, Jose L. ^{[4
]}

机构：

[1] CMP Georges Charpak, Ecole Mines St Etienne, F-13541 Gardanne, France

[2] Ecole Polytech, CIRRELT, Montreal, PQ H3C 3A7, Canada

[3] Ecole Polytech, MAGI, Montreal, PQ H3C 3A7, Canada

[4] Univ Los Andes, Dept Ingn Ind, Bogota, Colombia

来源：

OPERATIONS RESEARCH LETTERS | 2010年 / 38卷 / 05期

关键词：

Branch-and-cut-and-price; Column generation; Split Delivery Vehicle Routing Problem; Bus Rapid Transit Route Design Problem; ALGORITHM;

D O I：

10.1016/j.orl.2010.06.002

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we propose a methodology for branch-and-cut-and-price when cuts and columns are generated simultaneously. The methodology is illustrated with two application cases: the Split Delivery Vehicle Routing Problem (SDVRP) and the Bus Rapid Transit Route Design Problem (BRTRDP). (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：346 / 353

页数：8

共 14 条

[1] A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem [J].

Alves, Claudio ;

De Carvalho, J. M. Valerio .

COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (04) :1315-1328

[2] To split or not to split: That is the question [J].

Archetti, Claudia ;

Savelsbergh, Martin W. P. ;

Speranza, M. Grazia .

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW, 2008, 44 (01) :114-123

[3] A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting [J].

Belov, G ;

Scheithauer, G .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 171 (01) :85-106

[4]

de Carvalho JMV, 2005, INFORMS J COMPUT, V17, P175, DOI 10.1287/ijoc.1030.0060

[5]

DESAULNIERS G, 2005, GERAD 25 ANNIVERSARY

[6] Robust branch-and-cut-and-price for the capacitated vehicle routing problem [J].

Fukasawa, R ;

Longo, H ;

Lysgaard, J ;

de Aragao, MP ;

Reis, M ;

Uchoa, E ;

Werneck, RF .

MATHEMATICAL PROGRAMMING, 2006, 106 (03) :491-511

[7]

GENDREAU M, 2006, 2006851 LIA U AV

[8] SOLVING AIRLINE CREW SCHEDULING PROBLEMS BY BRANCH-AND-CUT [J].

HOFFMAN, KL ;

PADBERG, M .

MANAGEMENT SCIENCE, 1993, 39 (06) :657-682

[9]

Irnich Stefan., 2006, COLUMN GENERATION, P33

[10] Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement [J].

Ji, Xiaoyun ;

Mitchell, John E. .

DISCRETE OPTIMIZATION, 2007, 4 (01) :87-102

← 1 2 →