一种基于Hub-Spoke结构航空公司机型指派的实用启发性算法

doi:10.16381/j.cnki.issn1003-207x.2021.2459

Abstract

Abstract:

The fleet assignment problem of Hub-spoke network airlines in making flight schedules is addressed. According to the demand distribution of passengers and resulting in the flight costs from the airline's historical data， an optimization algorithm by tabular operation method based on the flight cost model is designed， and an heuristic algorithm is proposed for flight planning specialist to facilitate manual calculation and to adjust aircraft types， which solves the airline fleet assignment 0-1 integer programming problem， The algorithm integrates the ideas of Hungarian algorithm and backtracking algorithm. Starting from the minimum cost of ?ight optimization， the algorithm searches the optimal value by the depth-first-search method subject to the optimization constraints， and backtracks in the nodes when the aircraft constraints are not met， finds the minimum flight cost that meets the aircraft side constraints， and obtains the optimal fleet assignment and hence gives a theoretical proof. The effectiveness of the heuristic algorithm is obtained through case study. The total cost of ten B737 and five B757 scenarios is found to be the lowest among all scenarios by manual calculation using the tabular method， reaching $409，860， which proves that a reasonable mix of aircraft types can make the company operate better. Compared with the traditional operations research algorithm this algorithm is straightforward in construction and natural in optimization mechanism， which is simple and practical， also easy to understand and master， especially for small airlines or branches to manually formulate and adjust flight schedules.

Key words: 0-1 integer programming, airline fleet assignment（FAM）, heuristic algorithm, tabular operation method, backtracking algorithm

CLC Number:

TP273

Guohua Wu. Based on Hub-Spoke Network a Practice Heuristic Algorithm Applied to Airline Fleet Assignment[J]. Chinese Journal of Management Science, 2024, 32(1): 158-167.

Figures/Tables 11

航班i	进(+)出(-)港	成本增量 $△ c i j$		机型指派（回溯调整）	飞机平衡		回溯调整
航班i	进(+)出(-)港	j=1	j=2	机型指派（回溯调整）	j=1	j=2	j=1	j=2
0					$G 0,1$	$G 0,2$
1	-	$△ c 11$	0	j=2		-1
2	-	0	$△ c 22$	j=1	-1
:
k	+	0	$△ c k, 2$	j=1	+1
k+1	-	0	$△ c k + 1,2$	j=1	-1
:
n-1	+	$△ c n, 1$	0	j=2		+1
					$G n, 1$	$G n, 2$

References 36

1	Abara J.Applying to integer linear programming to thefleet assignment problem［J］. Interfaces， 1989， 19（4）： 20-28.
2	Rushmeier R A， Kontogiorgis S A.Advances in the optimization of airline fleet assignment［J］. Transportation Science， 1997， 31（2）：159-169.
3	Berge M E， Hopperstad C A. Demand driven dispatch： a method for dynamic aircraft capacity assignment， models and algorithms［J］. Operations Research， 1993， 41（1）：153-168.
4	Hane C A， Barnhart C， Johnson E L， et al. The fleet assignment problem： solving a large-scale integer program［J］. Mathematical Programming， 1995，70（1-3）：211-232.
5	Bazargan M. Airline operations and scheduling［M］.New York： Routledge， 2016.
6	Belobaba P， Odoni A， Barnhart C. The global airline industry［M］. Chichester： John Wiley & Sons Ltd， 2009.
7	朱金福.航空运输管理［M］.西安：西北工业大学出版社，2009：409-421.
	Zhu J F. Air transport management［M］. Xi'an：Northwestern Polytechnic University Press，2009：409-421.
8	Subramanian R， Scheff R P， Quillinan J D， et al. Coldstart： fleet assignment at delta air lines［J］. Interfaces， 1994，24（1）：104-120.
9	朱星辉，朱金福，巩在武.我国航空公司机型指派模型及算法研究［J］.工业技术经济，2007，26（4）：75-77.
	Zhu X H， Zhu J F， Gong Z W. Research on the model and algorithm of airline type assignment in China［J］. Industrial Technology and Economy， 2007， 26（4）： 75-77.
10	Zhou L. Airline planning and scheduling： models and solution methodologies［J］. Frontiers of Engineering Management， 2020， 7（5）： 1-26.
11	Lohatepanont M， Barnhart C. Airline schedule planning：integrated models and algorithms for schedule design and ﬂeet assignment［J］. Transportation Science， 2004，38（1）： 19-32.
12	汪瑜，孙宏.基于航班机型分配的机队规划启发式算法［J］.系统工程理论与实践，2011，31（2）：182-189.
	Wang Y， Sun H. A ﬂeet planning heuristic based on flight type assignment［J］. Systems Engineering-Theory & Practice， 2011，31（2）：182-189.
13	Barnhart C， Johnson E L， Nemhauser G L， et al. Branch-and-price： column generation for solving huge integer programs［J］. Operations research， 1998， 46（3）： 316-329.
14	Hai J， Barnhart C. Robust airline schedule design in a dynamic scheduling environment［J］. Computers & Operations Research， 2013， 40（3）： 831-840.
15	贾宝惠，张恩翼，李耀华. 飞机排班机型指派管理优化问题研究［J］.计算机仿真，2016，33（12）：42-46.
	Jia B H， Zhang E Y， Li Y H. Research on the optimization problem of aircraft scheduling type assignment management［J］. Computer Simulation， 2016， 33（12）：42-46.
16	胡玉真，宋艳，许保光.单架飞机受干扰后飞机路径恢复多项式算法研究［J］.运筹与管理， 2017， 26（8）：11-18.
	Hu Y Z， Song Y， Xu B G. Research on polynomial algorithm for aircraft path recovery after single aircraft disturbance［J］. Operations Research and Management，2017，26（8）：11-18.
17	肖晚霞，董兴业，林友芳. 航班恢复问题的迭代局部搜索算法［J］. 计算机与现代化， 2019（9）：1-6.
	Xiao W X， Dong X Y， Lin Y F. An iterative local search algorithm for ﬂight recovery problem［J］. Computers and Modernization， 2019（9）：1-6.
18	孙宏，文军，徐杰. 基于均衡使用要求的飞机排班算法［J］. 西南交通大学学报， 2004（5）：569-572.
	Sun H， Wen J， Xu J. Aircraft schedule algorithm based on balanced usage requirements［J］. Journal of Southwestern Jiaotong University， 2004（5）：569-572.
19	Barnhart C， Hatay L， Johnson E L. Deadhead selection for the long haul crew pairing problem［J］. Operations Research， 1995， 43（3）：491-499.
20	Saddoune M， Desaulniers G， Elhallaoui I， et al. Integrated airline crew pairing and crew assignment by dynamic constraint aggregation［J］. Transportation Science， 2012， 46（1）：39-55.
21	Ahmed M B， Hryhoryeva M， Hvattum L M， et al. A matheuristic for the robust integrated airline fleet assignment， aircraft routing and crew pairing problem［J］. Computers & Operations Research， 2022，137：105-551.
22	白凤，朱金福，高强. 基于列生成法的不正常航班调度［J］. 系统工程理论与实践， 2010， 30（11）：2036-2045.
	Bai F， Zhu J F， Gao Q. Scheduling irregular flights based on column generation method［J］. Systems Engineering-Theory & Practice， 2010，30（11）：2036-2045.
23	唐小卫，朱金福，高强. 流不平衡条件下飞机恢复的优化模型与算法研究［J］. 小型微型计算机系统， 2010， 31（4）：793-796.
	Tang X W， Zhu J F， Gao Q. Optimization model and algorithm study of aircraft recovery under flow imbalance conditions［J］. Small Microcomputer Systems， 2010， 31（4）：793-796.
24	李晓岚，乐美龙. 多目标飞机和旅客恢复分阶段启发式算法［J］. 计算机应用研究， 2014， 31（8）：2270-2274.
	Li X L， Le M L. Multi-objective aircraft and passenger recovery phased heuristic algorithm［J］. Computer Application Research， 2014， 31（8）：2270-2274.
25	Liang Z， Xiao F， Qian X， et al. A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance ﬂexibility［J］. Transportation Research Part B， 2018， 113：70-90.
26	Xu Y F， Wandelt S， Sun X Q. Airline integrated robust scheduling with a variable neighborhood search based heuristic［J］.Transportation Research Part B， 2021， 149 ：181-203.
27	Ozkır V， Ozgur M S. Two-Phase heuristic algorithm for integrated airline fleet assignment and routing problem［J］.Energies，2021，DOI：10.3390/en14113327 . doi: 10.3390/en14113327
28	Kiarashrad M， Pasandideh S H R， Mohammadi M. A mixed-integer nonlinear optimization model for integrated ﬂight scheduling， fleet assignment and ticket pricing in competitive market［J］. Journal of Revenue and Pricing Management， 2021，20（5）：596-607.
29	Guepet J， Acuna-Agost R， Briant O， et al. Exact and heuristic approaches to the airport stand allocation problem［J］.European Journal of Operational Research， 2015， 246（2）： 597-608.
30	Cacchiani V， Salazar-Gonz´alez J-J. Heuristic approaches for flight retiming in an integrated airline scheduling problem of a regional carrier［J］. Omega， 2020， DOI：10.1016/j.omega.2019.01.006 . doi: 10.1016/j.omega.2019.01.006
31	Khanmirza E， Nazarahari M， Haghbeigi M. A heuristic approach for optimal integrated airline schedule design and fleet assignment with demand recapture［J］. Applied Soft Computing Journal， 2020， DOI：10.1016/j.asoc.2020.106681 . doi: 10.1016/j.asoc.2020.106681
32	Okafor E G， Ubadike O C， Anene N H， et al. Study of ﬂeet assignment problem using a hybrid technique based on Monte Carlo simulation and genetic algorithm［J］. Nigerian Journal of Technology， 2019， DOI：10.4314/njt.v38i3.30 . doi: 10.4314/njt.v38i3.30
33	Wei K J， Vaze V， Jacquillat Alexandre. Airline timetable development and fleet assignment incorporating passenger choice［J］. Transportation Science， 2020， 54（1）：139-163.
34	Zhang D， Yu C H， Lau H. An integrated flight scheduling and fleet assignment method based on a discrete choice model［J］. Computers & Industrial Engineering， 2016， 98：195-210.
35	Safak Ö， Cavus Ö， Aktürk M S. Multi-stage airline scheduling problem with stochastic passenger demand and non-cruise times［J］. Transportation Research Part B， 2018， 114 ： 39-67.
36	Goodrich M T， Tamassia R， Goldwasser M H. Data structures and algorithms in Python［M］.New Jersey： John Wiley & Sons Ltd， 2013.

航班	进出港	成本（成本增量）		指派机型	飞机数量(回溯调整)		机型调整	成本损失
航班	进出港	737	757	指派机型	737	757	机型调整	成本损失
					2	1
104	-	25258（671）	24587（0）	757	2(1)	0（1）	737	671
105	-	29755（2758）	26997（0）	757	2(1)	-1（0）
125	+	19557（0）	22902（3345）	737	(1)	（1）	757	3345
106	-	21862（0）	23377（1515）	737	(0)	( )
126	+	18489（0）	22785（4296）	737	(1)	( )
127	+	17737（0）	22757（5021）	737	(2)	（）
					2	1

航班	进出港	成本（成本增量）		指派机型	飞机数量(回溯调整)		机型调整	成本损失
航班	进出港	737	757	指派机型	737	757	机型调整	成本损失
					2	1
104	-	25258（671）	24587（0）	757	2(1)	0（1）	737	671
105	-	29755（2758）	26997（0）	757	2(1)	-1（0）
125	+	19557（0）	22902（3345）	737	(2)	（0）
106	-	21862（0）	23377（1515）	737	（1）	( )
126	+	18489（0）	22785（4296）	737	(2)	( )
127	+	17737（0）	22757（5021）	737	(3)	（）
					3	0

编号	LOS		SFO		MIA		ATL		ORD		IAD		BOS		JFK		总数		算法	总成本（美元）
编号	a	b	a	b	a	b	a	b	a	b	a	b	a	b	a	b	a	b	算法	总成本（美元）
1	2	0	2	1	0	2	0	1	1	0	0	0	1	0	3	2	9	6	文献[5]	415309
2	2	0	2	1	0	2	0	1	1	0	0	0	1	0	3	2	9	6	本文	415309
3	1	1	1	1	0	2	0	1	1	0	0	0	1	0	5	1	9	6	本文	410128
4	2	0	1	1	0	2	0	1	1	0	0	0	1	0	5	1	10	5	本文	411278
5	1	1	1	1	0	2	0	1	1	0	0	0	1	0	6	0	10	5	本文	409860
6	2	0	1	1	0	2	0	1	1	0	0	0	1	0	6	0	11	4	本文	411010
7	2	0	2	0	1	0	1	0	1	0	0	0	1	0	5	0	13	0	无	418260
8	0	2	0	2	0	1	0	1	0	1	0	0	0	1	0	5	0	13	无	448149

[1]	GAO Hong-wei, LI Lu. Real-time Pricing Based on PMSC Management and Reward-Punishment Mechanism in Smart Grid [J]. Chinese Journal of Management Science, 2022, 30(7): 88-98.
[2]	XU Bao-guang, CHANG Jia-xin, GAO Min-gang. Research on Routing Problems about Road Information Collection Considering Mixed Mapping Method [J]. Chinese Journal of Management Science, 2022, 30(4): 218-227.
[3]	GUO Fang, HUANG Zhi-hong, HUANG Wei-lai, YANG Chao. Optimal Planning of the Electric Vehicle Routing and Battery Charging Problem with Self-pickup and Door-to-door Delivery Service [J]. Chinese Journal of Management Science, 2022, 30(2): 264-275.
[4]	GUO Fang, YANG Jun, YANG Chao. Study on Heterogeneous Electric Vehicle Routing and Batterycharging Problem with the Consideration of Differentiated Service Cost [J]. Chinese Journal of Management Science, 2019, 27(8): 118-128.
[5]	ZHANG Yang, DAN Bin, GAO Hua-Li. Stochastic Scheduling of Product Service System Orders with Due Date Assignment [J]. Chinese Journal of Management Science, 2019, 27(2): 93-106.
[6]	YANG Jun, FENG Peng-xiang, SUN Hao, YANG Chao. Carbon Emission Reduction Cost-Sharing Model in Supply Chain Based on Improvingthe Demand for Low-Carbon Products [J]. Chinese Journal of Management Science, 2015, 23(9): 87-96.
[7]	XIAO Yi-yong, CHANG Wen-bing, ZHANG Ren-qian. A Research on Heuristic Production Planning with Dual Constraints of Capabilities and Resources [J]. Chinese Journal of Management Science, 2008, 20(6): 33-40.
[8]	QIAO Zhong, LI Ling-ying. A Bi-Level Programming Model for Location of Commodity Exchange Market Network Points [J]. Chinese Journal of Management Science, 2008, 16(1): 125-130.
[9]	LU Kui, YANG Chang-hui, Dai Dao-ming. A Heuristic Algorithm for Multi-Product Capacitated Lot Sizing with Subcontracting and Time-varying Transportation Costs [J]. Chinese Journal of Management Science, 2008, 16(1): 80-85.
[10]	FAN Xia, LIU Xi-lin. The Study of Multiple Projects Investment Decision Based on Real Option [J]. Chinese Journal of Management Science, 2006, (1): 21-24.
[11]	LI Yan-hui, MA Shi-hua. An MINLP Model for the Single-Source and p-Median Distribution System Based on Time Constraints [J]. Chinese Journal of Management Science, 2004, (3): 86-90.
[12]	HE Tie-lin. On Multi-Constrained Paths in Networks [J]. Chinese Journal of Management Science, 2003, (4): 41-46.
[13]	Huang Wei-wen, QIAN Yan-nan, XU Bao-guang. The Application of Row/Column Elimination Method on Contatiner Loading in Import/Export Trade [J]. Chinese Journal of Management Science, 2002, (1): 89-93.
[14]	SHAN Lian-long, GAO Zi-you . A Stochastic Equilibrium Network Design Model and Its Solution Algorithm for Transit System [J]. Chinese Journal of Management Science, 2001, (1): 41-49.

Based on Hub-Spoke Network a Practice Heuristic Algorithm Applied to Airline Fleet Assignment

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 36

Related Articles 14

Metrics

Comments

Recommended 0