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

Next Previous

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]	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]	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]	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]	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]	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]	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]	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]	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]	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]	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]	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]	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]	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]	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

Get Citation

PDF

XML

Article Metrics

Article views (671) PDF downloads(64)

Weight balance problem modeling and benders decomposition algorithm design of preighter

doi: 10.19818/j.cnki.1671-1637.2023.02.014

Abstract

References

Catalog

Article Metrics

Related

Weight balance problem modeling and benders decomposition algorithm design of preighter

doi: 10.19818/j.cnki.1671-1637.2023.02.014

Abstract

References

Catalog

Article Metrics

Related

Export File

Citation

Format

Content