A neighborhood-based matheuristic for the vehicle routing problem with delivery options

This paper investigates a realistic version of the vehicle routing problem with delivery options (VRPDO) in the context of last-mile logistics management. The problem aims to optimize vehicle routing while considering alternative customer (request) delivery options and service levels for the last-mile delivery. The shared delivery locations can serve multiple requests simultaneously, but the chosen locations should satisfy the specific capacity and service levels, which requires synchronization between different routes. This synchronization of resources makes route planning more consistent with the needs of actual logistics services but greatly increases the complexity of algorithm design. To address this complex problem, a novel neighborhood-based matheuristic is proposed to intensively search for high-quality solutions from both primal and dual perspectives. Then, a relax-and-fix based insertion heuristic is developed to obtain initial feasible solutions for the proposed algorithm, which effectively balances the feasibility and optimality in solution construction. Finally, the performance of the proposed algorithm is evaluated on two sets of VRPDO benchmarks (small and large instances) available in the literature. The experimental results show that our proposed algorithm has superior performance compared to state-of-the-art methods, obtaining 114 out of 120 and 85 out of 120 best-known solutions for the small- and large-scale benchmark instances, respectively. Furthermore, a real VRPDO case study of a third-party logistics company in China is introduced, which confirms that the proposed algorithm is suitable for processing VRPDO in newly introduced real-world instances.