Optimization model of trunk-regional-general multilevel air transportation network considering hub balance
Article Text (Baidu Translation)
-
摘要: 为推动干支通多层航空运输网络构建和高效运行，考虑轴辐式航线网络的多层级特性以及通用航空与干支运输网络的衔接规则，研究了干支通多层航空运输网络优化方法。以网络运输成本和枢纽建设成本最小、最长运输时间最小、枢纽不平衡利用率最小为目标函数，构建了考虑容量限制的r分配非严格轴辐式网络多目标优化模型；结合多目标优化模型的特点，设计VNS-NSGA-Ⅲ进行求解，引入变邻域搜索算法，设计了6种不同的邻域结构来避免陷入局部最优；选取华北地区的部分机场进行小规模与大规模干支通航线网络建模求解，验证VNS-NSGA-Ⅲ的有效性，并进行了参数灵敏度分析。研究结果表明：相同参数条件下，与其他算法相比，VNS-NSGA-Ⅲ的反向世代距离最小(0.043 78)，证明其获得的Pareto解具有更好的多样性和收敛性；灵敏度分析结果表明普通枢纽数量从2增至8时，成本、时间和不平衡利用率目标分别下降了21.94%、23.20%和50.00%，中心枢纽数量从2增至5时，3个目标分别下降了13.86%、13.08%和33.52%；对于不同的分配策略，多分配模型在成本和时间目标上优于单分配模型，但多分配模型在增强路径灵活性的同时，容易增加关键枢纽负载，造成枢纽利用不均衡；枢纽选址结果、分配策略以及非枢纽连通性显著影响网络的流量分布情况和目标函数值。Abstract: To promote the construction and efficient operation of trunk-regional-general multilevel air transportation network, this paper studied the optimization method for trunk-regional-general multilevel air transportation network by considering the multilevel characteristics of the hub-and-spoke airline network and connection rules between general aviation and the trunk-regional transportation network. With the objective functions of minimizing network transportation costs and hub construction costs, minimizing the longest transportation time, and minimizing the unbalanced utilization degree of hubs, a multi-objective optimization model for capacitated r-allocation non-strict hub-and-spoke network was built. By combining characteristics of the multi-objective optimization model, the VNS-NSGA-Ⅲ was designed for solution, and the variable neighborhood search (VNS) was introduced to design six different neighborhoods to avoid falling into the local optimum. Some airports in North China were selected for small-scale and large-scale trunk-regional-general network modeling and solution to verify the effectiveness of the VNS-NSGA-Ⅲ, with parameter sensitivity analysis performed. Analysis results indicate that in identical parameter conditions, the VNS-NSGA-Ⅲ achieves the smallest inverted generational distance of 0.043 78 compared to other algorithms, demonstrating that its obtained Pareto solutions feature superior diversity and convergence. Sensitivity analysis results show that when the number of normal hubs increases from 2 to 8, the cost, time, and unbalanced utilization degree of hubs decrease by 21.94%, 23.20%, and 50.00% respectively. When the number of central hubs increases from 2 to 5, the three objectives decrease by 13.86%, 13.08%, and 33.52% respectively. Regarding different allocation strategies, the multiple-allocation model outperforms the single-allocation model in terms of both cost and time objectives. However, while enhancing route flexibility, the multiple-allocation model is prone to increase traffic load on critical hubs, causing an imbalance in hub utilization. Hub location results, allocation strategies and non-hub connectivity significantly influence network flow distribution and objective function values.
-
图 1 干支通多层航空运输网络结构
Figure 1. Trunk-regional-general multilevel air transportation network structure
图 4 小算例Pareto最优解集的比较结果
Figure 4. Comparison of Pareto optimal solution sets for small cases
表 1 机场列表
Table 1. List of airports
编号 机场名称 编号 机场名称 编号 机场名称 1 北京首都国际机场 11 乌兰察布集宁机场 21 大同南六庄机场 2 天津滨海国际机场 12 鄂尔多斯伊金霍洛机场 22 围场御道口机场 3 石家庄正定国际机场 13 长治王村机场 23 石家庄栾城机场 4 太原武宿国际机场 14 吕梁大武机场 24 河北沧州中捷通用机场 5 呼和浩特白塔国际机场 15 临汾乔李机场 25 河北平泉机场 6 唐山三女河机场 16 秦皇岛北戴河国际机场 26 阿鲁科尔沁机场 7 承德普宁机场 17 朔州滋润机场 27 包头五当召机场 8 邯郸机场 18 北京密云穆家峪通用机场 28 镶黄旗新宝拉格机场 9 张家口宁远机场 19 北京八达岭机场 29 达茂百灵庙机场 10 赤峰玉龙机场 20 天津塘沽机场 30 巴林右旗大板机场 
下载: 导出CSV
表 2 枢纽旅客吞吐量及目标函数值对比
Table 2. Comparison of hub passenger throughput and the value of objectives
枢纽类型和目标函数 案例1 案例2 案例3 机场 旅客吞吐量/人次 机场 旅客吞吐量/人次 机场 旅客吞吐量/人次 中心枢纽 2 8 151 588 2 7 275 004 3 5 625 518 3 7 055 523 3 6 244 990 4 3 026 460 普通枢纽 4 4 566 877 4 4 181 948 2 6 838 149 5 3 365 569 5 4 345 086 9 2 071 250 6 3 685 375 6 3 176 190 10 2 522 094 10 2 061 837 7 4 008 982 11 4 113 043 成本/106元 14 999.47 15 448.71 15 342.59 时间/min 161.23 145.28 132.70 不平衡利用率 0.141 86 0.092 39 0.306 53
下载: 导出CSV
表 3 中心枢纽指标变化
Table 3. Changes of indicators of central hub
中心枢纽候选机场 被选为中心枢纽的次数 被选为中心枢纽的概率/% 新增机场前 新增机场后 新增机场前 新增机场后 北京首都国际机场 53 97 40.46 70.80 天津滨海国际机场 58 31 44.27 22.63 石家庄正定国际机场 51 77 38.93 56.20 太原武宿国际机场 40 38 30.53 27.73 呼和浩特白塔国际机场 60 31 45.80 22.63
下载: 导出CSV
表 4 不同枢纽数量下的目标函数平均值
Table 4. Average objective functions value for different number of hubs
PC PR 成本/106元 时间/min 不平衡利用率 2 2 17 519.68 177.28 0.160 44 2 4 15 396.23 143.23 0.133 82 2 6 14 286.27 141.75 0.091 24 2 8 13 675.55 136.16 0.080 22 2 3 16 624.39 164.19 0.155 74 3 3 15 712.78 155.43 0.145 77 4 3 14 810.50 152.46 0.143 91 5 3 14 319.55 142.71 0.103 54
下载: 导出CSV
表 5 不同分配策略对目标函数值的影响
Table 5. Effect of different allocation strategies on objective functions
算例 r PC PR 成本平均值 时间平均值 不平衡利用率平均值 数值/106元 与单分配(r=1)相比降低比例/% 数值/min 与单分配(r=1)相比降低比例/% 数值 与单分配(r=1)相比降低比例/% 1 1 2 2 18 660.69 191.79 0.113 73 2 2 2 2 17 519.68 6.11 177.28 7.57 0.160 44 -41.07 3 1 2 4 15 949.51 151.87 0.141 13 4 2 2 4 15 396.23 3.47 143.23 5.69 0.133 82 5.18 5 1 3 2 17 096.60 178.84 0.124 88 6 2 3 2 16 687.96 2.39 176.97 1.05 0.129 29 -3.53 7 3 3 2 16 124.86 5.68 154.08 13.84 0.156 87 -25.62 8 1 3 4 15 460.49 158.96 0.155 66 9 2 3 4 14 787.44 4.35 151.14 4.92 0.139 92 10.11 10 3 3 4 14 769.45 4.47 144.55 9.07 0.13 809 11.29
下载: 导出CSV
表 6 不同非枢纽直连概率对网络指标的影响
Table 6. Effect of different non-hub direct connection probabilities on network indicators
非枢纽直连的概率 成本 时间 不平衡利用率 中心枢纽吞吐量 普通枢纽吞吐量 数值/106元 与直连概率为0时相比降低比例/% 数值/min 与直连概率为0时相比降低比例/% 数值 与直连概率为0时相比降低比例/% 数值/人次 与直连概率为0时相比降低比例/% 数值/人次 与直连概率为0时相比降低比例/% 0.0 15 396.23 143.23 0.133 82 5 326 747 3 895 495 0.1 14 369.68 6.67 139.65 2.50 0.113 97 14.83 4 882 851 8.33 3 507 220 9.97 0.2 15 232.43 1.14 137.41 4.17 0.102 34 27.62 4 439 856 16.65 3 116 396 22.21 0.3 16 981.51 -10.41 132.87 7.54 0.118 98 14.50 3 996 050 24.98 2 726 847 37.50
下载: 导出CSV
-
[1] GHODRATNAMA A, ARBABI H R, AZARON A. A bi-objective hub location-allocation model considering congestion[J]. Operational Research, 2020, 20: 2427-2466. doi: 10.1007/s12351-018-0404-3 [2] YANG Y H, LU X C. Bi-objective hub location-allocation problem with time window constraint[M]. Singapore: Springer Nature Singapore, 2024. [3] BASHIRI M, REZANEZHAD M. A reliable multi-objective p-hub covering location problem considering of hubs capabilities[J]. International Journal of Engineering, 2015, 28(5): 717-729. [4] ESKENAZI A G, JOSHI A P, BUTLER L G, et al. Equitable optimization of US airline route networks[J]. Computers, Environment and Urban Systems, 2023, 102: 101973. doi: 10.1016/j.compenvurbsys.2023.101973 [5] ZHALECHIAN M, TAVAKKOLI-MOGHADDAM R, RAHIMI Y. A self-adaptive evolutionary algorithm for a fuzzy multi-objective hub location problem: An integration of responsiveness and social responsibility[J]. Engineering Applications of Artificial Intelligence, 2017, 62: 1-16. doi: 10.1016/j.engappai.2017.03.006 [6] CHOBAR A P, ADIBI M A, KAZEMI A. A novel multi-objective model for hub location problem considering dynamic demand and environmental issues[J]. Journal of Industrial Engineering and Management Studies, 2021, 8(1): 1-31. [7] CHOBAR A P, ADIBI M A, KAZEMI A. Multi-objective hub-spoke network design of perishable tourism products using combination machine learning and meta-heuristic algorithms[J]. Environment, Development and Sustainability, 2025, 27(10): 23237-23264. [8] 李慧芳, 胡大伟, 陈希琼, 等. 考虑碳排放的混合轴辐式多式联运网络枢纽扩增选址-路径问题[J]. 交通运输工程学报, 2022, 22(4): 306-321. doi: 10.19818/j.cnki.1671-1637.2022.04.024LI Hui-fang, HU Da-wei, CHEN Xi-qiong, et al. Expanding hub location-routing problem for hybrid hub-and-spoke multimodal transport network considering carbon emissions[J]. Journal of Traffic and Transportation Engineering, 2022, 22(4): 306-321. doi: 10.19818/j.cnki.1671-1637.2022.04.024 [9] CHOU Y H. The hierarchical-hub model for airline networks[J]. Transportation Planning and Technology, 1990, 14(4): 243-258. doi: 10.1080/03081069008717429 [10] ŞAHIN G, SÜRAL H. A review of hierarchical facility location models[J]. Computers & Operations Research, 2007, 34(8): 2310-2331. [11] 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(S): 1-22. [12] 林建新, 林孟婷, 王皖东, 等. 分级设施选址问题研究进展与展望[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. [13] DUKKANCI O, KARA B Y. Routing and scheduling decisions in the hierarchical hub location problem[J]. Computers & Operations Research, 2017, 85: 45-57. [14] HUANG D, LIU Z Y, FU X, et al. Multimodal transit network design in a hub-and-spoke network framework[J]. Transportmetrica A: Transport Science, 2018, 14(8): 706-735. doi: 10.1080/23249935.2018.1428234 [15] KHODEMANI-YAZDI M, TAVAKKOLI-MOGHADDAM R, BASHIRI M, et al. Solving a new bi-objective hierarchical hub location problem with an M/M/c queuing framework[J]. Engineering Applications of Artificial Intelligence, 2019, 78: 53-70. doi: 10.1016/j.engappai.2018.10.004 [16] SHANG X T, YANG K, JIA B, et al. Heuristic algorithms for the bi-objective hierarchical multimodal hub location problem in cargo delivery systems[J]. Applied Mathematical Modelling, 2021, 91: 412-437. doi: 10.1016/j.apm.2020.09.057 [17] BORHANI M, AKBARI K, MATKAN A, et al. A multicriteria optimization for flight route networks in large-scale airlines using intelligent spatial information[J]. International Journal of Interactive Multimedia and Artificial Intelligence, 2020, 6(1): 123-131. doi: 10.9781/ijimai.2019.11.001 [18] 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 [19] 马昌喜, 石褚巍, 杜波. 轴辐式应急救援网络规划[J]. 交通运输工程学报, 2023, 23(3): 198-208. doi: 10.19818/j.cnki.1671-1637.2023.03.015MA 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 [20] YAMAN H. The hierarchical hub median problem with single assignment[J]. Transportation Research Part B: Methodological, 2009, 43(6): 643-658. doi: 10.1016/j.trb.2009.01.005 [21] ALUMUR S A, KARA B Y, KARASAN O E. Multimodal hub location and hub network design[J]. Omega, 2012, 40(6): 927-939. doi: 10.1016/j.omega.2012.02.005 [22] ZHANG C X, SUN X Q, DAI W B, et al. Solving hub location problems with profits using variable neighborhood search[J]. Journal of the Transportation Research Board, 2023, 2677(1): 1675-1695. doi: 10.1177/03611981221105501 [23] MRABTI N, HAMANI N, BOULAKSIL Y, et al. A multi-objective optimization model for the problems of sustainable collaborative hub location and cost sharing[J]. Transportation Research Part E: Logistics and Transportation Review, 2022, 164: 102821. doi: 10.1016/j.tre.2022.102821 [24] ZHENG H K, SUN H J, ZHU S R, et al. Air cargo network planning and scheduling problem with minimum stay time: A matrix-based ALNS heuristic[J]. Transportation Research Part C: Emerging Technologies, 2023, 156: 104307. doi: 10.1016/j.trc.2023.104307 [25] HU Q M, HU S L, WANG J, et al. Stochastic single allocation hub location problems with balanced utilization of hub capacities[J]. Transportation Research Part B: Methodological, 2021, 153: 204-227. doi: 10.1016/j.trb.2021.09.009 [26] 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 [27] 姜雨, 刘振宇, 胡志韬, 等. 大型机场进场航空器联合调度模型[J]. 交通运输工程学报, 2022, 22(1): 205-215. doi: 10.19818/j.cnki.1671-1637.2022.01.017JIANG Yu, LIU Zhen-yu, HU Zhi-tao, et al. Coordinated scheduling model of arriving aircraft at large airport[J]. Journal of Traffic and Transportation Engineering, 2022, 22(1): 205-215. doi: 10.19818/j.cnki.1671-1637.2022.01.017 [28] ZHANG Q F, LI H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731. doi: 10.1109/TEVC.2007.892759 [29] ZHANG Q F, ZHOU A M, JIN Y C, et al. RM-MEDA: A regularity model-based multiobjective estimation of distribution algorithm[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(1): 41-63. doi: 10.1109/TEVC.2007.894202 [30] GHEZAVATI V, HOSSEINIFAR P. Application of efficient metaheuristics to solve a new bi-objective optimization model for hub facility location problem considering value at risk criterion[J]. Soft Computing, 2018, 22(1): 195-212. doi: 10.1007/s00500-016-2326-4 -
图(9) / 表(6)
计量
- 文章访问数: 119
- HTML全文浏览量: 73
- PDF下载量: 18
- 被引次数: 0
