||Partitioning of Arrival Aircraft Scheduling Problems
||Institute of Civil Aviation
Aircraft Landing Problem
Our sky has become overcrowded due to an increase in yearly air transports, which in turn has caused a shortage in airport capacity. Aircraft flow constraints result in delays in busy airports during peak times and will in turn increase the costs for airline companies. The current method used by air traffic controllers (ATCs) is First-Come-First-Served (FCFS). However, this method is insufficient to solve the sequence issues faced by aircraft. In this research, an optimal partition method is proposed to decrease the scheduling algorithm calculation time. In the algorithm, the sequence is broken down into several smaller subsequences and rescheduled to the aforementioned sequences with two main targets. The first target is to try to reduce the total computation time, which enables the computation of a longer sequence than was possible in the past. The second target would be to alter the previous sequence into a new and more efficient way for aircraft to land. Aircraft are overlapped between subsequences to ensure this method doesn’t happen while scheduling the sequence without overlapping, both separated subsequences have their optimal sequence. Once the separated sequences are combined, however, the complete sequence may not have the most optimal sequencing. The new approach sequence allows aircraft to land faster and in a more orderly fashion than the original sequence, thus reducing the makespan period. Finally, several simulation results are used to demonstrate the effectiveness of the proposed approach phase.
LIST OF FIGURES VI
LIST OF TABLES VIII
CHAPTER 1 Introduction 1
1.1 Motivation 1
1.2 Literature Review 5
1.3 Thesis Outline 8
CHAPTER 2 Background Information 9
2.1. The importance of separation 9
2.2 Current Separation adjustment methods 10
2.2.1 Route Adjustment 10
2.2.2 Speed Adjustment 10
2.2.3 Holding Pattern Adjustment 10
2.3 Separation Regulations 12
2.4 Conflict Detection 13
2.5 Controlling the Time Window 14
2.6 Constrained Position Shifting (CPS)14
CHAPTER 3 The Aircraft Landing Problem 16
3.1 Problem description 16
3.2 The formula of the previous research methodology 18
3.2.1 Mixed integer linear programming (MILP) 18
3.2.2 Genetic algorithm (GA) 20
3.2.3 Dynamic programming (DP) 24
3.2.4 Quadratically constrained quadratic program (QCQP) 25
CHAPTER 4 Partition methods 30
4.1 Fixed partition size 30
4.2 Partition by repeated aircraft type 32
4.3 Partition using local optimal combinations 34
4.4 Overlapping aircraft with constrained position shifting 36
4.4.1 Position Shifting 37
4.4.2 Number of aircraft that must be overlapped 40
4.4.3 Algorithm of scheduling aircraft 42
4.4.4 Aircraft per subsequence simulation 45
4.5 Comparison of the above methods 47
CHAPTER 5 Simulation Results 49
5.1 Comparison of the results with those of the QCQP solution 49
5.2 Using different numbers of aircraft per subsequence 53
CHAPTER 6 Conclusion 59
 OAG, "On-time performance for airlines and airports and TOP 20 busiest routes" 2018.
 ACI, "Annual World Airport Traffic Forecasts 2017–2040", 2017.
 Schulz, E., "Global Networks, Global Citizens Global Market Forecast 2018 - 2037", 2018.
 Capri, S., and Ignaccolo, M.,"Genetic algorithms for solving the aircraft sequencing problem: the introduction of departures into the dynamic model," Journal of Air Transport Management, vol. 10, no. 5, pp. 345-351, 2004.
 ICAO, "CNS/ATM," 1998.
 Abela, J., Abramson, D., Krishnamoorthy, M., Silva, A. De, and Mills, M., "Computing Optimal Schedules for Landing Aircraft," The 12th National Conference of the Australian Society for Operations Research, pp. 71-90, 1993.
 Beasley, J. E., Krishnamoorthy, M., Sharaiha Y. M., and Abramson D., "Scheduling aircraft landings -the static case", Transportation Science, vol. 34, No. 2, pp. 180-197, 2000.
 Bennell, J. A., Potts, C. N., and Mesgarpour, M., "A Review of Airport Runway Optimization", University of Southampton, 2009.
 Wen, M., "Algorithms of Scheduling Aircraft Landing Problem,"Department of Informatics and Mathematical Modelling Technical University of Denmark, 2005.
 Dear, R. G., "The Dynamic Scheduling of Aircraft in The Near Terminal Area," Flight Transportation Laboratory Massachusetts Institute of Technology Cambridge, 1976.
 Dear, R. G., and Sherif, Y. S.,"The Dynamic Scheduling of Aircraft in High Density Terminal Areas," Microelectronics. Reliability, vol. 29, No. 5, pp. 743-749, 1989.
 Lieder, A., Briskorn, D., and Stolletz, R., "A Dynamic Programming Approach for The Aircraft Landing Problem with Aircraft Classes," European Journal of Operational Research, vol. 243, no. 1, pp. 61-69, 2015.
 Wang, T. C., and Li, Y. J., "Optimal Scheduling and Speed Adjustment in En Route Sector for Arriving Airplanes," Journal of Aircraft, vol. 48, no. 2, pp. 673-682, 2011.
 Wang, T. C., and Chen, T. C., "Arrival and Departure Aircraft Scheduling with Turbulence Interaction Concept," Journal of Aircraft, vol. 53, No. 5 , 2016.
 Wang, T. C., and Tsao, C. H., "Time-Based Separation for aircraft Landing Using Danger Value Distribution Flow Model ," Mathematical Problems in Engineering, vol. 2012, pp. 16, 2012.
 FAA, "Air traffic control," 2018.
 FAA, "Instrument Flying Handbook, "2001.
 CAA, "Air Traffic Management Procedures,"2017.
 ICAO, "Air Traffic Management Procedures For Air Navigation Services Doc 4444,"2016.
 Nicolaon, J. P., Freville, E., Vidal, A., Crick, P., "Potential Benefits of a Time-based Separation Procedure to maintain the Arrival Capacity of an Airport in strong head-wind conditions," no. Fifth USA/Europe Air Traffic Management Research and Development Seminar ,2003.
 Balakrishnan, H., and Chandran, B., "Scheduling Aircraft Landings under Constrained Position Shifting ,"AIAA Guidance, Navigation, and Control Conference, Colorado, 2006.
 Briskorn, D. and Stolletz, R., "Aircraft landing problems with aircraft classes," Journal of Scheduling, vol. 17, pp. 31-45, 2014.
 Goldberg, D. E., and Holland, J. H., " Genetic Algorithms And Machine Learning," Machine Learning, vol. 3, pp. 95-99, 1988.
 Shanno, D. F., and Weil, R. L., " Linear Programming with Absolute Value Functionals," Operations Research, pp.120-124, 1971.