Computer Science ›› 2017, Vol. 44 ›› Issue (Z11): 580-582.doi: 10.11896/j.issn.1002-137X.2017.11A.124

Previous Articles     Next Articles

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

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. .
[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!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .