考虑重心约束的飞翼车二维装载问题研究

计佳璐, 王浩东, 姬生忠, 唐丽敏

系统工程理论与实践 ›› 2024, Vol. 44 ›› Issue (10) : 3451-3466.

PDF(1736 KB)
中国科学院数学与系统科学研究院期刊网
PDF(1736 KB)
系统工程理论与实践 ›› 2024, Vol. 44 ›› Issue (10) : 3451-3466. DOI: 10.12011/SETP2023-0398
论文

考虑重心约束的飞翼车二维装载问题研究

    计佳璐, 王浩东, 姬生忠, 唐丽敏
作者信息 +

Two-dimensional loading problem of the flying-wing-vehicle considering centre of gravity constraints

    JI Jialu, WANG Haodong, JI Shengzhong, TANG Limin
Author information +
文章历史 +

摘要

本文研究二维装载约束下带时间窗的飞翼车车辆路径优化问题(2L-CFWVRPTW), 建立同时考虑车载重心和飞翼车两侧装载约束的数学模型. 针对飞翼车两侧开门的特殊装箱模型, 设计devide分厢策略, 开发分厢最少开放空间和精英遗传算法相结合的混合启发式算法(EGA-DeLOS), 算法中引入重心约束改进装厢适应度函数. 经典算例测试结果表明: EGA-DeLOS算法能够解决飞翼车二维装载约束下的车辆路径问题, 重心约束能够提高装箱解的适用性, 并且能够有效求解2L-CFWVRPTW问题, 为使用飞翼车的物流企业提供科学的决策支持.

Abstract

This paper studies the two-dimensional loading capacitated flying-wing-vehicle routing problem with time window (2L-CFWVRPTW), and establish a mathematical model that simultaneously considers the centre of gravity of the vehicle and the loading constraints on both sides of the winged vehicle. Aiming at the special loading model of the winged vehicle with doors on both sides, this paper designs devide strategy, develops a hybrid heuristic algorithm combining devide least open space and elite genetic algorithm (EGA-DeLOS), which introduces the centre of gravity constraints to improve the loading adaptability function. The test results of classical examples show that: The EGA-DeLOS algorithm is able to solve the vehicle path problem under the loading constraints of the flying wing vehicle, and the centre of gravity constraints can improve the applicability of crate solutions, and the EGA-DeLOS algorithm is able to solve the 2L-CFWVRPTW problem, which provides scientific decision support for logistics enterprises using flying wing vehicles.

关键词

飞翼车 / 二维装载约束 / 重心约束 / EGA-DeLOS算法

Key words

flying-wing-vehicle / two-dimensional loading capacitated / centre of gravity constraint / EGA-DeLOS algorithm

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
计佳璐 , 王浩东 , 姬生忠 , 唐丽敏. 考虑重心约束的飞翼车二维装载问题研究. 系统工程理论与实践, 2024, 44(10): 3451-3466 https://doi.org/10.12011/SETP2023-0398
JI Jialu , WANG Haodong , JI Shengzhong , TANG Limin. Two-dimensional loading problem of the flying-wing-vehicle considering centre of gravity constraints. Systems Engineering - Theory & Practice, 2024, 44(10): 3451-3466 https://doi.org/10.12011/SETP2023-0398
中图分类号： U116.2   

参考文献

[1] IORI M. Metaheuristic algorithms for combinatorial optimization problems[J]. 4OR: Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2005(3): 163-166.
[2] Iori M, Salazar-González J J, Vigo D. An exact approach for the vehicle routing problem with two-dimensional loading constraints[J]. Transportation Science, 2007, 41(2): 253-264.
[3] Hokama P H D B, Miyazawa F K, Xavier E C. A branch-and-cut algorithm for the vehicle routing problem with two-dimensional loading constraints[J]. European Journal of operayion Research, 2002, 302(1): 259-269.
[4] Hokama P, Miyazawa F K, Xavier E C. A branch-and-cut approach for the vehicle routing problem with loading constraints[J]. Expert Systems with Applications, 2016, 47: 1-13.
[5] 季彬, 周赛琦, 张政. 分支定价方法求解带二维装箱约束的车辆路径问题[J]. 控制理论与应用, 2023, 40(3): 409-418. Ji B, Zhu S Q, Zhang Z. Branch-and-price approach for solving the vehicle routing problem with two-dimensional loading constraints[J]. Control Theory and Applications, 2023, 40(3): 409-418.
[6] Ferreira K M, De Queiroz T A, Toledo F M B. An exact approach for the green vehicle routing problem with two-dimensional loading constraints and split delivery[J]. Computers & Operations Research, 2021, 136: 105402.
[7] 王思睿, 王林, 刘瑞, 等. 基于分支定价算法的异质品装箱问题研究[J]. 系统工程理论与实践, 2023, 43(10): 3040- 3057. Wang S R, Wang L, Liu R, et al. Branch-and-price algorithm for bin packing problem with heterogeneous items[J]. Systems Engineering—Theory and Practice, 2023, 43(10): 3040-3057.
[8] Zachariadis E E, Tarantilis C D, Kiranoudis C T. Integrated distribution and loading planning via a compact metaheuristic algorithm[J]. European Journal of Operational Research, 2013, 228(1): 56-71.
[9] Wei L J, Zhang Z Z, Zhang D F, et al. A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints[J]. European Journal of Operational Research, 2015, 243(3): 798-814.
[10] Wei L J, Zhang Z Z, Zhang D F, et al. A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints[J]. European Journal of Operational Research, 2018, 265(3): 843-859.
[11] 尚正阳, 顾寄南, 潘家保. 考虑LIFO约束的2L-CVRP优化[J]. 计算机集成制造系统, 2021, 27(7): 2134-2143. Shang Z Y, Gu J N, Pan J B. 2L-CVRP vehicle routing problem with LIFO loading constraint[J]. Computer Integrated Manufacturing Systems, 2021, 27(7): 2134-2143.
[12] Zachariadis E E, Tarantilis C D, Kiranoudis C T. The vehicle Routing problem with simultaneous pick-ups and deliveries and two-dimensional loading constraints[J]. European Journal of Operational Research, 2016, 251(2): 369-386.
[13] 颜瑞, 朱晓宁, 张群, 等. 考虑二维装箱约束的多车场带时间窗的车辆路径问题模型及算法研究[J]. 中国管理科学, 2017, 25(7): 67-77. Yan R, Zhu X N, Zhang Q, et al. Research of the model and algorithm for two-dimensional multi-depots capacitated vehicle routing problem with time window constrain[J]. Chinese Journal of Management Science, 2017, 25(7): 67-77.
[14] Sabar N R, Bhaskar A, Chung E, et al. An adaptive memetic approach for heterogeneous vehicle routing problems with two-dimensional loading constraints[J]. Swarm and Evolutionary Computation, 2020, 58(1). DOI: 10.1016/j.swevo.2020.100730
[15] Ji B, Zhou S Q, Yu S S, et al. An enhanced neighborhood search algorithm for solving the split delivery vehicle routing problem with two-dimensional loading constraints[J]. Computers & Industrial Engineering, 2021(162): 162.DOI: 10.1016/j.cie.2021.107720.
[16] 李彤, 崔晶. 不确定需求环境下的路径-装载协同优化研究[J]. 系统工程理论与实践, 2021, 41(10): 2561-2580. Li T, Cui J. Research on routing-loading cooperative optimization under uncertain demand environment[J]. Systems Engineering—Theory and Practice, 2021, 41(10): 2561-2580.
[17] Khebbache-Hadji S, Prins C, Yalaoui A, et al. Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows[J]. Central European journal of operations research, 2013, 21(2): 307-336.
[18] Khebbache S, Prins C, Yalaoui A, et al. Heuristics for two-dimensional loading capacitated vehicle routing problem with time windows[J]. IFAC Proceedings Volumes, 2009, 42(4): 1544-1549.
[19] Khebbache S, Prins C, Yalaoui A, et al. Memetic algorithm for two-dimensional loading capacitated vehicle routing problem with time windows[J]. CIE: 2009 International Conference on Computers and Industrial Engineering, 2009(1-3): 1110-1113.
[20] Sbai I, Limam O, Krichen S. An adaptive genetic algorithm for the capacitated vehicle routing problem with time windows and two-dimensional loading constraints[J]. IEEE/ACS International Conference on Computer Systems & Applications, 2018: 88-95.
[21] 唐坚强, 祁超, 王红卫. 带时间窗的多仓库订单拆分与异构车辆路径联合优化方法[J]. 系统工程理论与实践, 2023, 43(5): 1446-1464. Tang J Q, Qi C, Wang H W. Integrated optimization approach to mult-depot order splitting and heterogeneous vehicle routing with time windows[J]. Systems Engineering—Theory & Practice, 2023, 43(5): 1446-1464.
[22] 刘志硕, 成屹男, 左兴权, 等. 考虑罐容限制的多油库多行程加油站配送优化问题研究[J]. 系统工程理论与实践, 2023, 43(4): 1232-1250. Liu Z S, Cheng Y N, Zuo X Q, et al. A multi-depot vehicle routing problem with multi-trip for gasoline stations with limited-capacity tanks[J]. Systems Engineering—Theory & Practice, 2023, 43(4): 1232-1250.
[23] 王增臣, 周良. 带二维装载约束的车辆调度问题建模及优化[J]. 计算机技术与发展, 2018, 28(10): 105-110. Wang Z C, Zhou L. Modeling and optimization of vehicle scheduling problem with two-dimensional loading constraints[J]. Computer Technology and Development, 2018, 28(10): 105-110.
[24] Reil S, Bortfeldt A, Mönch L. Heuristics for vehicle routing problems with backhauls, time windows, and 3D loading constraints[J]. European Journal of Operational Research, 2018, 266(3): 877-894.
[25] Toth P, Vigo D. The granular tabu search and its application to the vehicle-routing problem[J]. INFORMS Journal on Computing, 2003, 15(4): 333-346.
[26] Gendreau M, Manuel I, Gilbert L, et al. A Tabu search heuristic for the vehicle routing problem with twodimensional loading constraints[J]. Networks, 2008, 51(1): 4-18.

基金

国家自然科学基金(71871038);国家自然科学基金(71971035);国家自然科学基金(72201045)
PDF(1736 KB)

275

Accesses

0

Citation

Detail
段落导航
相关文章

/

〈 〉