Weight balance problem modeling and benders decomposition algorithm design of preighter

ZHAO Xiang-ling; LI Yun-fei

doi:10.19818/j.cnki.1671-1637.2023.02.014

Volume 23 Issue 2

Apr. 2023

Turn off MathJax

Article Contents

Article Navigation > Journal of Traffic and Transportation Engineering > 2023 > 23(2): 199-211

ZHAO Xiang-ling, LI Yun-fei. Weight balance problem modeling and benders decomposition algorithm design of preighter[J]. Journal of Traffic and Transportation Engineering, 2023, 23(2): 199-211. doi: 10.19818/j.cnki.1671-1637.2023.02.014

Citation:

ZHAO Xiang-ling, LI Yun-fei. Weight balance problem modeling and benders decomposition algorithm design of preighter[J]. Journal of Traffic and Transportation Engineering, 2023, 23(2): 199-211. doi: 10.19818/j.cnki.1671-1637.2023.02.014

Citation:

PDF( 1279 KB)

Weight balance problem modeling and benders decomposition algorithm design of preighter

doi: 10.19818/j.cnki.1671-1637.2023.02.014

ZHAO Xiang-ling^{1, 2
,},
LI Yun-fei¹

1.
College of Air Traffic Management, Civil Aviation University of China, Tianjin 300300, China
2.
Key Laboratory of Data Analytics and Optimization for Smart Industry, Ministry of Education, Northeastern University, Shenyang 110819, Liaoning, China

Funds:

National Natural Science Foundation of China 52272356

Fundamental Research Funds for the Central Universities 3122018D025

Postgraduate Research and Innovation Project of Civil Aviation University of China 2021YJS060

More Information

Author Bio:
ZHAO Xiang-ling(1979-), male, associate professor, PhD, zxl-llx@163.com
Received Date: 2022-11-04
Available Online: 2023-05-09
Publish Date: 2023-04-25

Abstract

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.
- preighter,
- weight and balance,
- multi-objective optimization,
- benders decomposition,
- simulated annealing,
- Gurobi solver

FullText(HTML)

References(32)

References

[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.015 QIN 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.009 ZHAO 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.htm GU 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.005 WANG 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.016 LI 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-0127 ZHANG 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.htm ZHANG 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.htm BU 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

Relative Articles

Supplements(0)

Cited By

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Get Citation

PDF

XML

Article Metrics

Article views (539) PDF downloads(63)

Weight balance problem modeling and benders decomposition algorithm design of preighter

doi: 10.19818/j.cnki.1671-1637.2023.02.014

Abstract

References

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Proportional views

Related

Weight balance problem modeling and benders decomposition algorithm design of preighter

doi: 10.19818/j.cnki.1671-1637.2023.02.014

Abstract

References

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Proportional views

Related

Export File

Citation

Format

Content