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.
| Subject : | : | Abstracts |
| Topics | : | Column generation/branch-and-price |
| Topics | : | Multi-period VRP |
| Topics | : | Routing with synchronization |
| Topics | : | Vehicle routing with time windows |
| PDF version | : |  PDF version |
