货运飞机装箱与配载组合优化

赵向领; 左蕾

doi:10.13224/j.cnki.jasp.20220844

货运飞机装箱与配载组合优化

doi: 10.13224/j.cnki.jasp.20220844

赵向领^1，2,,
左蕾^1,

1.
中国民航大学空中交通管理学院，天津 300300
2.
东北大学智能工业数据解析与优化教育部重点实验室，沈阳 110819

基金项目: 国家自然科学基金（U2333217, 52272356）；中央高校基本科研业务费专项（3122020049，3122019130）；中国民航大学研究生科研创新资助项目（2022YJS087）

详细信息

作者简介:
赵向领（1979-），男，副教授、硕士生导师，博士，主要从事飞机装载与配平方面的研究。E-mail：zlx-llx@163.com

中图分类号: V271.9
计量
- 文章访问数: 679
- HTML浏览量: 342
- PDF量: 50
- 被引次数: 0
出版历程
- 收稿日期: 2022-11-04
- 网络出版日期: 2024-01-16

Optimization of cargo aircraft packing and stowage combination

ZHAO Xiangling^{1，2
,},
ZUO Lei^1
,

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， China

摘要

摘要:
为了指导航空货运装箱操作，挖掘航班运力，提高运输效率，通过装箱与配载组合优化建模与求解，获得初步装箱方案。建立了分步优化模型、组合优化模型和改进的组合优化模型，3种模型以业载量装载最大和重心偏移指定位置最小为目标，综合考虑了实际装箱和配载操作中的各种限制条件，包括集装箱和飞机机舱的体积限制、质量限制、位置限制、平衡限制等各类约束。以B777F机型为例，采用商业求解器Gurobi对3种模型4类不同条件数据进行求解、验证和对比分析。试验表明：分步优化模型的求解速度最快，在限定时间内求解出来的案例平均使用时间为87.77 s；但重心偏差最大，平均偏差为1.35%，部分案例出现不可接受情况，最大达到3.66%，平均业载量最小，为97 412.37 kg。组合优化模型求解时间最长，48%的案例在限制时间内无法求解出来，求解出的案例平均使用时间为880.25 s，现实操作中很难接受。改进组合优化模型，求解时间可接受，平均为424.79 s，目标优化效果最好，平均业载量最大，为97 679.77 kg；所有重心偏差被控制在1.16%以内，平均为0.79%。
- 航空货运 /
- 装箱 /
- 载重平衡 /
- 整数规划 /
- 组合优化
Abstract:
To guide the packing operation, raise aircraft payload, and boost transportation effectiveness, models of the combination of air cargo palletization (ACP) and aircraft weight and balance (AWB) were developed. The bi-level optimization model (BOM), the combinatorial optimization model (COM), and the improved combinatorial optimization model (IOM) were proposed, and the objectives of the models were the maximum payload and the minimum center of gravity (CG) deviation from a defined target CG. The models also took into account a wide range of restrictions in real packing and stowing operations, such as limitations on capacity, weight, loading position, aircraft balance, and other factors in aircraft and unit loading devices. Four scenarios with various conditional data for three models were tested and analyzed using the commercial solver Gurobi, by taking the B777F as an example. Tests showed that while the BOM had the greatest CG deviation and the smallest mean payload (97 412.37 kg), it also had the fastest solution speed. For cases solved within the time limit, the mean computational time was 87.77 s, but the mean CG deviation was 1.35%. And there were some unacceptable cases where the maximum approached 3.66%. The COM test required the longest time for completion; 48% of the cases cannot be solved in the given time limit, and the mean took 880.25 s for completion, making it a challenge to accept in real-life scenarios. The IOM had an acceptable solution time, with a mean of 424.79 s, the best target optimization effect, and the greatest payload, with a mean of 97 679.77 kg; all CG deviations were controlled within 1.16%, with a mean of 0.79%.
- air cargo /
- packing /
- weight and balance /
- integer programming /
- combinatorial optimization

HTML

图 1 B777F的主货舱

Figure 1. Main cargo compartment side view of Boeing 777

下载: 全尺寸图片幻灯片

图 2 B777F的下货舱

Figure 2. Side view of Boeing 777 lower cargo hold

下载: 全尺寸图片幻灯片

图 3 情形1雷达图

Figure 3. Radar chart of scenario 1

下载: 全尺寸图片幻灯片

图 4 情形2雷达图

Figure 4. Radar chart of scenario 2

下载: 全尺寸图片幻灯片

图 5 情形3雷达图

Figure 5. Radar chart of scenario 3

下载: 全尺寸图片幻灯片

图 6 情形4雷达图

Figure 6. Radar chart of scenario 4

下载: 全尺寸图片幻灯片

表 1 符号说明

Table 1. Symbol description

分类	参数	含义
货物	i	货物下标
	I	可用的货物集合
	$ {w_i} $	货物i的质量
	$ {v_i} $	货物i的体积
集装箱	j	集装箱下标
	U	可用的集装箱集合
	C	集装箱装载的最大货物质量
	V	集装箱装载的最大货物体积
	$ {W_j} $	集装箱j装载的货物总质量
货舱	k	货舱下标
	L	飞机左侧货舱舱位的集合
	R	飞机右侧货舱舱位的集合
	P	可用的货舱集合
	$ {B_k} $	货舱k的平衡力臂
	$ {W_k} $	货舱k装载的最大货物质量
	$ {S_{ P}} $	主货舱里并排的成对位置
飞机	$ {B_{{\text{oew}}}} $	空机的重心位置
	$ {B_{{\text{tof}}}} $	燃油的重心位置
	$ {B_{{\text{zfw}}}} $	无油质量的重心位置
	$ {B_{{\text{lb}}}} $	装载后最小重心位置
	$ {B_{{\text{ub}}}} $	装载后最大重心位置
	$ {W_{{\text{mpl}}}} $	最大业载
	$ {W_{{\text{tripf}}}} $	航程消耗燃油质量
	$ {W_{{\text{tof}}}} $	起飞燃油质量
	$ {W_{{\text{oew}}}} $	运营空机质量
	$ {W_{{\text{zfw}}}} $	无油质量

下载: 导出CSV

表 2 飞机基本参数表

Table 2. Basic parameters of aircraft

载重平衡数据	数值
运营空机质量/kg	141750
最大起飞质量/kg	347451
最大着陆质量/kg	260815
最大无燃油质量/kg	248115
目标重心	28%C_ma

下载: 导出CSV

表 3 每个货舱位置的最大载荷和力臂

Table 3. Maximum load and balance arm for each cargo hold position

主货舱舱位	质量限制/kg	力臂/m	主货舱舱位	质量限制/kg	力臂/m
AL	4082	11.684	AR	4082	11.684
BL	4082	14.8844	BR	4082	14.8844
CL	4802	18.0848	CR	4082	18.0848
DL	4082	21.2852	DR	4082	21.2852
EL	4082	24.4856	ER	4082	24.4856
FL	6803	27.686	FR	6803	27.686
GL	6803	30.8864	GR	6803	30.8864
HL	6803	34.0868	HR	6803	34.0868
JL	4082	37.2872	JR	4082	37.2872
KL	4082	40.4876	KR	4082	40.4876
LL	4082	43.6626	LR	4082	43.6626
ML	4082	47.1932	MR	4082	47.1932
PL	4082	50.3936	PR	4082	50.3936
R	3527	53.213

前下货舱舱位	质量限制/kg	力臂/m	后下货舱舱位	质量限制/kg	力臂/m
11P	5102	11.66114	31P	6350	37.85108
12P	5102	14.15288	32P	5102	40.33266
13P	5102	16.63446	41P	5102	44.04868
21P	5102	19.1135	42P	5102	46.53026
22P	5102	21.59508
23P	6350	24.07666

下载: 导出CSV

表 4 测试数据

Table 4. Test data

算例	条件	货物数量	质量范围/kg	体积范围/m³	$ {W_{{\text{pla}}}} $/kg	$ {V_{{\text{va}}}} $/m³
1	$ \begin{gathered} {W_{{\text{pla}}}} \leqslant {W_{{\text{mpl}}}} \\ _{}{V_{{\text{va}}}} \leqslant {V_{{\text{mv}}}} \\ \end{gathered} $	340	[290,305]	[1.0,1.2]	101299	372.49
2		720	[132,152]	[0.35,0.45]	102136	288.19
3		760	[127,140]	[0.35,0.45]	101389	304.03
4		800	[120,135]	[0.35,0.45]	101944	319.82
5		780	[115,135]	[0.4,0.55]	97483	371.01
6	$ \begin{gathered} {W_{{\text{pla}}}} \geqslant {W_{{\text{mpl}}}} \\ ^{}{V_{{\text{va}}}} \leqslant {V_{{\text{mv}}}} \\ \end{gathered} $	1080	[86,106]	[0.3,0.4]	103772	378.25
7		760	[50,260]	[0.01,1]	118344	391.43
8		1020	[95,110]	[0.3,0.4]	104649	357.75
9		1040	[95,110]	[0.3,0.4]	106730	364.68
10		1100	[84,104]	[0.3,0.45]	103459	410.15
11		340	[51,600]	[0.01,2.59]	109934	452.58
12		360	[52,599]	[0.01,2.71]	117501	460.52
13		380	[52,598]	[1,1.2]	122523	416.63
14		400	[50,549]	[1,1.2]	122160	438.49
15		1060	[93,108]	[0.3,0.4]	106592	371.54
16	$ \begin{gathered} {W_{{\text{pla}}}} \leqslant {W_{{\text{mpl}}}} \\ _{}{V_{{\text{va}}}} \geqslant {V_{{\text{mv}}}} \\ \end{gathered} $	400	[51,448]	[0.03,2.39]	100377	469.6
17		740	[123,138]	[0.01,1.5]	96386	536.6
18		780	[115,135]	[0.01,1.4]	97483	563.34
19		760	[125,140]	[0.02,1.6]	100824	621.6
20		800	[120,135]	[0.01,1.4]	101944	569.44
21		720	[132,152]	[0.01,1.8]	102136	669.15
22		820	[51,190]	[0.01,1.3]	98501	563.02
23		840	[50,180]	[0.01,1.3]	96961	566.94
24		860	[50,170]	[0.01,1.3]	94766	554.41
25		880	[50,170]	[0.01,1.2]	95023	532.87
26	$ \begin{gathered} {W_{{\text{pla}}}} \geqslant {W_{{\text{mpl}}}} \\ _{_{}}^{}{V_{{\text{va}}}} \geqslant {V_{{\text{mv}}}} \\ \end{gathered} $	360	[51,598]	[0.01,2.69]	111772	490.57
27		380	[50,500]	[0.03,2.41]	107475	480.7
28		800	[50,230]	[0.01,1.4]	114198	569.44
29		820	[115,140]	[0.01,1.3]	104584	563.02
30		840	[115,130]	[0.01,1.3]	102933	566.94

下载: 导出CSV

表 5 求解结果

Table 5. Solution results

算例	装箱配载分步优化模型				装箱配载组合优化模型				改进的组合优化模型
算例	Z₂/kg	Z₃/%	t/s	（V_va/V_mv）/%	Z₄/kg	Z₅/%	t/s	（V_va/V_mv）/%	Z₆/kg	Z₇	t/s	（V_va/V_mv）/%
1	101299	0.8707	0.26	79.58	101299	1.2069	115.22	79.58	101299	0.6979	1.65	79.58
2	102136	1.6162	0.17	61.57	102136	0.8087	337.05	61.57	102136	0.7106	3.07	61.57
3	101389	1.7336	0.16	64.95	101389	0.6998	493.67	64.95	101389	0.7900	2.31	64.95
4	101944	1.9962	0.15	68.33	101944	0.7509	469.52	68.33	101944	0.6905	2.34	68.33
5	97483	1.425	0.1	79.26	97483	0.8150	430.65	79.26	97483	0.6782	4.12	79.26
均值	100850	1.53	0.17	70.74	100850	0.86	369.22	70.74	100850	0.71	2.70	70.74
6	100446	1.4758	0.37	78.14	102297	0.7034	699.95	79.55	102296	0.8288	5.62	79.59
7	102294	0.8524	0.38	72.01	102291	0.7957	679.25	71.40	102294	0.7040	7.52	65.71
8	101084	0.6860	1.86	73.76	102293	0.6913	307.99	74.56	102300	0.7567	8.97	74.62
9	102292	0.8359	0.41	74.58	102292	0.7345	1027.1	74.49	102300	0.7395	5.19	74.72
10	101780	0.6936	0.39	86.14	102295	0.9775	1064.9	86.48	102296	0.9129	8.4	86.53
11	102299	1.0558	0.28	88.08	102299	0.7147	678.55	88.90	102291	0.8067	1.05	82.27
12	102295	2.0351	0.34	83.18	102297	0.7350	397.29	81.52	102299	0.9429	1.45	79.93
13	102300	0.8665	0.24	73.07	102296	1.0849	142.03	67.99	102294	0.9375	1.12	79.67
14	102299	1.4869	0.31	77.39	102294	0.7906	290.9	74.98	102294	1.1530	0.86	70.96
15	102294	1.5040	0.65	76.16	102291	0.7151	939.6	76.07	102292	0.7004	6.46	74.88
均值	101938	1.1492	0.523	78.25	102294	0.7943	623.6	77.59	102295	0.8483	4.66	76.89
16	100323	0.7095	41.74	99.86	100263	0.6830	3600	99.47	100274	0.6829	3600	99.63
17	90215	0.6937	3.88	99.98	89892	0.6427	3600	99.40	90214	0.6456	750.73	99.98
18	88612	1.4897	92.94	99.98	88283	0.6396	3600	99.55	88605	1.0757	3600	99.97
19	88612	3.6554	232.88	100	86936	0.6307	3600	99.60	87107	0.7018	3600	99.92
20	87167	1.9067	952.48	99.99	92006	0.6514	3600	99.62	92230	0.8631	3600	99.96
21	85052	0.9759	10.25	99.99	84808	0.6332	3600	99.46	84971	0.6228	3600	99.86
22	92468	2.9749	270.76	99.98	92363	0.6549	3600	99.70	93474	0.9627	3045	99.99
23	90607	1.0746	6.19	99.97	90662	0.6492	3600	99.90	90697	0.8284	1168	99.97
24	89402	2.9766	2.89	99.99	89289	0.6533	3600	99.71	89393	0.6433	3600	99.97
25	91197	0.7971	9.32	99.98	91124	0.6477	3600	99.79	91203	0.6599	1138	99.99
均值	90365	1.7254	162.3	99.97	90562	0.6485	3600	99.62	90816	0.7686	2770	99.92
26	102297	0.7707	192.91	91.80	102291	0.9935	491.82	85.81	102292	1.0507	1.85	85.35
27	102291	0.8499	807.61	94.54	102292	0.8656	474.07	91.94	102298	0.7644	1.99	90.18
28	102281	0.6904	3600	94.58	102299	0.7379	1365.5	97.95	102297	0.8747	4.43	94.63
29	95029	1.1038	2.09	99.99	94844	0.6708	3600	99.72	95019	0.6630	3600	99.97
30	93184	0.7741	1.01	99.99	92719	0.7698	3600	99.23	93112	0.6554	3600	99.89
均值	99016	0.8378	923.62	96.18	98889	0.8075	1906.29	94.93	99003	0.8016	1441.65	94.01

下载: 导出CSV

参考文献(25)

[1]	BRANDT F,NICKEL S. The air cargo load planning problem-a consolidated problem definition and literature review on related problems[J]. European Journal of Operational Research,2019,275(2): 399-410. doi: 10.1016/j.ejor.2018.07.013
[2]	TECHANITISAWAD A,TANGWIWATWONG P. A GA-based heuristic for the interrelated container selection loading problems[J]. Industrial Engineering and Management Systems,2004,3: 22-37.
[3]	CESCHIA S,SCHAERF A. Local search for a multi-drop multi-container loading problem[J]. Journal of Heuristics,2013,19(2): 275-294. doi: 10.1007/s10732-011-9162-6
[4]	LIU D S,TAN K C,HUANG S Y,et al. On solving multiobjective Bin packing problems using evolutionary particle swarm optimization[J]. European Journal of Operational Research,2008,190(2): 357-382. doi: 10.1016/j.ejor.2007.06.032
[5]	BAYRAKTAR T,ERSÖZ F,KUBAT C. Effects of memory and genetic operators on Artificial Bee Colony algorithm for Single Container Loading problem[J]. Applied Soft Computing,2021,108: 107462. doi: 10.1016/j.asoc.2021.107462
[6]	GIMENEZ-PALACIOS I,ALONSO M T,ALVAREZ-VALDES R,et al. Logistic constraints in container loading problems: the impact of complete shipment conditions[J]. TOP,2021,29(1): 177-203. doi: 10.1007/s11750-020-00577-8
[7]	LI Yanzhi,TAO Yi,WANG Fan. A compromised large-scale neighborhood search heuristic for capacitated air cargo loading planning[J]. European Journal of Operational Research,2009,199(2): 553-560. doi: 10.1016/j.ejor.2008.11.033
[8]	TANG C H. A scenario decomposition-genetic algorithm method for solving stochastic air cargo container loading problems[J]. Transportation Research Part E: Logistics and Transportation Review,2011,47(4): 520-531. doi: 10.1016/j.tre.2010.11.013
[9]	KALUZNY B L,SHAW R H A D. Optimal aircraft load balancing[J]. International Transactions in Operational Research,2009,16(6): 767-787. doi: 10.1111/j.1475-3995.2009.00723.x
[10]	VERSTICHEL J,VANCROONENBURG W,SOUFFRIAU W,et al. A mixed integer programming approach to the aircraft weight and balance problem[J]. Procedia- Social and Behavioral Sciences,2011,20: 1051-1059. doi: 10.1016/j.sbspro.2011.08.114
[11]	HUANG Kuancheng,CHI Wenhou. A Lagrangian relaxation based heuristic for the consolidation problem of airfreight forwarders[J]. Transportation Research Part C: Emerging Technologies,2007,15(4): 235-245. doi: 10.1016/j.trc.2006.08.006
[12]	BOOKBINDER J H,ELHEDHLI S,LI Zichao. The air-cargo consolidation problem with pivot weight: models and solution methods[J]. Computers & Operations Research,2015,59: 22-32.
[13]	张丽霞. 航空货运飞机装载问题研究[D]. 南京: 南京航空航天大学,2012. ZHANG Lixia. Research on air cargo loading problem[D]. Nanjing: Nanjing University of Aeronautics and Astronautics,2012. (in Chinese ZHANG Lixia. Research on air cargo loading problem[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2012. (in Chinese)
[14]	赵雨霏. 我国快递企业航空货运飞机装载优化研究[D]. 长春: 吉林大学,2016. ZHAO Yufei. Research on optimization of air cargo loading express enterprises in China[D]. Changchun: Jilin University,2016. (in Chinese ZHAO Yufei. Research on optimization of air cargo loading express enterprises in China[D]. Changchun: Jilin University, 2016. (in Chinese)
[15]	谷润平,贾旭颖,赵向领,等. 民航货机装载优化准确建模仿真研究[J]. 计算机仿真,2019,36(3): 20-26. GU Runping,JIA Xuying,ZHAO Xiangling,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 GU Runping, JIA Xuying, ZHAO Xiangling, 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)
[16]	史永胜,王策. 货机主货舱多约束条件下集装器装载优化[J]. 科学技术与工程,2020,20(25): 10517-10522. SHI Yongsheng,WANG Ce. Container loading optimization under multiple constraints of cargo aircraft main cargo compartment[J]. Science Technology and Engineering,2020,20(25): 10517-10522. (in Chinese doi: 10.3969/j.issn.1671-1815.2020.25.058 SHI Yongsheng, WANG Ce. Container loading optimization under multiple constraints of cargo aircraft main cargo compartment[J]. Science Technology and Engineering, 2020, 20(25): 10517-10522. (in Chinese) doi: 10.3969/j.issn.1671-1815.2020.25.058
[17]	赵向领,杜有权. 基于遗传算法的民用航空器配载问题[J]. 中国科技论文,2021,16(8): 849-854. ZHAO Xiangling,DU Youquan. Civil aircraft stowage based on genetic algorithm[J]. China Sciencepaper,2021,16(8): 849-854. (in Chinese ZHAO Xiangling, DU Youquan. Civil aircraft stowage based on genetic algorithm[J]. China Sciencepaper, 2021, 16(8): 849-854. (in Chinese)
[18]	姜昱君,韩锐. 民航客机货舱自动配平优化技术[J]. 计算机系统应用,2022,31(1): 159-167. JIANG Yujun,HAN Rui. Automatic load optimization technology for cargo hold of airliner[J]. Computer Systems & Applications,2022,31(1): 159-167. (in Chinese JIANG Yujun, HAN Rui. Automatic load optimization technology for cargo hold of airliner[J]. Computer Systems & Applications, 2022, 31(1): 159-167. (in Chinese)
[19]	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
[20]	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
[21]	LURKIN V,SCHYNS M. The Airline Container Loading Problem with pickup and delivery[J]. European Journal of Operational Research,2015,244(3): 955-965. doi: 10.1016/j.ejor.2015.02.027
[22]	SON D H,KIM H J. An algorithm for the loading planning of air express cargoes[J]. Journal of Society of Korea Industrial and Systems Engineering,2016,39(3): 56-63. doi: 10.11627/jkise.2016.39.3.056
[23]	WONG E Y C,MO D Y,SO S. Closed-loop digital twin system for air cargo load planning operations[J]. International Journal of Computer Integrated Manufacturing,2021,34(7/8): 801-813.
[24]	赵向领,李云飞,王治宇,等. 基于装卸顺序的中型机多航段协同配载优化[J]. 北京航空航天大学学报,2024,50(4):1147-1161. ZHAO Xiangling,LI Yunfei,WANG Zhiyu,et al. Cooperating loading balance optimization for medium-sized aircraft with multiple flight legs based on loading and unloading sequence[J]. Journal of Beijing University of Aeronautics and Astronautics,2024,50(4):1147-1161. (in Chinese ZHAO Xiangling, LI Yunfei, WANG Zhiyu, et al. Cooperating loading balance optimization for medium-sized aircraft with multiple flight legs based on loading and unloading sequence[J]. Journal of Beijing University of Aeronautics and Astronautics, 2024, 50（4）: 1147-1161. (in Chinese)
[25]	KRICHEN S,DAHMANI N. Solving a load balancing problem with a multi-objective particle swarm optimisation approach: application to aircraft cargo transportation[J]. International Journal of Operational Research,2016,27(1/2): 62-84. doi: 10.1504/IJOR.2016.078455