考虑分层需求的干支通多层航空运输网络优化模型

姜雨; 刘洪阳; 李焓璐; 原野; 薛清文

doi:10.19818/j.cnki.1671-1637.2026.147

考虑分层需求的干支通多层航空运输网络优化模型

doi: 10.19818/j.cnki.1671-1637.2026.147

1.
南京航空航天大学民航学院，江苏南京 211106
2.
南京航空航天大学通用航空与飞行学院，江苏常州 213300

基金项目:

国家自然科学基金项目 52372298

国家自然科学基金项目 52302517

详细信息

作者简介:
姜雨(1975-)，女，山东烟台人，教授，工学博士，E-mail: jiangyu07@nuaa.edu.cn

中图分类号: U8
计量
- 文章访问数: 41
- HTML全文浏览量: 19
- PDF下载量: 13
- 被引次数: 0
出版历程
- 收稿日期: 2025-07-31
- 录用日期: 2026-01-15
- 修回日期: 2025-12-11
- 刊出日期: 2026-02-28

Optimization model for trunk-regional-general hierarchical air transportation network with stratified demand

1.
College of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, Jiangsu, China
2.
College of General Aviation and Flight, Nanjing University of Aeronautics and Astronautics, Changzhou 213300, Jiangsu, China

Funds:

National Natural Science Foundation of China 52372298

National Natural Science Foundation of China 52302517

More Information

Corresponding author: JIANG Yu, professor, PhD, jiangyu07@nuaa.edu.cn

Article Text (Baidu Translation)

摘要

摘要: 以干支通多层航空运输网络为研究对象，进行符合其运行的建模，以构建分层需求多层级枢纽选址模型并求解为目标；通过需求层区分不同类别的需求，以包括运输成本、枢纽建设固定成本、航线连接固定成本在内的总成本最小为目标，构建了允许非枢纽直接连接和普通枢纽直接连接的r分配多层级枢纽选址模型；根据航空网络的拓扑结构特点，结合变邻域搜索(VNS)算法和遗传算法(GA)的优势，设计了基于交替机制的VNS-GA混合启发式算法，通过变邻域搜索优化枢纽选择和需求点分配，利用遗传算法优化直接连接关系；针对CAB、AP两个经典数据集和中国长三角区域机场数据进行建模求解，对比现有模型和分层需求模型，验证了算法有效性，并分析了参数灵敏度。研究结果表明：在15个点的小规模案例中，分层需求模型降低了9.23%的总成本；在25个点的小规模案例中，交替式VNS-GA算法在多种参数配置下与最优解差距均不超过2.56%，且平均求解时间仅为商业求解软件的10.78%；在100个点的中大规模案例中，灵敏度分析表明，分层权重系数的设置对优化结果影响最大，r分配策略能够降低总成本但存在明显的边际效益递减；在长三角区域半实例试验中，模型能够在增加50条直连航线的同时实现成本降低2.75%，验证了模型在干支通多层航空运输网络优化的可行性和效果。
- 航空运输 /
- 干支通多层航空运输网络 /
- 分层需求 /
- 多层级枢纽选址模型 /
- 交替式VNS-GA混合启发式算法 /
- 基于成本的网络优化 /
- 多规模试验 /
- 长三角区域
Abstract: The trunk-regional-general hierarchical air transportation network was taken as the research object, and modeling consistent with its operational characteristics was conducted to construct and solve a hierarchical hub location model with stratified demand. The demand layer was employed to distinguish various demands. To minimize the total cost, including transportation costs, hub construction fixed costs, and fixed costs for establishing flight connections, an r-allocation hierarchical hub location model permitting non-hub direct connections and regular hub direct connections was built. According to the topological characteristics of air transportation networks, a VNS-GA hybrid heuristic algorithm based on an alternating mechanism was designed by combining the advantages of the VNS algorithm and the genetic algorithm (GA). Hub selection and demand node allocation were optimized by VNS, while direct connections were optimized by GA. The modeling and solution were carried out for the two classical datasets, namely, Civil Aeronautics Board (CAB) and Australia Post (AP), as well as the Yangtze River Delta regional airport data in China. The existing model and the stratified demand model were compared to verify the effectiveness of the algorithm and analyze the parameter sensitivity. According to the research results, in the small-scale case of 15 nodes, the stratified demand model reduces the total cost by 9.23%. In the small-scale case of 25 nodes, the alternating VNS-GA algorithm has a gap with the optimum solution of no more than 2.56% under various parameter configurations, with the average solution time only 10.78% of that of the commercial solver. In the medium and large-scale case of 100 nodes, sensitivity analysis shows that the setting of stratified weight coefficients has a great impact on the optimization results. The r-allocation strategy can reduce the total cost but with obvious diminishing marginal benefits. In the semi-empirical experiment of the Yangtze River Delta region, the model can reduce the cost by 2.75% while adding 50 direct connections. This verifies the feasibility and effectiveness of the model in optimizing trunk-regional-general hierarchical air transportation networks.

HTML全文

图 1 干支通多层航空运输网络

Figure 1. Trunk-regional-general hierarchical air transportation network

下载: 全尺寸图片幻灯片

图 2 交替式VNS-GA流程

Figure 2. Flow of alternating VNS-GA

下载: 全尺寸图片幻灯片

图 3 染色体结构

Figure 3. Chromosome structures

下载: 全尺寸图片幻灯片

图 4 15个点的网络结构对比

Figure 4. Comparison of 15-node network topologies

下载: 全尺寸图片幻灯片

图 5 CAB15成本分解

Figure 5. Cost decomposition of CAB15

下载: 全尺寸图片幻灯片

图 6 二十五个点网络优化结果

Figure 6. Optimization results in 25-node networks

下载: 全尺寸图片幻灯片

图 7 CAB25成本分解

Figure 7. Cost decomposition of CAB25

下载: 全尺寸图片幻灯片

图 8 多算法随时间演化的最优轨迹曲线对比

Figure 8. Comparison of anytime best-found curves of multiple algorithms

下载: 全尺寸图片幻灯片

图 9 中大规模网络优化结果

Figure 9. Optimization result in medium-to-large-scale network

下载: 全尺寸图片幻灯片

图 10 普通枢纽最大分配数对总成本的影响

Figure 10. Effect of maximum allocation number for regular hubs on total cost

下载: 全尺寸图片幻灯片

图 11 枢纽数量对总成本的影响

Figure 11. Effect of hub number on total cost

下载: 全尺寸图片幻灯片

图 12 多场景长三角区域网络优化结果

Figure 12. Optimization results of the Yangtze River Delta regional network under multiple scenarios

下载: 全尺寸图片幻灯片

表 1 算法超参数

Table 1. Algorithm hyperparameters

组件	参数	默认值	区间	说明
数据构建	随机种子	42	固定	用于分层需求对的矩阵生成
外层算法	交替次数	5	[5, 10]	算法外层停止准则
外层算法	最大时间/s	500	[500, 1 000]	算法外层停止准则
VNS	最大代数	50	[30, 200]	最大迭代次数
VNS	邻域族	N1~N6	固定	分别对应非枢纽重分配、枢纽互换等
GA	种群规模	50	[50, 120]	迭代效率与解质量平衡
GA	最大代数	10	[10, 50]	收敛控制
GA	交叉率	1.0	[0.7, 1.0]	常规设定
GA	变异率	0.1	[0.05, 0.20]	常规设定

下载: 导出CSV

表 2 不同模型的总成本对比

Table 2. Comparison of total cost performances across optimization models

模型	{λ₁, λ₂, λ₃}	总成本
分层需求模型	{0.6, 0.3, 0.1}	2 110 179 029.67
单独考虑经济舱	{0.6, 0.0, 0.0}	1 568 129 660.54
单独考虑商务舱	{0.0, 0.3, 0.0}	536 224 445.89
单独考虑头等舱	{0.0, 0.0, 0.1}	233 098 455.07

下载: 导出CSV

表 3 算法性能对比

Table 3. Comparison of algorithm performances

n	n₁	n₂	r	平均时间/s				平均差值百分比/%
n	n₁	n₂	r	Gurobi	VNS-GA	GA	VNS	Gurobi	VNS-GA	GA	VNS
15	5	1	1	4.80	5.63	7.48	8.02	0	0.19	1.75	2.93
	5	2	1	7.40	5.59	8.20	7.88	0	0.28	1.75	0.77
	5	2	2	6.73	6.32	8.52	7.62	0	0.23	2.40	0.72
	7	3	1	3.43	5.88	9.91	8.81	0	0.22	0.29	0.65
	7	3	2	4.73	6.05	8.20	8.64	0	0.62	1.28	0.70
	7	3	3	5.40	12.96	8.23	8.99	0	0.40	2.50	1.06
20	5	1	1	20.99	24.55	13.65	21.84	0	3.62	0.65	4.99
	5	2	1	15.23	20.91	19.31	26.78	0	2.41	7.00	6.43
	5	2	2	16.53	16.91	14.11	23.68	0	1.49	7.25	5.48
	7	3	1	10.52	18.94	13.74	33.27	0	1.37	3.90	3.37
	7	3	2	10.54	17.97	14.43	33.32	0	1.47	5.20	3.86
	7	3	3	11.28	16.89	14.31	33.60	0	1.80	4.40	3.87
25	5	1	1	311.60	34.00	47.03	94.06	0	2.30	3.26	4.21
	5	2	1	337.99	34.51	44.10	102.77	0	2.69	2.82	2.50
	5	2	2	254.58	37.40	56.58	100.02	0	2.45	3.58	7.12
	7	3	1	361.51	35.09	80.11	116.86	0	1.13	1.41	4.77
	7	3	2	407.77	38.64	85.56	97.88	0	0.50	0.82	3.29
	7	3	3	395.99	43.47	61.53	101.06	0	0.55	1.18	2.48

下载: 导出CSV

表 4 参数灵敏度分析结果

Table 4. Sensitive analysis result of parameters

参数	标定依据	默认值	灵敏度分析取值	目标值	运输成本	固定成本	中心枢纽编号	普通枢纽编号
默认配置				1 255 829.93	1 206 173.53	49 656.41	19, 42	20, 35, 59
α₁	票价比例运输效率	0.6	0.5	1 233 068.23	1 183 082.22	49 986.01	19, 42	20, 35, 66
α₁		0.6	0.7	1 267 246.60	1 222 046.80	45 199.79	35, 42	27, 39, 59
α₂		0.8	0.7	1 213 952.24	1 169 280.04	44 672.20	35, 42	27, 39, 66
α₂		0.8	0.9	1 289 006.41	1 260 029.34	28 977.06	19, 42	20, 35, 66
β₁	参考文献开辟成本	3.0	2.0	1 259 874.22	1 208 388.08	51 486.14	19, 42	20, 35, 59
β₁		3.0	4.0	1 253 317.44	1 200 960.75	52 356.68	19, 42	20, 35, 59
β₂		2.0	1.0	1 248 200.52	1 199 614.24	48 586.28	19, 42	20, 35, 66
β₂		2.0	1.5	1 254 287.29	1 205 987.97	48 299.32	19, 42	20, 35, 59
δ	中心枢纽规模差异	5.0	2.5	1 246 269.92	1 203 373.07	42 896.85	19, 42	20, 35, 59
δ	中心枢纽规模差异	5.0	10.0	1 264 591.94	1 199 781.43	64 810.51	19, 42	20, 35, 66
F₀	量纲对齐	1 000	2 000	1 267 569.29	1 200 780.75	66 788.54	19, 42	20, 35, 59
F₀		1 000	3 000	1 283 456.31	1 201 111.35	82 344.96	19, 42	20, 35, 59
G₀		0.1	0.2	1 271 627.96	1 230 470.24	41 157.72	19, 42	20, 35, 59
G₀		0.1	0.3	1 281 242.28	1 229 485.53	51 756.75	27, 42	35, 39, 66
λ_s	分层假设	{0.6, 0.3, 0.1}	{0.34, 0.33, 0.33}	1 009 764.85	980 841.52	28 923.32	19, 42	20, 35, 66
λ_s	分层假设	{0.6, 0.3, 0.1}	{0.1, 0.3, 0.6}	776 647.90	747 175.58	29 472.32	27, 42	20, 35, 59

下载: 导出CSV

参考文献(31)

[1]	ALBAREDA-SAMBOLA M, MARTINEZ-MERINO L I, RODRIGUEZ-CHIA A M. The stratified p-center problem[J]. Computers and Operations Research, 2019, 108: 213-225. doi: 10.1016/j.cor.2019.04.013
[2]	GHAFFARINASAB N, KARA B Y, CAMPBELL J F. The stratified p-hub center and p-hub maximal covering problems[J]. Transportation Research Part B: Methodological, 2022, 157: 120-148. doi: 10.1016/j.trb.2022.01.002
[3]	WANG S, WANDELT S, SUN X Q. Stratified p-hub median and hub location problems: Models and solution algorithms[J]. IEEE Transactions on Intelligent Transportation Systems, 2024, 25(9): 11452-11470. doi: 10.1109/TITS.2024.3415658
[4]	O'KELLY M E. A quadratic integer program for the location of interacting hub facilities[J]. European Journal of Operational Research, 1987, 32(3): 393-404. doi: 10.1016/S0377-2217(87)80007-3
[5]	CAMPBELL J F. Integer programming formulations of discrete hub location problems[J]. European Journal of Operational Research, 1994, 72(2): 387-405. doi: 10.1016/0377-2217(94)90318-2
[6]	O'KELLY M, SUN X Q, WANDELT S. Hub location problems: A meta review and ten disruptive research challenges[J]. Journal of the Air Transport Research Society, 2025, 4: 100073. doi: 10.1016/j.jatrs.2025.100073
[7]	CHOU Y H. The hierarchical-hub model for airline networks[J]. Transportation Planning and Technology, 1990, 14(4): 243-258. doi: 10.1080/03081069008717429
[8]	TORKESTANI S S, SEYEDHOSSEINI S M, MAKUI A, et al. Hierarchical facility location and hub network problems: A literature review[J]. Journal of Industrial and Systems Engineering, 2016, 9: 1-22.
[9]	林建新, 林孟婷, 王皖东, 等. 分级设施选址问题研究进展与展望[J]. 清华大学学报(自然科学版), 2022, 62(7): 1121-1131. LIN Jian-xin, LIN Meng-ting, WANG Wan-dong, et al. Review of the hierarchical facility location problem[J]. Journal of Tsinghua University (Science and Technology), 2022, 62(7): 1121-1131.
[10]	商晓婷. 多层级多模式交通枢纽选址优化方法及应用[D]. 北京: 北京交通大学, 2021. SHANG Xiao-ting. Optimization methods and applications of multilevel multimodal transportation hub location[D]. Beijing: Beijing Jiaotong University, 2021.
[11]	SHANG X T, YANG K, LUO Q, et al. Robust optimization models for the hierarchical cost-minimizing hub covering problem in the urban agglomeration comprehensive transport system[J]. International Journal of General Systems, 2025: 1-35.
[12]	马昌喜, 石褚巍, 杜波. 轴辐式应急救援网络规划[J]. 交通运输工程学报, 2023, 23(3): 198-208. doi: 10.19818/j.cnki.1671-1637.2023.03.015 MA Chang-xi, SHI Chu-wei, DU Bo. Hub-and-spoke emergency rescue network planning[J]. Journal of Traffic and Transportation Engineering, 2023, 23(3): 198-208. doi: 10.19818/j.cnki.1671-1637.2023.03.015
[13]	WANG M, CHENG Q, HUANG J C, et al. Research on optimal hub location of agricultural product transportation network based on hierarchical hub-and-spoke network model[J]. Physica A: Statistical Mechanics and Its Applications, 2021, 566: 125412. doi: 10.1016/j.physa.2020.125412
[14]	SHANG X T, YANG K, WANG W Q, et al. Stochastic hierarchical multimodal hub location problem for cargo delivery systems: Formulation and algorithm[J]. IEEE Access, 2020, 8: 55076-55090. doi: 10.1109/ACCESS.2020.2981669
[15]	吴迪, 石帅杰, 张雅婷, 等. 不确定需求下基于云仓储的物流网络节点选择[J]. 交通运输工程学报, 2025, 25(2): 189-203. doi: 10.19818/j.cnki.1671-1637.2025.02.012 WU Di, SHI Shuai-jie, ZHANG Ya-ting, et al. Selection of logistics network nodes based on cloud warehousing under uncertain demand[J]. Journal of Traffic and Transportation Engineering, 2025, 25(2): 189-203. doi: 10.19818/j.cnki.1671-1637.2025.02.012
[16]	吴迪, 朱玉玺, 武文龙, 等. 基于远海岛屿的海上常态巡航救助系统选址-路径优化[J]. 交通运输工程学报, 2025, 25(6): 200-218. doi: 10.19818/j.cnki.1671-1637.2025.06.017 WU Di, ZHU Yu-xi, WU Wen-long, et al. Location-routing optimization for regular maritime cruise and emergency rescue system in remote islands[J]. Journal of Traffic and Transportation Engineering, 2025, 25(6): 200-218. doi: 10.19818/j.cnki.1671-1637.2025.06.017
[17]	姜雨, 林操, 龙颖, 等. 考虑枢纽平衡的干支通多层航空运输网络优化模型[J]. 交通运输工程学报, 2025, 25(6): 186-199. doi: 10.19818/j.cnki.1671-1637.2025.06.016 JIANG Yu, LIN Cao, LONG Ying, et al. Optimization model of trunk-regional-general multilevel air transportation network considering hub balance[J]. Journal of Traffic and Transportation Engineering, 2025, 25(6): 186-199. doi: 10.19818/j.cnki.1671-1637.2025.06.016
[18]	TIKANI H, HONARVAR M, MEHRJERDI Y Z. Developing an integrated hub location and revenue management model considering multi-classes of customers in the airline industry[J]. Computational and Applied Mathematics, 2018, 37(3): 3334-3364. doi: 10.1007/s40314-017-0512-3
[19]	TIKANI H, HONARVAR M, MEHRJERDI Y Z. Two-stage stochastic programming model for capacitated complete star p-hub network with different fare classes of customers[J]. Journal of Industrial and Systems Engineering, 2018, 11(1): 74-96.
[20]	TAHERKHANI G, ALUMUR S A, HOSSEINI M. Benders decomposition for the profit maximizing capacitated hub location problem with multiple demand classes[J]. Transportation Science, 2020, 54(6): 1446-1470. doi: 10.1287/trsc.2020.1003
[21]	JAYASWAL S, VIDYARTHI N. Multiple allocation hub location with service level constraints for two shipment classes[J]. European Journal of Operational Research, 2023, 309(2): 634-655. doi: 10.1016/j.ejor.2023.01.066
[22]	LI Z C, BING X, FU X W. A hierarchical hub location model for the integrated design of urban and rural logistics networks under demand uncertainty[J]. Annals of Operations Research, 2025, 348(2): 1087-1108. doi: 10.1007/s10479-023-05189-6
[23]	KARIMI H. The capacitated hub covering location-routing problem for simultaneous pickup and delivery systems[J]. Computers & Industrial Engineering, 2018, 116: 47-58.
[24]	KRATICA J, MILANOVIC M, STANIMIROVIC Z, et al. An evolutionary-based approach for solving a capacitated hub location problem[J]. Applied Soft Computing, 2011, 11: 1858-1866. doi: 10.1016/j.asoc.2010.05.035
[25]	AZIZI N, CHAUHAN S, SALHI S, et al. The impact of hub failure in hub-and-spoke networks: Mathematical formulations and solution techniques[J]. Computers & Operations Research, 2016, 65: 174-188.
[26]	DAI W B, ZHANG J, SUN X Q, et al. HUBBI: Iterative network design for incomplete hub location problems[J]. Computers & Operations Research, 2019, 104: 394-414.
[27]	BRIMBERG J, MLADENOVIĆ N, TODOSIJEVIĆ R, et al. General variable neighborhood search for the uncapacitated single allocation p-hub center problem[J]. Optimization Letters, 2017, 11(2): 377-388. doi: 10.1007/s11590-016-1004-x
[28]	ERNST A T, KRISHNAMOORTHY M. Efficient algorithms for the uncapacitated single allocation p-hub median problem[J]. Location Science, 1996, 4(3): 139-154. doi: 10.1016/S0966-8349(96)00011-3
[29]	EBERY J, KRISHNAMOORTHY M, ERNST A, et al. The capacitated multiple allocation hub location problem: Formulations and algorithms[J]. European Journal of Operational Research, 2000, 120(3): 614-631. doi: 10.1016/S0377-2217(98)00395-6
[30]	WU Y H, QURESHI A G, YAMADA T. Adaptive large neighborhood decomposition search algorithm for multi-allocation hub location routing problem[J]. European Journal of Operational Research, 2022, 302(3): 1113-1127. doi: 10.1016/j.ejor.2022.02.002
[31]	LAGUNA M, MARTÍ R, MARTÍNEZ-GAVARA A, et al. Greedy randomized adaptive search procedures with path relinking. An analytical review of designs and implementations[J]. European Journal of Operational Research, 2025, 327(3): 717-734. doi: 10.1016/j.ejor.2025.02.022