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

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

摘要/Abstract

摘要：

本文针对Hub-spoke结构航空公司在制订航班计划时机型指派问题，根据航空公司历史数据导出的旅客需求概率分布以及航班成本，设计了一种基于航班成本优化模型的表上作业法，提出了一种便于航班计划专员手工计算和调整机型的启发性算法，解决了航空公司机型指派0-1规划问题。该算法集成了匈牙利算法和回溯算法的思想，从航班成本最小值出发，根据航班优化的约束条件，按照深度优先搜索可行解，在不满足航班约束的节点处进行回溯，直到找到满足航班边界约束条件的航班成本最小值，得到最佳的机型指派，并给出了理论证明。通过案例对比验证该启发性算法有效性，通过表上作业法手工计算发现10架B737和5架B757方案总成本为409860美元，是所有方案中最低的，证明机型合理搭配可以使得公司运行效果更好；与传统的运筹学算法相比该算法构造直接和优化机理自然，简单实用，便于理解和掌握，便于大型航空公司计算机应用或分公司进行航班计划手工制订和调整。

关键词: 0-1整数规划, 航空公司机型指派, 启发性算法, 表上作业法, 回溯法

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

中图分类号:

TP273

吴国华. 一种基于Hub-Spoke结构航空公司机型指派的实用启发性算法[J]. 中国管理科学, 2024, 32(1): 158-167.

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.

图/表 11

图1

图2

图3

图4

图5

表1

机型指派表上作业法"

航班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$

表1

图6

图7

表2

表3

表4

参考文献 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]	樊霞, 刘西林. 基于实物期权的项目组合投资决策研究[J]. 中国管理科学, 2006, (1): 21-24.
[2]	范体军, 胡清淮. 大型供应链设计的基本数学模型与算法研究[J]. 中国管理科学, 2004, (6): 46-51.