A Branch-and-Cut Algorithm for the Symmetric Two-Echelon Capacitated Vehicle Routing Problem

被引：109

作者：

Jepsen, Mads ^{[1
]}

Spoorendonk, Simon ^{[1
]}

Ropke, Stefan ^{[2
]}

机构：

[1] Tech Univ Denmark, Dept Engn Management, DK-2800 Lyngby, Denmark

[2] Tech Univ Denmark, Dept Transport, DK-2800 Lyngby, Denmark

来源：

TRANSPORTATION SCIENCE | 2013年 / 47卷 / 01期

关键词：

vehicle routing; two-echelon systems; branch-and-cut; COLUMN GENERATION APPROACH; INEQUALITIES; SEARCH; MODELS; TRUCK;

D O I：

10.1287/trsc.1110.0399

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able. to solve 47 to optimality, surpassing previous exact algorithms.

引用

页码：23 / 37

页数：15

共 37 条

[1]

[Anonymous], 1986, ANN OPER RES

[2] A Column Generation Approach for the Split Delivery Vehicle Routing Problem [J].

Archetti, C. ;

Bianchessi, N. ;

Speranza, M. G. .

NETWORKS, 2011, 58 (04) :241-254

[3]

Archetti C, 2008, OPER RES COMPUT SCI, V43, P103, DOI 10.1007/978-0-387-77778-8_5

[4] The capacitated m-ring-star problem [J].

Baldacci, R. ;

Dell'Amico, M. ;

Gonzalez, J. Salazar .

OPERATIONS RESEARCH, 2007, 55 (06) :1147-1162

[5] An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts [J].

Baldacci, Roberto ;

Christofides, Nicos ;

Mingozzi, Aristide .

MATHEMATICAL PROGRAMMING, 2008, 115 (02) :351-385

[6] An Exact Method for the Capacitated Location-Routing Problem [J].

Baldacci, Roberto ;

Mingozzi, Aristide ;

Calvo, Roberto Wolfler .

OPERATIONS RESEARCH, 2011, 59 (05) :1284-1296

[7] New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem [J].

Baldacci, Roberto ;

Mingozzi, Aristide ;

Roberti, Roberto .

OPERATIONS RESEARCH, 2011, 59 (05) :1269-1283

[8] An exact solution framework for a broad class of vehicle routing problems [J].

Baldacci R. ;

Bartolini E. ;

Mingozzi A. ;

Roberti R. .

Computational Management Science, 2010, 7 (3) :229-268

[9] A lower bound for the split delivery vehicle routing problem [J].

Belenguer, JM ;

Martinez, MC ;

Mota, E .

OPERATIONS RESEARCH, 2000, 48 (05) :801-810

[10] A Branch-and-Cut method for the Capacitated Location-Routing Problem [J].

Belenguer, Jose-Manuel ;

Benavent, Enrique ;

Prins, Christian ;

Prodhon, Caroline ;

Calvo, Roberto Wolfler .

COMPUTERS & OPERATIONS RESEARCH, 2011, 38 (06) :931-941

← 1 2 3 4 →