面向拥堵问题的枢纽航线网络优化模型

doi:10.3969/j.issn.1001-506X.2020.11.18

系统工程与电子技术 ›› 2020, Vol. 42 ›› Issue (11): 2553-2559.doi: 10.3969/j.issn.1001-506X.2020.11.18

面向拥堵问题的枢纽航线网络优化模型

徐涛^1,^2,³(), 吴志帅^1,²(), 卢敏^1,^2,³(), 吕宗磊^1,^2,³(), 李忠虎³()

1. 中国民航大学计算机科学与技术学院, 天津 300300
2. 中国民航大学民航信息技术科研基地, 天津 300300
3. 民航旅客服务智能化应用技术重点实验室, 北京 101318

收稿日期:2020-02-17 出版日期:2020-11-01 发布日期:2020-11-05
作者简介:徐涛(1962-),通信作者,男,教授,博士研究生导师,硕士,主要研究方向为民航信息系统理论与安全、智能信息处理。E-mail:txu@cauc.edu.cn|吴志帅(1993-),男,硕士,主要研究方向为民航智能信息处理。E-mail:wu_zhishuai@163.com|卢敏(1985-),男,副研究员,硕士研究生导师,博士,主要研究方向为民航智能信息处理。E-mail:lumin@mail.nankai.edu.cn|吕宗磊(1981-),男,副教授,硕士研究生导师,博士,主要研究方向为机器学习与知识工程、最优化理论与方法。E-mail:zllv@cauc.edu.cn|李忠虎(1984-),男,高级工程师，硕士,主要研究方向为民航市场研究。E-mail:lzhh@travelsky.com
基金资助:
国家自然科学基金项目(61502499);天津市自然科学基金(18JCYBJC85100);教育部人文社会科学研究规划基金项目(19YJA630046)

Optimization model of hub-and-spoke network for congestion problem

Tao XU^1,^2,³(), Zhishuai WU^1,²(), Min LU^1,^2,³(), Zonglei LYU^1,^2,³(), Zhonghu LI³()

1. College of Computer Science and Technology, Civil Aviation University of China, Tianjin 300300, China
2. Civil Aviation Information Technology Research Base, Civil Aviation University of China, Tianjin 300300, China
3. Key Laboratory of Intelligent Application Technology for Civil Aviation Passenger Service, Beijing 101318, China

Received:2020-02-17 Online:2020-11-01 Published:2020-11-05

摘要/Abstract

摘要：

为解决枢纽机场客流拥堵问题,提高机场运行效率,减少运营成本,提出了一种面向拥堵问题的枢纽航线网络优化模型。该模型基于非严格枢纽航线网络结构,以不同运输方式的费用和流量为约束条件,以枢纽航线网络成本最低为目标，设计了能够减少求解运算的复杂变量表示方法,以及减少陷入局部最优解概率的模拟退火粒子群优化(simulated annealing particle swarm optimization, SAPSO)算法。实验结果表明,相较于严格的枢纽航线网络,所提优化模型能够显著地缓解枢纽机场的拥堵,均衡枢纽机场间客流量,减少网络成本;同时,所提算法具有较快的收敛速度和良好的稳定性。

关键词: 航空运输, 枢纽航线网络, 模拟退火粒子群优化算法, 拥堵问题, 直航

Abstract:

In order to solve the problem of passenger flow congestion at the hub airport, improve airport operation efficiency, and reduce operating costs, an optimization model of the hub-and-spoke network for congestion problem is proposed. The model is based on the structure of non-strict hub-and-spoke network, with costs and flows of different modes of transportation as constraints, and the goal of minimizing the hub-and-spoke network costs. A complex variable representation method that can reduce the calculation and the simulated annealing particle swarm optimization (SAPSO) algorithm, which can reduce the probability of falling into a local optimal solution is designed. The experimental results show that compared with the strict hub-and-spoke network, the optimization model proposed can significantly alleviate the congestion of the hub airport, balance passnger flow between hub airports and reduce the network cost. At the same time, the proposed algorithm has faster convergence speed and better stability.

Key words: air transportation, hub-and-spoke network, simulated annealing particle swarm optimization (SAPSO) algorithm, congestion problem, direct flight

中图分类号:

TP301.6

徐涛, 吴志帅, 卢敏, 吕宗磊, 李忠虎. 面向拥堵问题的枢纽航线网络优化模型[J]. 系统工程与电子技术, 2020, 42(11): 2553-2559.

Tao XU, Zhishuai WU, Min LU, Zonglei LYU, Zhonghu LI. Optimization model of hub-and-spoke network for congestion problem[J]. Systems Engineering and Electronics, 2020, 42(11): 2553-2559.

图/表 12

图1

图2

图3

表1

表2

面向拥堵问题的枢纽航线网络优化算法(算法2)"

输入:迭代次数maxiter,初始化矩阵X_n×(n-1)、V_n×(n-1),直航分担率Z_ij,机场节点间的客流量及成本集合,机场的容量阈值集合,可行解范围[X_min, X_max],搜索步长范围[V_min, V_max],模拟退火的起始温度T
输出:航线及流量最优分配方案

步骤 1  粒子初始化位置矩阵X_n×(n-1)、速度矩阵V_n×(n-1)//已知i、j,通过矩阵V_n×(n-1)可知X_{ijk_im_j}
步骤 2  for粒子i, i∈[2, n]{//在位置矩阵X_n×(n-1)第1列中初始化个体和全局最优位置值、并记录最优位置
步骤 3    xa(1)=X_12k₁m₂且xa(i)=X_{i1k_im₁}   //xa(i)记录每行的局部最优值
步骤 4    x_i=[i, j, xa(i)]                                  //记录每行局部最优位置
步骤 5    xb=min(Q(X_{i1k_im₁}), Q(xa(1))}       //初始化个体最优值
步骤 6  ya=X_12k₁m₂                //初始化全局最优位置
步骤 7  y=[1, 2, ya]                   //记录全局最优位置
步骤 8  yb=Q(ya)                  //记录全局最优值
步骤 9  for迭代次数t, t∈[1, maxiter]{
步骤 10    for粒子i, i∈[1, n] {
步骤 11      for粒子j, j∈[1, n-1]{//更新个体和全局最优位置、最优值
步骤 12        if Q(X_{ijk_im_j})＜xb{
步骤 13          then xa(i)=X_{ijk_im_j}且xb=Q(X_{ijk_im_j})且x_i=[i, j, xa(i)]}
步骤 14        if xb＜yb {
步骤 15          then ya=X_{ijk_im_j}且yb=Q(ya)且y=[i, j, ya]且yt(t)=yb}
步骤 16    线性更新惯性权重值ω及粒子位置X′_{ijk_im_j}和速度V′_{ijk_im_j}
步骤 17        if X′_{ijk_im_j}∈[X_min, X_max], V′_{ijk_im_j}∈[V_min, V_max]且exp(-ΔE/T)＜ε, ε∈(0, 1){
        //判断位置和速度是否越界,引入模拟退火机制, ε为(0，1)区间内的随机数
步骤 18          then接受新位置X_{ijk_im_j} = X′_{ijk_im_j}
步骤 19        else if根据算法1重新生成位置X_{ijk_im_j}和速度V_{ijk_im_j}}}}
步骤 20  ym=min(yt(t))}
步骤 21  return ym所对应的xa(i)及x_i//返回全局最优粒子位置X_{ijk_im_j}及第i行个体的所有元素

表2

表3

表4

表5

图4

图5

图6

图7

参考文献 21

1	ELHEDHLI S , HU F X . Hub-and-spoke network design with congestion[J]. Computers & Operations Research, 2005, 32 (6): 1615- 1632.
2	ALUMUR S A , KARA B Y , KARASAN O E . The design of single allocation incomplete hub networks[J]. Transportation Research Part B: Methodological, 2009, 43 (10): 936- 951. doi: 10.1016/j.trb.2009.04.004
3	HU H , CHENG L , XUAN D D , et al. Comprehensive passenger hub layout model of combined selection for capacity limitation and transportation mode[J]. Journal of Traffic and Transportation Engineering, 2012, 12 (4): 59- 66.
4	黄娟, 贺政纲. 基于Logit模型的空铁联运运量预测[J]. 交通运输工程与信息学报, 2018, 16 (4): 92- 96.
	HUANG J , HE Z G . Air-rail combined transportation volume forecast based on Logit model[J]. Journal of Transportation Engineering and Information, 2018, 16 (4): 92- 96.
5	ALUMUR S A , NICKEL S , ROHRBECK B , et al. Modeling congestion and service time in hub location problems[J]. Applied Mathematical Modeling, 2018, 55 (1): 13- 32.
6	AZIZI N , VIDYARTHI N , CHAUHAN S S . Modelling and analysis of hub-and-spoke networks under stochastic demand and congestion[J]. Annals of Operations Research, 2018, 264 (1/2): 1- 40.
7	LIN M H . Airport congestion and capacity when carriers are asymmetric[J]. International Journal of Industrial Organization, 2019, 62 (C): 273- 290.
8	LIN M H , ZHANG Y . Hub-airport congestion pricing and capacity investment[J]. Transportation Research Part B: Methodological, 2017, 101 (C): 89- 106.
9	OZGUNKIBIROGLU C , SERARSLAN M N , TOPCU Y I , et al. Particle swarm optimization for uncapacitated multiple allocation hub location problem under congestion[J]. Expert Systems with Applications, 2019, 119 (1): 1- 19.
10	WU W W , ZHANG H Y , WEI W B . Optimal design of hub-and-spoke networks with access to regional hub airports: a case for the Chinese regional airport system[J]. Transportmetrica A: Transport Science, 2018, 14 (4): 330- 345. doi: 10.1080/23249935.2017.1385658
11	HUANG X L, CHEN Y Y. An optimization model for multimodal transportation decisions based on congestion information[C]//Proc.of the 11th World Congress on Intelligent Control and Automation, 2014: 610-615.
12	HAMID M , MOHAN K , ANDREAS T , et al. A modified benders method for the single-and multiple allocation P-hub median problems[J]. Operations Research Proceedings, 2018, 1 (1): 135- 141.
13	NIRAJ R D , KRISHNAMOORTHY M , ERNST A T . Efficient models, formulations and algorithms for some variants of fixed interval scheduling problems[J]. Data and Decision Sciences in Action, 2018, 8 (4): 43- 69.
14	BAILEY A, ORNBUKI-BERRNAN B, ASOBIELA S. Discrete PSO for the uncapacitated single allocation hub location problem[C]//Proc.of the Symposium on Computational Intelligence in Production and Logistics Systems, 2013: 92-98.
15	WU W W , WANG H . Chaotic particle swarm optimization algorithm for hub and spoke systems with congestion[J]. Open Automation and Control Systems Journal, 2014, 6 (1): 609- 615.
16	ADEHI M , BAROUGHI F , ALIZADEH B . A modified particle swarm optimization algorithm for general inverse ordered Pmedian location problem on network[J]. Facta Universitatis, Series: Mathematics and Informatics, 2017, 32 (4): 447- 468.
17	YAMAN H , KARA B Y , TANSEL B C . The latest arrival hub location problem for cargo delivery systems with stopovers[J]. Transportation Research Part B: Methodological, 2007, 41 (8): 906- 919. doi: 10.1016/j.trb.2007.03.003
18	WANG R , YANG K , YANG L X , et al. Modeling and optimization of a road-rail intermodal transport system under uncertain information[J]. Engineering Applications of Artificial Intelligence, 2018, 72 (1): 423- 436.
19	SEN G , KRISHNAMOORTHY M . Discrete particle swarm optimization algorithms for two variants of the static data segment location problem[J]. Applied Intelligence, 2018, 48 (3): 771- 790. doi: 10.1007/s10489-017-0995-z
20	李长隆, 钮可. 马尔科夫链蒙特卡罗方法浅析[J]. 黑龙江科技信息, 2016, 17 (26): 48- 52.
	LI C L , NU K . Analysis of Markov chain Monte Carlo method[J]. Heilongjiang Science and Technology Information, 2016, 17 (26): 48- 52.
21	ALKAABNEHA F , DIABATBC A , ELHEDHLID S . A Lagrangian heuristic and GRASP for the hub-and-spoke network system with economies-of-scale and congestion[J]. Transportation Research Part C: Emerging Technologies, 2019, 102 (5): 249- 273.

枢纽数目	严格的枢纽航线网络	非严格的枢纽航线网络
2	34 788 901 667.024	25 512 181 537.597
3	34 784 521 754.737	25 512 156 252.034
4	34 783 905 425.458	25 512 145 482.079

枢纽数目	枢纽节点	严格的枢纽航线网络	非严格的枢纽航线网络
2	hub1	0.60	0.52
2	hub2	0.40	0.48
3	hub1	0.50	0.33
	hub2	0.12	0.37
	hub3	0.38	0.30
4	hub1	0.33	0.22
	hub2	0.30	0.26
	hub3	0.07	0.27
	hub4	0.30	0.25

枢纽数目	负荷指标	严格的枢纽航线网络	非严格的枢纽航线网络
2	最小	0.66	0.60
	最大	1.44	0.78
	平均	1.05	0.69
3	最小	0.97	0.69
	最大	2.38	0.79
	平均	1.44	0.76
4	最小	0.78	0.76
	最大	2.01	0.79
	平均	1.88	0.78

[1]	邢志伟, 刘洪恩, 李彪, 罗谦, 文涛, 陈肇欣. 基于时空关联网络的机场机位运行过程建模[J]. 系统工程与电子技术, 2021, 43(3): 722-730.
[2]	邢志伟, 李彪, 罗谦. 过站航班地面保障运行效能评估[J]. 系统工程与电子技术, 2019, 41(5): 1071-1078.
[3]	张天慈, 丁萌, 左洪福, 王帮峰, 曾丽娜, 孙泽军. 基于区域控制的航空器滑行轨迹优化模型[J]. 系统工程与电子技术, 2016, 38(1): 136-141.
[4]	邢涛, 舒奂泽, 胡庆荣, 李军, 王冠勇. 修正的垂直航向运动补偿算法[J]. 系统工程与电子技术, 2015, 37(12): 2751-2757.
[5]	朱晓辉，张军. 基于似然轨迹预测的空中交通复杂度评估方法[J]. 系统工程与电子技术, 2014, 36(2): 300-305.

面向拥堵问题的枢纽航线网络优化模型

Optimization model of hub-and-spoke network for congestion problem

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 21

相关文章 5

编辑推荐

Metrics

本文评价