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

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

Abstract

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

CLC Number:

TP301.6

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.

Figures/Tables 12

Fig.1

Fig.2

Fig.3

Table 1

Table 2

Hub-and-spoke network optimization algorithm for congestion problem (algorithm 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行个体的所有元素

Table 2

Table 3

Table 4

Table 5

Fig.4

Fig.5

Fig.6

Fig.7

References 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]	Zhiwei XING, Hong'en LIU, Biao LI, Qian LUO, Tao WEN, Zhaoxin CHEN. Modelling for airport gate operation process based on relational spatio-temporal network [J]. Systems Engineering and Electronics, 2021, 43(3): 722-730.
[2]	XING Zhiwei, LI Biao, LUO Qian. Operational effectiveness evaluation of ground service for transit flight [J]. Systems Engineering and Electronics, 2019, 41(5): 1071-1078.
[3]	ZHANG Tian-ci, DING Meng, ZUO Hong-fu, WANG Bang-feng, ZENG Li-na, SUN Ze-jun. Zone control based aircraft ground movement trajectory optimization model [J]. Systems Engineering and Electronics, 2016, 38(1): 136-141.
[4]	ZHU Xiao-hui， ZHANG Jun. Air traffic complexity evaluation method based on probabilistic trajectory prediction [J]. Systems Engineering and Electronics, 2014, 36(2): 300-305.

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

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 21

Related Articles 4

Recommended Articles

Metrics

Comments