一种限界优化方法求解航班着陆调度问题
DOI:
CSTR:
作者:
作者单位:

中国民航大学

作者简介:

通讯作者:

中图分类号:

V355;U8

基金项目:

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


A Limit Optimization Method to Solve the Flight Landing Scheduling Problem
Author:
Affiliation:

Civil Aviation University of China,Tianjin

Fund Project:

National Natural Science Foundation of China(62173332);Natural Science Priority Program (3122023050);National Natural Science Foundation of China(U2133207);The Fundamental Research Funds for the Central Universities(3122020051)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    航空运输需求持续增长与枢纽终端区空域资源紧张的情况日益凸显,本文提出了一种限界优化的动态规划方法(Dynamic Programming Approach to Limit Optimization,DPALO)求解终端区航班着陆调度问题(Arrived Landing Problem, ALP)。首先建立了时间窗约束的航班着陆调度的离散化数学模型,推导了固定顺序下求解ALP的递推公式,并结合ALP问题特点,限界优化航班时间窗,并证明了所提方法不影响模型最优值的求解;其次运用精英遗传算法、粒子群算法、线性循环交换和线性循环插空等方法调整航班序列,以期求得较优解;最后在 OR-Library 数据集进行验证,实验结果表明,采用精英遗传算法调整航班着陆序列,DPALO的计算结果优于已知最优解((the Best Known Values,BKV)、仿生算法(Bionic Algorithm,BA)和位移决策算法(Dynamic Aircraft Landing Problem,DALP),与细胞自动机优化方法(Cellular Automaton Optimization,CAO)、紧致子序列算法(Compact Subsequence Algorithm,CSA)和混合粒子群优化-局部搜索算法(Hybrid Particle Swarm Optimization-Local Search algorithm in a Rolling Horizon framework,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. In this paper, a Dynamic Programming Approach to Limit Optimization (DPALO) is proposed to solve the Arrived Landing Problem (ALP). Firstly, a discrete mathematical model of flight landing scheduling with time window constraints is established, and a recursive formula for solving ALP with 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. Next, elite genetic algorithms, particle swarm algorithms, linear loop swapping and linear loop interpolation are applied to adjust the flight sequences with a view to finding an optimal solution. Finally validation is performed on OR-Library dataset. The experimental results show that using elite genetic algorithm to adjust the flight landing sequence, DPALO outperforms the known optimal solution (BKV), bionic algorithm (BA) and displacement decision algorithm (DALP). Similar to the results of the cellular automata optimization approach (CAO), the tight subsequence algorithm (CSA), and the hybrid particle swarm optimization-local search algorithm (RH-HPSO-LS), DPALO achieves milliseconds in time on the small sample dataset, and improves its time efficiency on the large sample dataset in comparison to CSA, CAO, and RH-HPSO-LS time efficiencies of 76.88%, 89.11%, and 78.28%, respectively.

    参考文献
    相似文献
    引证文献
引用本文
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2024-06-11
  • 最后修改日期:2024-09-13
  • 录用日期:2024-10-14
  • 在线发布日期:
  • 出版日期:
文章二维码
您是第位访问者
网站版权 © 南京航空航天大学学报
技术支持:北京勤云科技发展有限公司