No Access

Weighted Constrained Position Shift Model for Aircraft Arrival Sequencing and Scheduling Problem

Bo Xu

Business School, University of Shanghai for Science and Technology, Shanghai 200093, P. R. China

School of Economics and Management, Tongji University, Shanghai 200092, P. R. China

E-mail Address: 1986xubo@gmail.com

Corresponding author.

Search for more papers by this author

Weimin Ma

School of Economics and Management, Tongji University, Shanghai 200092, P. R. China

E-mail Address: mawm@tongji.edu.cn

Search for more papers by this author

Hui Huang

Jiangsu Migo Education and Technology Company Limited, Shanghai 200233, P. R. China

E-mail Address: huang.liuyuan@163.com

Search for more papers by this author

, and

Lei Yue

School of Economics and Management, Tongji University, Shanghai 200092, P. R. China

E-mail Address: yuechaolei@163.com

Search for more papers by this author

https://doi.org/10.1142/S0217595916500287Cited by:2 (Source: Crossref)

Abstract

The constrained position shift (CPS) model is a famous model in the aircraft arrival sequencing and scheduling (ASS) problem, which allows each aircraft to shift forward or backward at most $k$ (a given integer number) positions in the first come first serve (FCFS) sequence. However, CPS is insufficient to cope with the case that some aircraft requiring more than $k$ positions shift. From this point, we modify it to be a more applicable model, named weighted constrained position shift (W-CPS) model. Three methods are developed to solve W-CPS, which are dynamic programming (DP), mixed integer programming (MIP) and ant colony (AC) algorithm. Numerical results validate the efficiency of these methods.

Keywords:

References

Arkind, KD (2004). Requirements for a novel terminal area capacity enhancement concept in 2022. In American Institute of Aeronautics and Astronautics, Guidance, Navigation and Control Conf. Exhibit, Providence, RI. American Institute of Aeronautics and Astronautics, Reston, VA. Google Scholar
Abela, J, D Abramson, M Krishnamoorthy, A De Silva and G Mills (1993). Computing optimal schedules for landing aircraft. In Proc. 12th Natl. Conf. Australian Society for Operations Research, pp. 71–90. Adelaide. Google Scholar
Balakrishnan, H and BG Chandran (2010). Algorithms for scheduling runway operations under constrained position shifting. Operations Research, 58(6), 1650–1665. Web of Science, Google Scholar
Beasley, JE, M Krishnamoorthy, YM Sharaiha and D Abramson (2000). Scheduling aircraft landings-The static case. Transportation Science, 34(2), 180–197. Web of Science, Google Scholar
Bencheikh, G, J Boukachour, AEH Alaoui and FE Khoukhi (2009). Hybrid method for aircraft landing scheduling based on a job shop formulation. International Journal of Computer Science & Network Security, 9, 78–88. Google Scholar
Bencheikh, G, J Boukachour and AE Alaoui (2011). Improved ant colony algorithm to solve the aircraft landing problem. International Journal of Computer Theory and Engineering, 3(2), 224–233. Google Scholar
Bennell, JA, M Mesgarpour and CN Potts (2011). Airport runway scheduling. A Quarterly Journal of Operations Research, 9, 115–138. Web of Science, Google Scholar
Bianco, L, P Dell’Olmo and S Giordani (1999). Minimizing total completion time subject to release dates and sequence-dependent processing times. Annals of Operations Research, 86, 393–415. Web of Science, Google Scholar
Boehme, D (1994). Improved airport surface traffic management by planning. In Advanced Technologies for Air Traffic Flow Management, H Winter and H-G Nusser (Eds.) Lecture Notes in Control and Information Science, Vol. 198, pp. 191–224. Berlin: Springer. Google Scholar
Briskorn, D and R Stolletz (2014). Aircraft landing problems with aircraft classes. Journal of Scheduling, 17(1), 31–45. Web of Science, Google Scholar
Carr, FR (2004). Robust Decision-Support Tools for Airport Surface Traffic. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA. Google Scholar
Dear, RG (1976). The Dynamic Scheduling of Aircraft in the Near Terminal Area. MIT Flight Transportation Laboratory Report R76-9, Massachusetts Institute of Technology, Cambridge. Google Scholar
Dear, RG and YS Sherif (1991). An algorithm for computer assisted sequencing and scheduling of terminal area operations. Transportation Research, Part A, Policy & Practice, 25(2–3), 129–139. Web of Science, Google Scholar
de Neufville, R and AR Odoni (2013). Airport Systems: Planning, Design and Management, 2nd edn. McGraw-Hill, New York. Google Scholar
Dorigo, M (1992). Optimization, Learning and Natural Algorithms. Ph.D. thesis, Dip. Elettronica e Informazi one, Politecnico di Milano, Italy. Google Scholar
Dorigo, M and LM Gambardella (1997a). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66. Google Scholar
Dorigo, M and LM Gambardella (1997b). Ant colonies for the traveling salesman problem. BioSystems, 43, 73–81. Web of Science, Google Scholar
D’Ariano, A, D Pacciarelli, M Pistelli and M Pranzo (2015) Real-time scheduling of aircraft arrivals and departures in a terminal maneuvering area, Networks, 65(3), 212–227. Web of Science, Google Scholar
Faye, A (2015). Solving the aircraft landing problem with time discretization approach. European Journal of Operational Research, 242, 1028–1038. Web of Science, Google Scholar
Federal Aviation Administration (2009). http://aspm.faa.gov/main/opsnet.asp. Google Scholar
Furini, F, MP Kidd, CA Persiani and P Toth (2015). Improved rolling horizon approaches to the aircraft sequencing problem. Journal of Scheduling, 18, 435–447. Web of Science, Google Scholar
Garey, MR and DS Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: Freeman. Google Scholar
Idris, HR, B Delcaire, I Anagnostakis, WD Hall, N Pujet, E Feron, RJ Hansman, J-P Clarke and AR Odoni (1998). Identification of flow constraint and control points in departure operations at airport systems. American Institute of Aeronautics and Astronautics, Guidance, Navigation and Control Conf., Boston, AIAA-1998-4291. American Institute of Aeronautics and Astronautics, Reston, VA. Google Scholar
Lieder, A, D Briskorn and R Stolletz (2015). A dynamic programming approach for the aircraft landing problem with aircraft classes. European Journal of Operational Research, 243, 61–69. Web of Science, Google Scholar
Ma, W, B Xu, M Liu and H Huang (2014). An efficient approximation algorithm for aircraft arrival sequencing and scheduling problem. Mathematical Problems in Engineering, Article ID 236756, 8 pages. Web of Science, Google Scholar
Neuman, F and H Erzberger (1991). Analysis of delay reducing and fuel saving sequencing and spacing algorithms for arrival spacing. NASA Technical Report A-91203; NAS 1.15:103880; NASA-TM-103880. Retrieved August 2008, NASA Technical Reports Server (NTRS). Google Scholar
Pinol, H and J Beasley (2006). Scatter search and bionomic algorithms for the aircraft landing problem. European Journal of Operational Research, 171(2), 439–462. Web of Science, Google Scholar
Psaraftis, HN (1980). A dynamic programming approach for sequencing groups of identical jobs. Operations Research, 28(6), 1347–1359. Web of Science, Google Scholar
Randall, MC (2002). Scheduling aircraft landings using ant colony optimisation. In Proceedings of The IASTED International Conference Artificial Intelligence and Soft Computing, Banff, Canada. Google Scholar
Sama, M, A D’Ariano, P D’Ariano and D Pacciarelli (2014). Optimal aircraft scheduling and routing at a terminal control area during disturbances, Transportation Research, Part C 47(1), 61–85. Web of Science, Google Scholar
Sama, M, A D’Ariano and D Pacciarelli (2013). Rolling horizon approach for aircraft scheduling in the terminal control area of busy airports, Transportation Research, Part E 60(1), 140–155. Web of Science, Google Scholar
Soomer, M (2008). Runway Operations Scheduling Using Airline Preferences, Ph.D. Dissertation, VU University, Amsterdam. Google Scholar
Soomer, M and G Franx (2008). Scheduling aircraft landings using airlines preferences. European Journal of Operational Research, 190(1), 277–291. Web of Science, Google Scholar
Trivizas, DA (1998). Optimal scheduling with maximum position shift (MPS) constraints: A runway scheduling application. Journal of Navigation, 51(2), 250–266. Web of Science, Google Scholar
Willemain, TR, H Fan and H Ma. Statistical Analysis of Intervals Between Projected Airport Arrivals. DSES Technical Report 38-04-510, Rensselaer Polytechnic Institute, Troy, NY, 2004. Google Scholar
Zhan, ZH, J Zhang, Y Li, O Liu, SK Kwok, WH Ip and O Kaynak (2010). An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem. IEEE Transactions on Intelligent Transportation Systems, 11(2), 399–412. Web of Science, Google Scholar