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

Ann-Kathrin Rothenbächer (), Michael Drexl () and Stefan Irnich ()
Additional contact information
Ann-Kathrin Rothenbächer: Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University, Mainz D-55099, Germany
Michael Drexl: Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University, Mainz D-55099, Germany; Faculty of Applied Natural Sciences and Industrial Engineering, Deggendorf Institute of Technology, Deggendorf D-94469, Germany
Stefan Irnich: Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University, Mainz D-55099, Germany

Transportation Science, 2018, vol. 52, issue 5, 1174-1190

Abstract: 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.

Keywords: vehicle routing; truck-and-trailer routing; branch-and-price-and-cut (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (26)

Downloads: (external link)
https://doi.org/10.1287/trsc.2017.0765 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:52:y:2018:i:5:p:1174-1190

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().