The Vehicle Routing Problem with Pickups, Deliveries, and 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 restricting pickups and deliveries based on the vehicle's 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 Linehauls. We propose a set-covering formulation and solve this via a novel price-and-branch algorithm 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 is also used to populate the route sets and provide initial solutions within the price-and-branch algorithm. Computational results show that for instances with up to 45 customers, the price-and-branch enforced with the ALNS finds solutions with only a 0.5% root-node optimality gap. A case study at our industry partner based on 24 days of operations reveals that up to 17.4% costs can be saved using our methods. 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%.