English

应用科学学报

• 论文 • 上一篇    下一篇

停机位指派模型的排序模拟退火算法

陈 欣 ，陆 迅1,2，朱金福1   

  1. 1．南京航空航天大学 民航学院，江苏 南京 210016；
    2．上海机场战略部，上海 201206
  • 收稿日期:2007-03-23 修回日期:2007-05-30 出版日期:2007-09-30 发布日期:2007-09-30

Simulated Annealing with Sorting for Gate Assignment in Hub Airport

CHEN Xin1, LU Xun1,2, ZHU Jin-fu1   

  1. 1 School of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
    2 Department of Strategy and Development, Shanghai Airport Authority, Shanghai 201206, China
  • Received:2007-03-23 Revised:2007-05-30 Online:2007-09-30 Published:2007-09-30

被引次数

20

摘要： 实时的停机位指派对减少枢纽机场航班中转时间起着重要作用，但是停机位指派问题是NP-hard问题，常用的启发式算法计算效果较差。本文设计了一种排序模拟退火算法以求解枢纽机场的停机位指派问题。该算法首先根据停机位期望偏好值和航班客座率进行排序以得到模拟退火算法的初始解，然后运用经典模拟退火算法求解最优指派结果。算例表明，随着航班数量的增加，排序模拟退火算法的计算精度优于经典模拟退火算法，计算效率优于CPLEX软件且具有较快的收敛速度，为实时解决枢纽机场停机位优化指派问题提供了可能。

关键词: 枢纽机场, 停机位指派, 排序模拟退火算法, CPLEX

Abstract: It is important to reduce transfer time in hub airports with real-time gate assignment. However, the gate assignment problem (GAP) is an NP-hard problem, and traditional heuristic algorithms do not provide satisfactory solutions. We propose a new simulated annealing algorithm integrated with a sorting strategy to resolve the GAP. An initial solution is obtained through sorting each gate preference value and flight load factor. An optimal solution is then obtained using the traditional simulated annealing algorithm. Case studies show the simulated annealing algorithm with a prior sorting process can provide better results than the traditional simulated annealing algorithm. Computation efficiency is also better than CPLEX with an acceptable convergence rate. The proposed algorithm provides a new ways to resolve the GAP in hub airports.

Key words: hub airport, gate assignment problem, simulated annealing integrated with sorting approach, CPLEX