The work aims to investigate a vehicle routing optimization method with simultaneous delivery and pickup under dynamic three-dimensional loading constraints and time windows, to improve compartment space utilization, reduce vehicle use and logistics costs, and enhance the solution efficiency for large-scale integrated delivery-pickup problems, so as to address the insufficient coordination between vehicle routing and three-dimensional cargo loading in urban logistics with simultaneous delivery and pickup, the difficulty of characterizing dynamic changes in compartment space during service operations, and the low cargo accessibility caused by conventional rear-door loading and unloading. A multi-phase optimization framework based on height-adjustable pallets and side-loading mechanisms for vehicle compartments was proposed. Firstly, a multi-objective optimization model integrating dynamic three-dimensional loading constraints, time windows, weight limits, and practical rules such as the Last-In-First-Out (LIFO) principle was constructed, aiming to minimize total travel distance, reduce the number of vehicles used, and decrease total time window violations. Secondly, a multi-phase hybrid algorithm (MLS-NSGA-Ⅲ) was designed to optimize the three-dimensional bin packing problem, customer clustering, and vehicle routing. The convergence of solutions was enhanced through the introduction of a chromosome reconstruction strategy and local search operators derived from the NSGA-III algorithm. Finally, large-scale case studies were conducted to compare logistics costs and resource utilization across different delivery modes, while standard benchmarks were utilized to validate the effectiveness of the algorithm. Experimental results demonstrate that the proposed method reduces total logistics costs by approximately 45.2% compared with traditional approaches. Furthermore, the algorithm's computational time shows an approximately linear growth trend as the problem scale increases, significantly enhancing solution efficiency for large-scale problems.
Key words
dynamic three-dimensional loading /
vehicle routing problem /
multi-objective optimization /
multi-stage heuristic algorithm /
NSGA-Ⅲ
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
References
[1] HORNSTRA R P, SILVA A, ROODBERGEN K J, et al.The Vehicle Routing Problem with Simultaneous Pickup and Delivery and Handling Costs[J]. Computers & Operations Research, 2020, 115: 104858.
[2] LELOUP E, PAQUAY C, PIRONET T, et al.A Three-Phase Algorithm for the Three-Dimensional Loading Vehicle Routing Problem with Split Pickups and Time Windows[J]. European Journal of Operational Research, 2025, 323(1): 45-61.
[3] GENDREAU M, IORI M, LAPORTE G, et al.A Tabu Search Algorithm for a Routing and Container Loading Problem[J]. Transportation Science, 2006, 40(3): 342-350.
[4] BORTFELDT A, YI J M.The Split Delivery Vehicle Routing Problem with Three-Dimensional Loading Constraints[J]. European Journal of Operational Research, 2020, 282(2): 545-558.
[5] WANG Y, WEI Z K, LUO S Y, et al.Collaboration and Resource Sharing in the Multidepot Time-Dependent Vehicle Routing Problem with Time Windows[J]. Transportation Research Part E: Logistics and Transportation Review, 2024, 192: 103798.
[6] RAMOS A G, SILVA E, OLIVEIRA J F.A New Load Balance Methodology for Container Loading Problem in Road Transportation[J]. European Journal of Operational Research, 2018, 266(3): 1140-1152.
[7] NING T, WANG J Y, HAN Y M.Logistics Distribution De-Carbonization Pathways and Effect in China: A Systematic Analysis Using VRPSDP Model[J]. International Journal of Low-Carbon Technologies, 2021, 16(4): 1404-1411.
[8] KREBS C, EHMKE J F, KOCH H.Effective Loading in Combined Vehicle Routing and Container Loading Problems[J]. Computers & Operations Research, 2023, 149: 105988.
[9] BORTFELDT A, HOMBERGER J. Packing First, Routing Second—A Heuristic for the Vehicle Routing and Loading Problem[J]. Computers & Operations Research, 2013, 40(3): 873-885.
[10] 王超, 金淳, 韩庆平. 三维装载与CVRP联合多目标优化问题的模型及算法[J]. 控制与决策, 2016, 31(5): 929-934.
WANG C, JIN C, HAN Q P, et al.Model and Algorithm for Multi-Objective Joint Optimization of Threedimensional Loading and CVRP[J]. Control and Decision, 2016, 31(5): 929-934.
[11] 杜博文, 张英贵, 刘春君, 等. 带三维装载和一对一取送约束的车辆路径优化研究[J]. 工业工程与管理, 2022, 27(2): 35-44.
DU B W, ZHANG Y G, LIU C J, et al.Optimization on One-to-One Pickup and Delivery Vehicle Routing Problem with Three-Dimensional Loading Constraints[J]. Industrial Engineering and Management, 2022, 27(2): 35-44.
[12] 颜瑞, 张群, 胡睿. 考虑三维装箱约束的车辆路径问题研究[J]. 中国管理科学, 2015, 23(1): 128-134.
YAN R, ZHANG Q, HU R.Research of Vehicle Routing Problem with Three-Dimensional Loading Constraints[J]. Chinese Journal of Management Science, 2015, 23(1): 128-134.
[13] 刘永, 岳志城, 王勇, 等. 三维装载优化模型与算法研究综述[J]. 包装工程, 2024, 45(17): 216-225.
LIU Y, YUE Z C, WANG Y, et al.Review of 3D Packing Optimization Model and Algorithm[J]. Packaging Engineering, 2024, 45(17): 216-225.
[14] DEB K, JAIN H.An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems with Box Constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577-601.
[15] WANG Y, YUAN Y Y, GUAN X Y, et al.Collaborative Two-Echelon Multicenter Vehicle Routing Optimization Based on State-Space-Time Network Representation[J]. Journal of Cleaner Production, 2020, 258: 120590.
[16] WASSAN N, NAGY G.Vehicle Routing Problem with Deliveries and Pickups: Modelling Issues and Meta-Heuristics Solution Approaches[J]. International Journal of Transportation, 2014, 2(1): 95-110.
[17] 刘永, 岳志城, 王勇. 托盘装载约束下带时间窗的配送车辆路径优化研究[J]. 交通运输系统工程与信息, 2023, 23(6): 262-273.
LIU Y, YUE Z C, WANG Y.Distribution Routing Problem with Time Window under Constraint of Pallet Loading[J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(6): 262-273.
[18] DERELI T, DAS G S.A Hybrid ‘Bee(s) Algorithm’ for Solving Container Loading Problems[J]. Applied Soft Computing, 2011, 11(2): 2854-2862.
[19] ŞAFAK Ö, ERDOĞAN G. A Large Neighbourhood Search Algorithm for Solving Container Loading Problems[J]. Computers & Operations Research, 2023, 154: 106199.
[20] MOURA A.A Model-Based Heuristic to the Vehicle Routing and Loading Problem[J]. International Transactions in Operational Research, 2019, 26(3): 888-907.
[21] KÜÇÜK M, TOPALOGLU YILDIZ S. Constraint Programming-Based Solution Approaches for Three-Dimensional Loading Capacitated Vehicle Routing Problems[J]. Computers & Industrial Engineering, 2022, 171: 108505.
[22] OU J W, LIU X L, XING L N, et al.Solving Many-Objective Delivery and Pickup Vehicle Routing Problem with Time Windows with a Constrained Evolutionary Optimization Algorithm[J]. Expert Systems with Applications, 2024, 255: 124712.
PDF(6470 KB)
