An Adaptive Interactive Routing-Packing Strategy for Split Delivery Vehicle Routing Problem with 3D Loading Constraints

The split delivery vehicle routing problem with three-dimensional loading constraints (3L-SDVRP) extends the traditional capacitated vehicle routing problem by integrating vehicle routing and three-dimensional packing, thus increasing the overall complexity of the problem. The interaction between routing and packing is crucial to the efficacy of any solution method for 3L-SDVRP. However, conventional approaches such as packing first routing second (P1R2) and routing first packing second (R1P2) exhibit limitations in computational efficiency and adaptability. Based on current strategies, we propose a interactive routing-packing strategy that adaptively decides between loading a single node or two nodes together during the routing. By allowing independent node loading, our method enables the generation of a loading plan prior to routing, thereby eliminating the need for repetitive solving packing sub-problem---an advantage similar to the P1R2 paradigm. Conversely, loading two nodes together requires immediate packing adjustments and helps to reduce the number of vehicles needed---a benefit akin to the R1P2. Our strategy integrates the strengths of both P1R2 and R1P2, thereby achieving enhanced loading flexibility and computational efficiency. Experimental results demonstrate that our methodology outperforms existing strategies regarding vehicle count.