一种限界优化方法求解航班着陆调度问题
A Limit Optimization Method for Flight Landing Scheduling Problems
冯小荣 1张帅 1丘东林 2王兴隆1
作者信息
- 1. 中国民航大学空中交通管理学院,天津 300300;民航飞联网重点实验室,天津 300300
- 2. 中国民航大学空中交通管理学院,天津 300300
- 折叠
摘要
航空运输需求持续增长与枢纽终端区空域资源紧张的情况日益凸显,本文提出了一种限界优化的动态规划方法(Dynamic programming approach to limit optimization,DPALO)求解终端区航班着陆调度问题(Arrived landing problem,ALP).首先建立了时间窗约束的航班着陆调度的离散化数学模型,推导了固定顺序下求解ALP的递推公式,并结合ALP问题特点,限界优化航班时间窗,并证明了所提方法不影响模型最优值的求解.其次,运用精英遗传算法、粒子群算法、线性循环交换和线性循环插空等方法调整航班序列,以期求得较优解.最后在 OR-Library 数据集进行验证,实验结果表明,采用精英遗传算法调整航班着陆序列,DPALO的计算结果优于已知最优解((Best known values,BKV)、仿生算法(Bionic algorithm,BA)和位移决策算法(Displacement decision algorthm,DDA),与细胞自动机优化方法(Cellular automaton optimization,CAO)、紧致子序列算法(Compact subsequence algorithm,CSA)和滚动时域-混合粒子群优化-局部搜索算法(Rolling horizon framework hybrid particle swarm optimization local search algorithm,RH-HPSO-LS)的结果相近;DPALO的时间效率在小样本数据集上时间效率达到毫秒级,在大样本数据集上相较于CSA、CAO和RH-HPSO-LS分别提升了76.88%、89.11%和78.28%.
Abstract
The continuous growth of air transportation demand and the tightness of airspace resources in the terminal area of a hub are becoming more and more prominent.A dynamic programming approach to limit optimization(DPALO)is proposed to solve the arrived landing problem(ALP).First,a discrete mathematical model of flight landing scheduling with time window constraints is established,and a recursive formula for solving ALP with a fixed order is derived.The flight time window is optimized by combining the ALP problem characteristics with the constraints,and it is proved that the proposed method does not affect the solution of the optimal value of the model.Second,elite genetic algorithms,particle swarm algorithms,the linear loop swapping and the linear loop interpolation are applied to adjust the flight sequences and then to finding an optimal solution.Finally,validation is performed on the OR-Library dataset.The experimental results show that using the elite genetic algorithms to adjust the flight landing sequence,DPALO outperforms the best known values(BKV),the bionic algorithm(BA)and the displacement decision algorithm(DDA)and obtains similar results to those of the cellular automata optimization approach(CAO),the tight subsequence algorithm(CSA),and the rolling horizon framework of hybrid particle swarm optimization local search algorithm(RH-HPSO-LS).The time efficiency of DPALO achieves milliseconds in time on the small sample dataset,and it is improved by 76.88%,89.11%,and 78.28%on the large sample dataset in comparison to CSA,CAO,and RH-HPSO-LS,respectively.
关键词
航班着陆调度/时间窗约束/动态规划/遗传算法/粒子群算法Key words
flight landing scheduling/time window constraints/dynamic programming/genetic algorithm/particle swarm optimization(PSO)引用本文复制引用
出版年
2024
国家科技期刊平台
NSTL
万方数据