Weight balance problem modeling and benders decomposition algorithm design of preighter
-
摘要: 研究了民航客改货飞机的载重平衡问题，分析了客改货飞机与客机和纯货机在载重平衡问题所存在的差异，建立了具备主货舱指派问题和下货舱背包问题组合优化特性的客改货载重平衡问题的线性整数规划模型，实现业载量最大和配载重心偏离指定目标重心最小的多目标函数，包含了实际操作中客改货机型的货舱及其位置约束、各种质量约束、上下舱联合约束与飞机重心包线约束等；设计了Benders分解算法对该模型求解，把原问题分为主问题和子问题两部分；设计了改进模拟退火算法求解主问题，改进了离散变量的编码、变异以及个体修正等策略；设计了基于逻辑检查的y-check算法，用于检查子问题的上下舱联合限重、重心包线等复杂约束，给出了Benders' Cut约束模型；设计了以B757-200客改货飞机为例的20组不同规模算例，基于Gurobi、Lingo、人工配载和本文提出的算法对模型进行验证。研究结果表明：Gurobi求解质量和速度最好，平均业载量为29 517.3 kg，重心偏差为0.02%，求解时间为0.13 s；人工配载方法最差，平均业载量为27 131.9 kg，重心偏差为5.26%，求解时间为581.75 s；本文提出的算法由于采用了智能启发式算法，平均业载量为28 379.1 kg，与Gurobi和Lingo的最优解相比稍差，但重心偏差为0.05%，可以忽略不计，平均求解速度为20.33 s，远快于Lingo的7 370.65 s。Abstract: The weight balance problem (WBP) of civil aviation preighter was studied. The WBP differences between preighter, passenger aircraft, and cargo aircraft were compared. A linear integer programming model of preighter WBP was built with the combined optimization characteristics of main cargo compartment assignment problem and lower cargo backpack problem. The multi-objective function of the maximum payload and the minimum deviation of the center of gravity (CG) from the specified target was realized, including the cargo holds and their position constraints, various mass constraints, joint constraints on upper and lower cabins, as well as the CG envelope constraints of the preighter in actual operation. The benders decomposition algorithm was designed to solve the model, dividing the original problem into two parts: the main problem and the subproblem. To solve the main problem, a modified simulated annealing algorithm was proposed, which improved the coding, variation, and individual modification strategies of discrete variables. The y-check algorithm based on logical check was designed to check the complex constraints such as joint weight limits of upper and lower cabins and the CG envelope of subproblems. The benders' cut constraint model was given. Twenty groups of examples with different scales were designed by taking a B757-200 preighter as an example. The Gurobi, Lingo, artificial stowing, and the proposed algorithm were tested to verify the model. Research results show that the Gurobi has the best resolution quality and speed, whose average payload, CG deviation and solution time are 29 517.3 kg, 0.02%, and 0.13 s, respectively. The artificial stowing method is the worst, and its average payload, CG deviation, and solution time reach 27 131.9 kg, 5.26%, and 581.75 s, respectively. As an intelligent heuristic algorithm, the proposed algorithm gets a payload of 28 379.1 kg, which is slightly worse than the optimized solutions of Gurobi and Lingo. Its CG deviation is only 0.05%, which can be ignored. The average solution speed is 20.33 s, much faster than the Lingo's 7 370.65 s.
-
表 1 上下舱联合区间限重
Table 1. Combined weight limit of upper and lower cabins
区间 实际区间联合载量计算公式 区间限重/kg 1 舱位1 2 716 2 区间1+舱位2+(下货舱1)×10% 4 360 3 区间2+舱位3+(下货舱1)×80% 7 871 4 区间3+舱位4+(下货舱1)×10%+ (下货舱2)×40% 11 557 5 区间4+舱位5+(下货舱2)×40% 14 043 6 区间5+舱位6+(下货舱2)×20% 15 893 7 区间6+舱位7 17 712 8 区间9+舱位8 23 748 9 区间10+舱位9 21 909 10 区间11+舱位10+(下货舱3)×20% 20 102 11 区间12+舱位11+(下货舱3)×50% 18 257 12 区间13+舱位12+(下货舱3)×30%+ (下货舱4)×10% 15 733 13 区间14+舱位13+(下货舱4)×40% 11 969 14 区间15+舱位14+(下货舱4)×30% 8 239 15 舱位15+(下货舱4)×20% 3 476 
下载: 导出CSV
表 2 波音757-200基本参数
Table 2. Basic parameters of Boeing 757-200
参数 数值 参数 数值 PCGT/%MAC 23 WMPL/kg 30 708 WTOF/kg 10 000 IFuel, WTOW 4.5 航程燃油/kg 8 000 IFuel, WLW 0.4 WOEW/kg 52 752 IOEW 31.3 BM/m 25.19 BMAC/m 5.07 C1 70 000 CD/m 26.36
下载: 导出CSV
表 3 主舱舱位约束
Table 3. Main cargo hold space constraints
舱位 力臂/m 最大载荷/kg 最大高度/m 分区载荷/kg C1 9.91 2 716 2.00 C1~C5质量和不超过18 000 C2 12.17 2 948 2.00 C3 14.43 2 948 2.00 C4 16.69 2 948 2.00 C5 18.95 2 948 2.00 C6 21.21 2 948 2.00 C6~C10质量和不超过24 000 C7 23.47 2 948 2.00 C8 25.73 4 264 2.00 C9 27.99 4 264 2.00 C10 30.25 2 948 2.00 C11 32.51 2 948 2.00 C11~C15质量和不超过29 000 C12 34.77 2 948 2.00 C13 37.03 2 948 2.00 C14 39.29 2 948 2.00 C15 41.55 2 948 1.95
下载: 导出CSV
表 4 下货舱舱位约束
Table 4. Lower cargo hold space constraints
下货舱 下货舱1 下货舱2 下货舱3 下货舱4 货舱限重/kg 2 469 4 672 3 773 5 606 舱位累积限重/kg 4 672 7 393 力臂/m 13.58 18.64 32.73 38.29 最大容积/m3 4.9 13.9 14.2 16.7
下载: 导出CSV
表 5 业载量
Table 5. Payloads
kg 算例 z1+z2 本文算法 Gurobi Lingo 人工配载 1 25 583.6 27 166.0 27 194.0 25 543.0 2 28 706.8 30 705.0 30 708.0 27 733.0 3 29 876.7 29 711.0 29 711.0 27 605.0 4 28 209.5 28 901.0 28 901.0 26 503.0 5 28 229.5 29 820.0 29 760.0 27 798.0 6 27 652.0 28 486.0 28 466.0 26 101.0 7 27 753.2 29 052.0 29 052.0 26 639.0 8 28 685.1 29 669.0 29 669.0 27 839.0 9 29 121.7 29 676.0 29 676.0 27 327.0 10 28 760.2 29 548.0 29 538.0 27 543.0 11 28 503.0 30 050.0 30 035.0 28 012.0 12 28 692.6 30 368.0 30 368.0 28 117.0 13 27 791.3 28 669.0 28 653.0 25 786.0 14 27 502.6 28 691.0 28 691.0 26 023.0 15 28 338.2 29 348.0 29 348.0 26 479.0 16 28 441.3 30 078.0 29 989.0 27 721.0 17 29 138.2 30 240.0 30 240.0 28 032.0 18 28 771.7 29 860.0 29 834.0 26 841.0 19 28 707.9 29 725.0 29 725.0 27 054.0 20 29 116.3 30 583.0 30 583.0 27 942.0 均值 28 379.1 29 517.3 29 507.1 27 131.9
下载: 导出CSV
表 6 重心偏差
Table 6. CG deviations
%MAC 算例 z3 本文算法 Gurobi Lingo 人工配载 1 0.05 0.02 3.47 5.05 2 0.04 0.02 2.71 6.01 3 0.08 0.02 2.98 5.15 4 0.05 0.02 3.23 5.65 5 0.01 0.02 2.85 4.37 6 0.02 0.02 3.20 5.45 7 0.09 0.02 3.12 5.23 8 0.05 0.02 2.99 5.79 9 0.03 0.02 2.99 5.32 10 0.03 0.02 3.00 5.54 11 0.02 0.02 3.36 5.65 12 0.10 0.02 2.87 5.02 13 0.05 0.02 2.95 4.97 14 0.10 0.02 3.06 4.87 15 0.03 0.02 2.99 5.32 16 0.01 0.02 2.78 5.09 17 0.06 0.02 3.33 4.86 18 0.07 0.02 3.41 5.45 19 0.09 0.02 2.99 5.33 20 0.06 0.02 3.49 5.01 均值 0.05 0.02 3.09 5.26
下载: 导出CSV
表 7 求解时间
Table 7. Solving times
算例 时间/s 本文算法 Gurobi Lingo 人工配载 1 24.89 0.21 7 358.00 546.00 2 20.12 0.19 7 365.00 557.00 3 20.12 0.07 7 366.00 532.00 4 20.18 0.09 7 523.00 603.00 5 20.19 0.08 7 201.00 549.00 6 20.21 0.09 7 358.00 587.00 7 20.15 0.13 7 289.00 592.00 8 20.16 0.10 7 527.00 563.00 9 20.18 0.08 7 284.00 610.00 10 20.12 0.17 7 252.00 546.00 11 19.95 0.09 7 356.00 598.00 12 20.92 0.08 7 432.00 599.00 13 19.94 0.08 7 267.00 567.00 14 19.92 0.09 7 256.00 642.00 15 19.91 0.09 7 389.00 609.00 16 19.97 0.27 7 426.00 597.00 17 19.91 0.14 7 396.00 609.00 18 19.93 0.25 7 298.00 548.00 19 19.96 0.10 7 589.00 579.00 20 19.88 0.09 7 481.00 602.00 均值 20.33 0.13 7 370.65 581.75
下载: 导出CSV
-
[1] 张洪. 面向C919的装载配平模型分析及系统开发[D]. 天津: 中国民航大学, 2014.ZHANG Hong. Weight and balance model analysis of the C919 airplane and the system development[D]. Tianjin: Civil Aviation University of China, 2014. (in Chinese) [2] WONG W H, ZHANG A M, VAN HUI Y, et al. Optimal baggage-limit policy: airline passenger and cargo allocation[J]. Transportation Science, 2009, 43(3): 355-369. doi: 10.1287/trsc.1090.0266 [3] 康诗月. 航空联盟舱位控制及收益分配问题研究[D]. 南京: 南京航空航天大学, 2016.KANG Shi-yue. Research on seat inventory control and revenue allocation in airline alliance[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2016. (in Chinese) [4] 秦瑛, 霍佳震, 陈军, 等. 基于需求转移的航空公司座位分配博弈模型[J]. 统计与决策, 2016(2): 56-60. doi: 10.13546/j.cnki.tjyjc.2016.02.015QIN Ying, HUO Jia-zhen, CHEN Jun, et al. Game model of airline seat allocation based on demand transfer[J]. Statistics and Decision, 2016(2): 56-60. (in Chinese) doi: 10.13546/j.cnki.tjyjc.2016.02.015 [5] MARTIN-VEGA L A. Aircraft load planning and the computer description and review[J]. Computers and Industrial Engineering, 1985, 9(4): 357-369. doi: 10.1016/0360-8352(85)90023-3 [6] AMIOUNY S V, BARTHOLDI J J, VANDE VATE J H, et al. Balanced loading[J]. Operations Research, 1992, 40(2): 238-246. doi: 10.1287/opre.40.2.238 [7] WODZIAK J R, FADEL G M. Packing and optimizing the center of gravity location using a genetic algorithm[J]. Journal of Computers in Industry, 1994(11): 2-14. [8] HEIDELBERG K R, PARNELL G S, AMES J E. Automated air load planning[J]. Naval Research Logistics, 1998, 45(8): 751-768. doi: 10.1002/(SICI)1520-6750(199812)45:8<751::AID-NAV1>3.0.CO;2-R [9] MONGEAU M, BES C. Optimization of aircraft container loading[J]. IEEE Transactions on Aerospace and Electronic Systems, 2003, 39(1): 140-150. doi: 10.1109/TAES.2003.1188899 [10] DAHMANI N, KRICHEN S. On solving the bi-objective aircraft cargo loading problem[C]//IEEE. 6th Symposium on Multidisciplinary Analysis and Optimization. New York: IEEE, 2013: 352-362. [11] LIMBOURG S, SCHYNS M, LAPORTE G. Automatic aircraft cargo load planning[J]. Journal of the Operational Research Society, 2012, 63(9): 1271-1283. doi: 10.1057/jors.2011.134 [12] LURKIN V, SCHYNS M. The airline container loading problem with pickup and delivery[J]. European Journal of Operational Research, 2015, 244: 955-965. doi: 10.1016/j.ejor.2015.02.027 [13] ZHAO Xiang-ling, YUAN Yuan, DONG Yun, et al. Optimization approach to the aircraft weight and balance problem with the centre of gravity envelope constraints[J]. IET Intelligent Transport Systems, 2021, 15: 1269-1286. doi: 10.1049/itr2.12096 [14] 赵向领, 杜有权. 基于遗传算法的民用航空器配载问题[J]. 中国科技论文, 2021, 16(8): 849-854. doi: 10.3969/j.issn.2095-2783.2021.08.009ZHAO Xiang-ling, DU You-quan. Civil aircraft stowage based on genetic algorithm[J]. China Science Paper, 2021, 16(8): 849-854. (in Chinese) doi: 10.3969/j.issn.2095-2783.2021.08.009 [15] 谷润平, 贾旭颖, 赵向领, 等. 民航货机装载优化准确建模仿真研究[J]. 计算机仿真, 2019, 36(3): 20-26. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJZ201903005.htmGU Run-ping, JIA Xu-ying, ZHAO Xiang-ling, et al. Research on loading, optimization and accurate modeling and simulation of civil aviation cargo aircraft[J]. Computer Simulation, 2019, 36(3): 20-26. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSJZ201903005.htm [16] 孟超. 民航宽体客机腹舱装载优化研究[D]. 天津: 中国民航大学, 2020.MENG Chao. Research on the optimization of belly loading of civil aviation wide body airliner[D]. Tianjin: Civil Aviation University of China, 2020. (in Chinese) [17] 白杨. 航空物流系统分析及优化[D]. 南京: 南京航空航天大学, 2010.BAI Yang. Analysis and optimization of air logistics system[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2010. (in Chinese) [18] LARSEN O, MIKKELSEN G. An interactive system for the loading of cargo aircraft[J]. European Journal of Operational Research, 1980(4): 367-373. [19] MATHUR K. An integer-programming-based heuristic for the balanced loading problem[J]. Operations Research Letters, 1998, 22: 19-25. doi: 10.1016/S0167-6377(97)00044-8 [20] 张丽霞. 航空货运飞机装载问题研究[D]. 南京: 南京航空航天大学, 2012.ZHANG Li-xia. Research on air cargo loading problem[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2012. (in Chinese) [21] BROSH I. Optimal cargo allocation on board a plane: a sequential linear programming approach[J]. European Journal of Operational Research, 1981, 8(1): 40-46. doi: 10.1016/0377-2217(81)90027-8 [22] KALUZNY B L, DAVID SHAW R H A. Optimal aircraft load balancing[J]. International Transactions in Operational Research, 2009, 16(6): 767-787. doi: 10.1111/j.1475-3995.2009.00723.x [23] VANCROONENBURG W, VERSTICHEL J, TAVERNIER K, et al. Automatic air cargo selection and weight balancing: a mixed integer programming approach[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 65: 70-83. doi: 10.1016/j.tre.2013.12.013 [24] BRANDT F. The air cargo load planning problem[D]. Karlsruhe: Karlsruhe Institute of Technology, 2017. [25] 赵向领, 李云飞, 王治宇, 等.基于装卸顺序的中型机多航段协同配载优化[J/OL].北京航空航天大学学报, (2022-8-26)[2023-3-26]. https://doi.org/10.13700/j.bh.1001-5965.2022.0439 .ZHAO Xiang-ling, LI Yun-fei, WANG Zhi-yu, et al. Loading and unloading sequence based weight and balance problem optimization of medium-sized aircraft with multiple flight legs[J/OL]. (2022-8-26)[2023-3-26].https://doi.org/10.13700/j.bh.1001-5965.2022.0439 . (in Chinese)[26] BENDERS J F. Partitioning procedures for solving mixed-variables programming problems[J]. Numerische Mathematik, 1962, 4: 238-252. doi: 10.1007/BF01386316 [27] COTE J F, DELLAMICO M, IORI M. Combinatorial benders' cuts for the strip packing problem[J]. Operations Research, 2014, 62(3): 643-661. doi: 10.1287/opre.2013.1248 [28] 王克, 唐火红, 何其昌, 等. 混流生产线作业指派的优化方法研究[J]. 合肥工业大学学报(自然科学版), 2020, 43(3): 316-320. doi: 10.3969/j.issn.1003-5060.2020.03.005WANG Ke, TANG Huo-hong, HE Qi-chang, et al. Optimization method for assignment problem of mixed production line[J]. Journal of Hefei University of Technology (Natural Science), 2020, 43(3): 316-320. (in Chinese) doi: 10.3969/j.issn.1003-5060.2020.03.005 [29] 李建斌, 杨光耀, 陈峰. 零售业电子商务仓储中心货位指派问题研究[J]. 工业工程与管理, 2013, 18(4): 102-108. doi: 10.3969/j.issn.1007-5429.2013.04.016LI Jian-bin, YANG Guang-yao, CHEN Feng. Retail warehouse center storage location assignment research for E-commerce[J]. Industrial Engineering and Management, 2013, 18(4): 102-108. (in Chinese) doi: 10.3969/j.issn.1007-5429.2013.04.016 [30] 张钧, 贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39, 47. doi: 10.3778/j.issn.1002-8331.1902-0127ZHANG Jun, HE Ke-tai. Study on hybrid Genetic and simulated annealing algorithm for three-dimensional packing problems[J]. Computer Engineering and Applications, 2019, 55(14): 32-39, 47. (in Chinese) doi: 10.3778/j.issn.1002-8331.1902-0127 [31] 张德富, 彭煜, 朱文兴, 等. 求解三维装箱问题的混合模拟退火算法[J]. 计算机学报, 2009, 32(11): 2147-2156. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX200911006.htmZHANG De-fu, PENG Yu, ZHU Wen-xing, et al. A hybrid simulated annealing algorithm for the three-dimensional packing problem[J]. Chinese Journal of Computers, 2009, 32(11): 2147-2156. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX200911006.htm [32] 卜雷, 尹传忠, 蒲云. 零担货物序贯装箱优化问题的遗传模拟退火算法[J]. 西南交通大学学报, 2002, 37(5): 531-535. https://www.cnki.com.cn/Article/CJFDTOTAL-XNJT200205011.htmBU Lei, YIN Chuan-zhong, PU Yun. A genetic and simulated annealing algorithm for optimal sequential casing of less-than-carload freights[J]. Journal of Southwest Jiaotong University, 2002, 37(5): 531-535. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XNJT200205011.htm -
点击查看大图
图(10) / 表(7)
计量
- 文章访问数: 406
- HTML全文浏览量: 205
- PDF下载量: 58
- 被引次数: 0
