The Vehicle Routing Problem with Pickups, Deliveries, and Scheduled Linehauls

We study the joint collection and distribution of less-than-truckload freight in a multi-depot setting. Linehauls between the depots allow for an increased freight consolidation, saving cost and greenhouse gas emissions. However, to realize these benefits, the linehauls must be coordinated with daily pickup-and-delivery routes from the depots to collect and distribute products. The routes are subject to loading constraints, which restrict pickups and deliveries based on the vehicles’ distribution and collection loads. In collaboration with a major European logistics provider, we define this problem as the Vehicle Routing Problem with Pickups, Deliveries, and Scheduled Linehauls. We propose a set-covering formulation and solve this via a novel restricted master heuristic where the associated labeling algorithm effectively incorporates the time synchronization between the departure times of generated routes and associated linehauls. Moreover, we develop an adaptive large neighborhood search (ALNS) algorithm that finds high-quality solutions quickly. The ALNS also populates the route sets and provides initial solutions within the restricted master heuristic. Computational results show that for instances with up to 45 customers, the restricted master heuristic enforced with the ALNS finds solutions with only a 0.04% gap relative to the linear relaxation at the root node. A case study at our industry partner based on 24 days of operations reveals that our methods can save up to 17.4% of costs. Additionally, we explore the impact of implementing service area restrictions per depot, a common industry practice that simplifies operations by transforming the problem into single-depot variants. Our findings show that this results in an average cost increase of 4.9%.