基于GSAA的停机位指派优化问题的研究

交通运输系统工程与信息 ›› 2008, Vol. 8 ›› Issue (1): 138-143 .

基于GSAA的停机位指派优化问题的研究

鞠姝妹;许俐^*

南京航空航天大学民航学院南京 210016

收稿日期:2007-08-24 修回日期:2007-11-16 出版日期:2008-02-25 发布日期:2008-02-25
通讯作者: 许俐
作者简介:鞠妹妹（1984-），女，江苏淮安市人，硕士生.
基金资助:
民航总局软科学基金项目（MHRD0622）.

Airport Gate Assignment Problems Based on GSAA

JU Shu-mei;XU Li

School of Civil Aviation， Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China

Received:2007-08-24 Revised:2007-11-16 Online:2008-02-25 Published:2008-02-25
Contact: XU Li

摘要/Abstract

摘要： 停机位的合理指派是机场地面作业中的一项核心任务，对减少枢纽机场航班中转时间起着重要作用，但是停机位指派问题是NP难问题，模型和算法都比较复杂。建立了以旅客满意度为优化目标的数学模型，并设计了一种贪婪模拟退火算法（GSAA），以求解枢纽机场的停机位指派问题。该算法首先根据贪婪算法FCFS准则使“丢失”的航班数最少得到模拟退火算法的初始解，然后运用经典模拟退火算法求解出最优指派结果。数值仿真证明了模型和算法的有效性。

关键词: 枢纽机场, 停机位指派, 旅客满意度, 贪婪模拟退火算法

Abstract: Airport gate assignment is a key task among the airport ground work which is important to reduce transfer time in hub airports. However, the gate assignment problem (GAP) is an NP-hard problem, and its models and algorithms are complex. This paper proposes a model and a new greedy simulated annealing algorithm (GSAA) to resolve the GAP. The initial solution of the proposed algorithm is obtained through FCFS criterion of greedy method to minimize the “dropping” flights, and then the optimal solution is obtained through the traditional simulated annealing algorithm. Simulation result shows the validity of the model and the algorithm.

Key words: hub airport, gate assignment problem, the degree of passenger satisfaction, greedy simulated annealing algorithm

中图分类号:

V351.11

鞠姝妹,许俐. 基于GSAA的停机位指派优化问题的研究[J]. 交通运输系统工程与信息, 2008, 8(1): 138-143 .

JU Shu-mei,XU Li. Airport Gate Assignment Problems Based on GSAA[J]. Journal of Transportation Systems Engineering and Information Technology, 2008, 8(1): 138-143 .

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract17631.shtml

http://www.tseit.org.cn/CN/Y2008/V8/I1/138

参考文献

[1] Geun-Sik Jo, Jong-Jin Jung, Chang-Yoon Yang. Expert system for scheduling in an airline gate allocation[J]. Expert System with Applications, 1997, 13(4), 275-282.

[2] Yu Cheng. A knowledge-based airport gate assignment system integrated with mathematical programming[J]. Computers and Industrial Engineering, 1997, 32, 837-852.

[3] Shangyao Yan, Chia-Ming Chang. A network model for gate assignment[J]. Journal of Advanced Transportation, 1998, 32:176-189.

[4] Ali Haghani , Min-Ching Chen. Optimizing gate assignment[J]. Transportation Research A, 1998, 32, 437-454.

[5] Ahmet Bolat. Procedures for providing robust gate assignments for arriving aircraft[J]. European Journal of Operational Research, 2000, 120(2000), 63-80.

[6] Shangyao Yan, Chen Ming Huo. Optimization of multiple objective gate assignments[J]. Transportation Research A, 2001, 35:413-432.

[7] 康立山, 谢云, 尤矢勇, 罗祖华. 非数值并行算法（第一册）─模拟退火算法[M]. 科学出版社. 1997, 53-55.[KANG Li-shan, XIE Yun, YOU Shi-yong, LUO Zu-hua. Non-numerical Parallel Algorithms(1)─Simulated Annealing Algorithm[M]. Beijing, Science Publication. 1997: 53-55.]

[8] 常钢, 魏生民. 停机位分配问题优化技术[J]. 中国民航学院学报, 2006, 24(2): 25-29. [CHANG Gang, WEI Sheng-min. Research on optimization of aircraft stands assignment problem[J]. Journal of Civil Aviation University of China, 2006, 24(2): 25-29.]

[9] 文军, 孙宏, 徐杰, 梁志杰. 基于排序算法的机场停机位分配问题的研究[J].系统工程, 2004, 22(7): 102-105. [WEN Jun, SUN Hong, XU Jie, LIANG Zhi-jie. Research of airport gate assignment problem based on sorting algorithm[J]. System Engineering, 2004, 22(7): 102-105.]

[10]Ding H., Lim A.,.Rodrigues B, Zhu Y.. Aircraft and gate scheduling optimization at airports[C]//. Proceedings of the 37th Hawaii International Conference on System Science-2004, 2004.