Program > By author > Rothenbächer Ann-Kathrin

Branch-Price-and-Cut for the Generalized Truck-and-Trailer Routing Problem
Ann-Kathrin Rothenbächer  1@  , Michael Drexl  1@  , Stefan Irnich  1@  
1 : Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University
Jakob-Welder-Weg 9, D-55128 Mainz -  Germany

We consider the truck-and-trailer routing problem with time windows (TTRPTW). The fleet consists of several lorries which may attach a trailer. As some customers are not accessible for a lorry with the trailer attached, the trailers can be parked at customer sites or additional transshipment locations. When a lorry returns to its trailer after a subtour, load can be transferred from the lorry to the trailer.

We extend the TTRPTW planning horizon to two days and allow customers to be visited either on both days or on only one day (in which case twice the daily supply must be collected), and we consider that the time needed for a load transfer depends on the amount of load transferred.

We tackle the problem with an exact branch-and-price-and-cut algorithm and generate the columns with a label-setting algorithm. The pricing procedure uses many known acceleration techniques, e.g., a bidirectional labelling, the ng-neighbourhood, reduced networks and relaxed dominance. Moreover, we separate subset-row inequalities to strengthen the lower bounds.

Computational studies show that our algorithm compares favourably with existing approaches on TTRP and TTRPTW benchmark instances known from literature.


Online user: 1