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

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.