基于紧致子序列的航班着陆调度问题研究  

Research on aircraft landing scheduling problem based on compact subsequence

作　　者：冯小荣 高正达 王进 王兴隆[1,2] 惠康华[3] FENG Xiaorong;GAO Zhengda;WANG Jin;WANG Xinglong;HUI Kanghua(Key Laboratory of Internet of Aircrafts,Civil Aviation University of China,Tianjin 300300,China;College of Air Traffic Management,Civil Aviation University of China,Tianjin 300300,China;School of Computer Science and Technology,Civil Aviation University of China,Tianjin 300300,China)

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

出　　处：《北京航空航天大学学报》2024年第8期2421-2431,共11页Journal of Beijing University of Aeronautics and Astronautics

基　　金：国家重点研发计划(2020YFB1600101);中央高校基本科研业务费专项资金(3122020052)。

摘　　要：航班着陆调度问题已被证明是NP难问题,综合考虑多种实际情况,建立了时间窗约束的航班着陆优化模型,定义了紧致子序列概念,论述了其性质及左移、分割和合并的条件。在此基础上,提出一种基于紧致子序列的算法(CSA)求解固定顺序下航班着陆调度问题。按照航班的最优着陆时间排序,运用CSA计算出该顺序下各航班着陆时间;采用循环线性交换和循环线性插空策略微调该固定顺序,不断迭代逼近模型的最优解;采用OR-Library数据集进行验证。实验结果表明,CSA结合启发式微调策略求解结果明显优于位移决策算法DALP和仿生算法(BA),与CPLEX、混合粒子群优化-局部搜索算法RH-HPSO-LS、细胞自动机优化(CAO)算法相近,在时间效率上明显优于对比算法;在小规模数据集上,计算精度与速度优势更加明显。CSA是一种确定性算法,不依赖于先验参数,具有更高的鲁棒性,保证了启发式微调策略不断逼近最优解。The aircraft landing scheduling problem has been proven to be an NP-hard problem.A multi-aircraft optimization model with time window constraints is established for the fixed aircraft scheduling sequence considering more practical situations.The concept of compact subsequence,its properties,left shift,division and merging conditions are discussed.A compact subsequence algorithm(CSA)for fixed-order aircraft landing problems is proposed.Sort by the optimal landing time of the aircraft and calculate the landing time of each aircraft in this order using CSA.Adjust the fixed order using the circular linear exchange and cyclic linear interpolation strategies.Then,compute iteratively to get an approximation of the model’s ideal solution.The OR-Library dataset is used for verification.Comparable to the CPLEX,RH-HPSO-LS,and cellular automation-based optimization(CAO),the results demonstrate that CSA,when paired with a heuristic fine-tuning method,can yield much superior outcomes than DALP and bionomic algorithm(BA).The algorithm also shows better advantages in time efficiency.It is extremely obvious that the advantages of computing precision and speed on small-scale datasets.CSA is a deterministic method that does not depend on prior parameters and has higher robustness,it can ensure that the heuristic fine-tuning strategy approaches the optimal solution continuously.

关 键 词：航班着陆调度 时间窗约束 紧致子序列 循环线性交换 循环线性插空 

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