目的 针对城市物流同步送取货场景中,车辆路径规划与货物三维装载协同不足、车厢空间随送取过程动态变化难以刻画、传统后开门装卸方式影响货物存取效率等问题,研究动态三维装载约束下带时间窗送取结合车辆路径优化方法,旨在提高车厢空间利用率、降低车辆使用与配送成本,并提升大规模送取一体配送问题的求解效率。方法 提出一种基于高度可变托盘与车厢侧边装卸方式的多阶段优化框架。首先,通过融合动态三维装载、时间窗、重量限制及先进后出等现实约束,构建以行驶距离最小、车辆使用数量最少、违反时间窗总时间最少的多目标优化模型。其次,提出多阶段混合算法（MLS-NSGA-Ⅲ）对三维装箱问题、客户聚类、车辆路径进行多目标优化,引入NSGA-Ⅲ算法染色体基因重构策略和局部搜索策略增强解的收敛性。结果 通过大规模实例对比分析了不同配送模式下的物流成本与资源利用率,同时使用标准算例验证了算法的有效性。结论 与传统模式相比,所提方法的物流总成本降低了约45.2%,且算法计算时间随规模增长降至近似线性,显著提升了大规模问题的求解效率。
Abstract
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.
关键词
动态三维装载 /
车辆路径问题 /
多目标优化 /
多阶段启发式算法 /
NSGA-Ⅲ
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}}
参考文献
[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.
基金
国家自然科学基金（72371044）;重庆市智能供应链工程技术研究中心开放基金（OFCISCETRC24202）;绿色物流智能技术重庆市重点实验室开放基金项目（KLGLIT2024YB002）
PDF(6470 KB)
渝公网安备 50010702501716号 渝ICP备15012534号-2
