计算机科学 ›› 2017, Vol. 44 ›› Issue (Z11): 580-582.doi: 10.11896/j.issn.1002-137X.2017.11A.124

• 综合、交叉与应用 • 上一篇    下一篇

精确求解进港飞机调度双目标优化问题的epsilon约束算法

王璐,张小宁,孙智慧,吴辉   

  1. 上海民航职业技术学院 上海200232,同济大学经济与管理学院 上海200092,同济大学经济与管理学院 上海200092,上海民航职业技术学院 上海200232
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金重点项目(71531011)资助

Exact Epsilon-constraint Algorithm for Bi-objective Optimization of Flight Arrival Scheduling Problem

WANG Lu, ZHANG Xiao-ning, SUN Zhi-hui and WU Hui   

  • Online:2018-12-01 Published:2018-12-01

摘要: 随着机场客流的持续增长,航班延误日益严重。同时,对于机场最重要的跑道资源而言,积雪结冰等会造成 飞机 打滑,从而出现事故。对于机场管理者,周期性地维护跑道至关重要,以防雨雪天气出现飞机打滑事故。该研究主要针对跑道上的 航班调度问题,考虑恶劣天气环境下跑道的周期性维护(如周期性喷洒除雪盐等)。为了在保证航班的服务质量的同时提高机场跑道的使用效率,文中以最小化航班总延误和跑道使用时间为优化的双目标。首先,提出该双目标优化问题混合整数规划模型;其次,为了精确求解出Pareto前沿,开发出epsilon约束算法;最后,给出算例来说明模型和算法的可行性。通过数学规划理论建模并开发精确求解算法,为机场资源优化研究提供参考。

关键词: 机场物流,整数规划,双目标优化,精确算法

Abstract: With the rapid growth of airport passenger traffic,more and more flights delay.Meanwhile,in the management of the aircraft landing at the airport,security is very important.On the runway,low degree of friction caused by snow or ice can indure the airplane accidents.Therefore,periodic runway maintenance is extremely important.This paper studied the scheduling problem of aircrafts on the runway with periodic maintenance.To guarantee a good service performance for airlines,and to increase the efficiency of runway utilization,we set two objective functions,i.e.,the first one minimizing the total tardiness of all airplanes and the second minimizing the makespan.We established a bi-objective mixed integer linear programming model.Then to obtain the exact Pareto front,we developed an epsilon-constraint method.At last,we used an example to demonstrate a possible application of our model as well as the algorithm.The purpose of this work is to obtain exact solution set for the bi-objective optimization problem,which can help practitioners in airport management for reference.

Key words: Airport logistics,Pnteger programming,Bi-objective optimization,Exact algorithm

[1] PINOL H,BEASLEY J E.Scatter Search and Bionomic Algo-rithms for the aircraft landing problem[J].European Journal of Operational Research,2006,171(2):439-462.
[2] BEASLEY J E,SONANDER J,HAVELOCK P.Scheduling aircraft landings at London Heathrow using a population heuristic[J].Journal of the Operational Research Society,2001,52(5):483-493.
[3] DEAR R G.The dynamic scheduling of aircraft in the near terminal area[C]∥MIT Flight Transportation Laboratory Report R76-9,Massachusetts Institute of Technology.Cambridge,1976.
[4] BALAKRISHNAN H,Chandran B G.Algorithms for Scheduling Runway Operations Under Constrained Position Shifting[J].Operations Research,2010,58(6):1650-1665.
[5] BEASLEY J E,KRISHAMOORTHY M,SHARAIHA Y M.Scheduling Aircraft Landings--The Static Case[J].Transportation Science,2000,34(2):180-197.
[6] EUN Y,HWANG I,BANG H.Optimal Arrival Flight Sequencing and Scheduling Using Discrete Airborne Delays[J].IEEE Transactions on Intelligent Transportation Systems,2010,11(2):359-373.
[7] HARIKIOPOULO D,NEOGI N.Polynomial-Time FeasibilityCondition for Multiclass Aircraft Sequencing on a Single-Runway Airport[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(1):2-14.
[8] SOLVELING G.Stochastic programming methods for scheduling of airport runway operations under uncertainty.http://core.ac.uk/display/10189987 .
[9] 王璐,滕毅,吴辉.机场物流管理中考虑跑道维护的航班调度优化研究[J].物流工程与管理,2015(9):64-65.
[10] OIS,GENDREAU M,POTVIN J Y.An exact -constraint me-thod for bi-objective combinatorial optimization problems:Application to the Traveling Salesman Problem with Profits[J].European Journal of Operational Research,2009,194(1):39-50.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!