Branch-and-Price-and-Cut for the Truck-and-Trailer Routing Problem with Time Windows

被引:41
作者
Rothenbaecher, Ann-Kathrin [1 ]
Drexl, Michael [1 ,2 ]
Irnich, Stefan [1 ]
机构
[1] Johannes Gutenberg Univ Mainz, Gutenberg Sch Management & Econ, Chair Logist Management, D-55099 Mainz, Germany
[2] Deggendorf Inst Technol, Fac Appl Nat Sci & Ind Engn, D-94469 Deggendorf, Germany
关键词
vehicle routing; truck-and-trailer routing; branch-and-price-and-cut; STABILIZED COLUMN GENERATION; SHORTEST-PATH PROBLEM; SOLVING TRUCK; CONSTRAINTS; INEQUALITIES; SEARCH; ALGORITHMS;
D O I
10.1287/trsc.2017.0765
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper, we present a new branch-and-price-and-cut algorithm to solve the truck-and-trailer routing problem with time windows (TTRPTW) and two real-world extensions. In all TTRPTW variants, the fleet consists of one or more trucks that may attach a trailer. Some customers are not accessible with a truck-and-trailer combination, but can however be serviced by one if the trailer is previously detached and parked at a suitable location. In the first extension, the planning horizon comprises two days and customers may be visited either on both days or only once, in which case twice the daily supply must be collected. The second extension incorporates load transfer times depending on the quantity moved from a truck to its trailer. The exact branch-and-price-and-cut algorithm for the standard variant and the two new extensions is based on a set-partitioning formulation in which columns are routes describing the movement of a truck and its associated trailer. Linear relaxations of this formulation are solved by column generation where new routes are generated with a dynamic programming labeling algorithm. The effectiveness of this pricing procedure can be attributed to the adaptation of techniques such as bidirectional labeling, the ng-neighborhood, and heuristic pricing using dynamically reduced networks and relaxed dominance. The cutting component of the branch-and-price-and-cut adds violated subset-row inequalities to strengthen the linear relaxation. Computational studies show that our algorithm outperforms existing approaches on TTRP and TTRPTW benchmark instances used in the literature.
引用
收藏
页码:1174 / 1190
页数:17
相关论文
共 37 条
[1]  
[Anonymous], 2013, REV METODOS CUANTITA
[2]   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
[3]   Heuristic for a real-life truck and trailer routing problem [J].
Batsyn, Mikhail ;
Ponomarenko, Alexander .
2ND INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY AND QUANTITATIVE MANAGEMENT, ITQM 2014, 2014, 31 :778-792
[4]   A Branch-and-Cut Algorithm for the Single Truck and Trailer Routing Problem with Satellite Depots [J].
Belenguer, Jose Manuel ;
Benavent, Enrique ;
Martinez, Antonio ;
Prins, Christian ;
Prodhon, Caroline ;
Villegas, Juan G. .
TRANSPORTATION SCIENCE, 2016, 50 (02) :735-749
[5]   Dual-optimal inequalities for stabilized column generation [J].
Ben Amor, Hatem ;
Desrosiers, Jacques ;
Valerio de Carvalho, Jose Manuel .
OPERATIONS RESEARCH, 2006, 54 (03) :454-463
[6]   Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem [J].
Bode, Claudia ;
Irnich, Stefan .
OPERATIONS RESEARCH, 2012, 60 (05) :1167-1182
[7]  
Bodin Lawrence, 2000, Arc Routing, P419
[8]   Ship routing and scheduling with flexible cargo sizes [J].
Bronmo, G. ;
Christiansen, M. ;
Nygreen, B. .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2007, 58 (09) :1167-1177
[9]   A heuristic approach for the truck and trailer routing problem [J].
Caramia, M. ;
Guerriero, F. .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2010, 61 (07) :1168-1180
[10]   A Milk Collection Problem with Incompatibility Constraints [J].
Caramia, Massimiliano ;
Guerriero, Francesca .
INTERFACES, 2010, 40 (02) :130-143