An efficient local search algorithm for split delivery vehicle routing problem with three-dimensional loading

Abstract The split delivery vehicle routing problem with three-dimensional loading constraints (3L-SDVRP) is a complex capacitated vehicle routing problem variant that considers split delivery and three-dimensional loading. It aims to determine the optimal routes for a fleet of vehicles by minimizing the number of vehicles required and the total travel distance. However, current methods are limited in efficiency and often yield suboptimal solutions. More efficient and effective methods are needed. Building on a state-of-the-art algorithm for solving the 3L-SDVRP, this paper proposes a more efficient algorithm with several novel features. Firstly, improvements to the packing method are introduced to enhance the loading performance and reduce required vehicles. Secondly, three new search operators are proposed to exploit problem characteristics in order to improve search efficiency significantly. Thirdly, a new adaptive splitting strategy dynamically decides when to split boxes according to the current status of the vehicle and node, thereby reducing computational costs. Lastly, the algorithm includes a new post-optimization method to further improve the solution quality. Extensive experiments validate that our proposed method efficiently reduces the number of required vehicles with fewer computational resources. The effectiveness of each novel component has also been confirmed through ablation experiments.