
系統識別號 
U00262705201916153600 
論文名稱(中文) 
飛機進場排序拆解問題 
論文名稱(英文) 
Partitioning of Arrival Aircraft Scheduling Problems 
校院名稱 
成功大學 
系所名稱(中) 
民航研究所 
系所名稱(英) 
Institute of Civil Aviation 
學年度 
106 
學期 
2 
出版年 
107 
研究生(中文) 
康云馨 
研究生(英文) 
YunShin Kang 
學號 
Q46051043 
學位類別 
碩士 
語文別 
英文 
論文頁數 
62頁 
口試委員 
指導教授王大中 口試委員詹劭勳 口試委員沈宗緯

中文關鍵字 
航空器降落問題
最佳化排序
流量管制

英文關鍵字 
Aircraft Landing Problem
Optimal Sequence
Flow Control

學科別分類 

中文摘要 
隨著航空交通量逐年增加，天空變的更加擁擠，使得機場容量不足，加上流量管制，會造成繁忙機場在尖峰時刻班機的延遲，使成本增加。目前航管人員所使用的方法是先到先服務(FirstComeFirstServed)，此方法無法改變飛機的進場順序，可能會造成降落的飛機等待時間過長而產生時間和成本的浪費。此研究在探討以最佳拆解法來加快排程演算法的求解速度，此演算法會將飛機的進場排序來做拆解，透過將進場順序拆解成較小的子集來重新排序進場的飛機，並有兩個主要的目標，第一個目標是要減少演算法的計算時間，透過拆解原始的最佳化問題來減少計算時間，讓我們可以在計算更大的飛機序列時也可以在短時間內完成。第二個目標是希望排序完成的飛機序列可以跟原來的作法一樣是最佳序列。最後會將此演算法與二次規劃算法來做比較，證明其方法的效率以及可行性。

英文摘要 
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 FirstComeFirstServed (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.

論文目次 
摘要 I
ABSTRACT Ⅱ
誌謝 Ⅲ
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
REFERENCES 60

參考文獻 
[1] OAG, "Ontime performance for airlines and airports and TOP 20 busiest routes" 2018.
[2] ACI, "Annual World Airport Traffic Forecasts 2017–2040", 2017.
[3] Schulz, E., "Global Networks, Global Citizens Global Market Forecast 2018  2037", 2018.
[4] 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. 345351, 2004.
[5] ICAO, "CNS/ATM," 1998.
[6] 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. 7190, 1993.
[7] Beasley, J. E., Krishnamoorthy, M., Sharaiha Y. M., and Abramson D., "Scheduling aircraft landings the static case", Transportation Science, vol. 34, No. 2, pp. 180197, 2000.
[8] Bennell, J. A., Potts, C. N., and Mesgarpour, M., "A Review of Airport Runway Optimization", University of Southampton, 2009.
[9] Wen, M., "Algorithms of Scheduling Aircraft Landing Problem,"Department of Informatics and Mathematical Modelling Technical University of Denmark, 2005.
[10] Dear, R. G., "The Dynamic Scheduling of Aircraft in The Near Terminal Area," Flight Transportation Laboratory Massachusetts Institute of Technology Cambridge, 1976.
[11] Dear, R. G., and Sherif, Y. S.,"The Dynamic Scheduling of Aircraft in High Density Terminal Areas," Microelectronics. Reliability, vol. 29, No. 5, pp. 743749, 1989.
[12] 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. 6169, 2015.
[13] 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. 673682, 2011.
[14] Wang, T. C., and Chen, T. C., "Arrival and Departure Aircraft Scheduling with Turbulence Interaction Concept," Journal of Aircraft, vol. 53, No. 5 , 2016.
[15] Wang, T. C., and Tsao, C. H., "TimeBased Separation for aircraft Landing Using Danger Value Distribution Flow Model ," Mathematical Problems in Engineering, vol. 2012, pp. 16, 2012.
[16] FAA, "Air traffic control," 2018.
[17] FAA, "Instrument Flying Handbook, "2001.
[18] CAA, "Air Traffic Management Procedures,"2017.
[19] ICAO, "Air Traffic Management Procedures For Air Navigation Services Doc 4444,"2016.
[20] Nicolaon, J. P., Freville, E., Vidal, A., Crick, P., "Potential Benefits of a Timebased Separation Procedure to maintain the Arrival Capacity of an Airport in strong headwind conditions," no. Fifth USA/Europe Air Traffic Management Research and Development Seminar ,2003.
[21] Balakrishnan, H., and Chandran, B., "Scheduling Aircraft Landings under Constrained Position Shifting ,"AIAA Guidance, Navigation, and Control Conference, Colorado, 2006.
[22] Briskorn, D. and Stolletz, R., "Aircraft landing problems with aircraft classes," Journal of Scheduling, vol. 17, pp. 3145, 2014.
[23] Goldberg, D. E., and Holland, J. H., " Genetic Algorithms And Machine Learning," Machine Learning, vol. 3, pp. 9599, 1988.
[24] Shanno, D. F., and Weil, R. L., " Linear Programming with Absolute Value Functionals," Operations Research, pp.120124, 1971.

論文全文使用權限 
同意授權校內瀏覽/列印電子全文服務，於20240528起公開。同意授權校外瀏覽/列印電子全文服務，於20240528起公開。 


