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

Ann-Kathrin Rothenbächer (), Michael Drexl () and Stefan Irnich ()
Additional contact information
Ann-Kathrin Rothenbächer: Johannes Gutenberg-University Mainz, Germany
Michael Drexl: Johannes Gutenberg-University Mainz, Germany
Stefan Irnich: Johannes Gutenberg-University Mainz, Germany

No 1617, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

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 ?eet consists of one or more trucks that may attach a trailer. Some customers are not accessible with a truckand-trailer combination, but can however be serviced by one if the trailer is previously detached and parked atasuitablelocation. Inthe?rstextension, the planning horizon comprises twodays and customers maybe 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 e?ectiveness of this pricing procedure can be attributed to the adaptation of techniques such as bidirectional labeling, the ng-neighbourhood, 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)
Pages: 31 pages
Date: 2016-09-15
New Economics Papers: this item is included in nep-cmp and nep-tre
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1617.pdf First version, 2016 (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:jgu:wpaper:1617

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().