一种限界优化方法求解航班着陆调度问题  

A Limit Optimization Method for Flight Landing Scheduling Problems

作　　者：冯小荣 张帅 丘东林 王兴隆[1,2] FENG Xiaorong;ZHANG Shuai;QIU Donglin;WANG Xinglong(Air Traffic Management College,Civil Aviation University of China,Tianjin 300300,China;Key Laboratory of Internet of Aircraft,Tianjin 300300,China)

机构地区：[1]中国民航大学空中交通管理学院,天津300300 [2]民航飞联网重点实验室,天津300300

出　　处：《南京航空航天大学学报》2024年第6期1024-1035,共12页Journal of Nanjing University of Aeronautics & Astronautics

基　　金：国家自然科学基金面上项目(62173332);国家自然科学基金重点项目(U2133207);中央高校基本科研业务费‑自然科学重点项目(3122023050);中央高校基本科研业务费专项基金项目(3122020051)。

摘　　要：航空运输需求持续增长与枢纽终端区空域资源紧张的情况日益凸显,本文提出了一种限界优化的动态规划方法(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%。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.

关 键 词：航班着陆调度 时间窗约束 动态规划 遗传算法 粒子群算法 

分 类 号：V355[航空宇航科学与技术—人机与环境工程] U8[交通运输工程]