隨機性班機延誤下整合性機門指派模式與求解演算法之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：51

、訪客IP：3.145.56.150

姓名

賴奕杉(Yi-Shan Lai) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

隨機性班機延誤下整合性機門指派模式與求解演算法之研究
(An Approach for Conformity Airport Gate Assignments for Stochastic Flight Delays And Decomposition Algorithm)

相關論文

★ 橋梁檢測人力機具排班最佳化之研究	★ 勤業務專責分工下消防人員每日勤務排班最佳模式之研究
★ 司機員排班作業最佳化模式之研究	★ 科學園區廢水場實驗室檢驗員任務指派最佳化模式之研究
★ 倉儲地坪粉光工程之最佳化模式研究	★ 生下水道工程工作井佈設作業機組指派最佳化之研究
★ 急診室臨時性短期護理人力指派最佳化之探討	★ 專案監造人力調派最佳化模式研究
★ 地質鑽探工程人機作業管理最佳化研究	★ 職業棒球球隊球員組合最佳化之研究
★ 鑽堡於卵礫石層施作機具調派最佳化模式之研究	★ 職業安全衛生查核人員人力指派最佳化研究
★ 救災機具預置最佳化之探討	★ 水電工程出工數最佳化之研究
★ 石門水庫服務台及票站人員排班最佳化之研究	★ 空調附屬設備機組維護保養排程最佳化之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在整個機場的營運作業中，機門指派在機場的營運效率與服務水準上扮演關鍵性的角色。然而機場實際營運中，時常發生班機隨機到離延誤的情形，當延誤導致班機使用機門時間有衝突時，目前國內則以人工方式進行重新指派動作，此人工經驗為主的指派方式，在班次密集的尖峰時段將不能確定其指派效率與績效。因此若能在規劃時期考量實際營運時班機隨機延誤的特性，提供規劃人員較符合實際擾動之指派結果，使其在實際營運中不受到大幅擾動，增加在實際營運的適用性，將是一個相當重要的課題。本研究將以機場營運者為立場，考量實際營運時班機隨機到離延誤之特性，發展出整合靜態規劃與即時階段之求解架構，其中包含以完全資訊為概念發展完全資訊模式，進一步以完全資訊模式為概念，考量即時階段班機指派時間順序發展隨機性模式。期望能幫助機場相關人員有效地考量班機隨機延誤擾動下的規劃指派結果，進而提升機門指派作業之整體績效。
本研究除了發展兩整合模式，並進一步探討理論上整合問題之最佳性。此外，本研究在完全資訊模式以數學規劃軟體求解中小型問題，但兩模式之大型問題規模龐大，因此以分解式演算法的概念針對兩模式特性發展有效的求解演算法，且對完全資訊模式以劃分問題的方式發展下限解演算法，並相同以劃分問題方式發展上限解演算法，配合數學規劃軟體進行求解。其次，隨機性模式為一非線性零壹整數規劃問題，因此同樣以分解式演算法為基礎，以隨機事件為考量發展分解式演算法，再配合數學規劃軟體進行求解。最後，本研究以台灣桃園國際機場為例，進行範例測試與分析，結果甚佳，顯示本研究所建構知模式與求解方法應可為未來機場當局之參考。

摘要(英)

The assignment of flights to gates is essential to an airport，s operation and level of service. However, stochastic flight delays often occur in real world. The aircraft may not be assigned to the planned gate due to the stochastic flight delays in real operations. As a result, an airport staff has to reassign flights to gates in real-time operations and the actual performance of the original assignments could be reduced. Therefore, considering of stochastic flight delays is necessary in actual operations. It also helps airport authority to handle the assignment of flights to gates and improve the performance of gate assignment problem. A integrated framework which contain the gates planning and the real-time stages, is introduced to solve the stochastic programming problem. We develop the perfect information model and the gate reassignment model base on a integrated framework. The two models solve the stochastic flight delay. First, the perfect information model is established based on the concept of perfect information. Second, the stochastic model considers of prioritize time of the flight assignment. It is expected to that this is a useful tool for authorities to effectively handle gates reassignment and thus enhance current airport operation.
We also study optimality of integrated problems except for developing two models. Besides, the two models could not solve large-scale problems optimally by using mathematics programming software. In order to solve large-scale problems efficiently, we develop decomposition algorithms each for these two models. The stochastic model is nonlinear mathematics programming program. The preliminary results are good, showing that the models could be useful for a Taiwan international airport.

關鍵字(中)

★ 擾動
★ 分解式演算法
★ 班機隨機到離延誤
★ 機門指派

關鍵字(英)

★ Decomposition algorithm
★ Gate assignment
★ Disturbances
★ Stochastic flight delays

論文目次

中文摘要 I
ABSTRACT II
誌謝 III
目錄 IV
圖目錄 VII
表目錄 IX
第一章緒論 1
1.1研究背景與動機 1
1.2研究目的與範圍 2
1.3研究方法與流程 3
第二章文獻回顧 5
2.1機門指派之相關研究 5
2.2規劃性隨機處理相關研究 6
2.3隨機規劃問題 8
2.3.1兩階段規劃問題(Two-Stage Programming Problem) 8
2.3.2分佈問題(Distribution Problem)與機會限制規劃問題 (Chance-Constrained Programming Problem) 11
2.3.3完全資訊期望價值(The Expected Value of Perfect Information, EVPI)與隨機解價值(The Value of the Stochastic Solution, VSS) 13
2.4即時性擾動相關研究 15
2.5 分解式演算法相關文獻 16
2.6文獻評析 17
第三章模式建構 19
3.1問題描述 19
3.2完全資訊模式 23
3.2.1完全資訊模式設計概念與模式假設 23
3.2.2完全資訊模式數學定式 24
3.3隨機性模式 35
3.3.1隨機性模式設計概念 36
3.3.2隨機性模式數學定式 36
3.4 小結 40
第四章求解演算法設計 41
4.1 完全資訊模式求解演算法架構 41
4.2 完全資訊模式下限解之求解演算法架構 46
4.3 隨機性模式之求解演算法架構 50
4.4評估分析 56
4.5 小結 57
第五章範例測試 58
5.1 資料分析 58
5.1.1 機門使用狀況 58
5.1.2 飛航機型與航次組合 59
5.1.3 班機延誤 60
5.2 電腦演算發展 60
5.2.1 問題規模 60
5.2.2 模式輸入資料 61
5.3 電腦演算環境及設定 62
5.3.1 電腦演算環境 62
5.3.2 相關程式設定 62
5.3.3 模式輸出資料 62
5.4 測試結果與分析 63
5.4.1 啟發解法績效評估 63
5.4.2 隨機事件數目 64
5.4.3 不同營運日比較分析 67
5.5 敏感度分析 68
5.5.1班機規劃之時間擾動權重敏感度(即為與 ) 68
5.5.2 機門指派空間擾動值敏感度(即為與 ) 73
5.6 方案分析 77
5.6.1 班機最大容許延遲指派時間 78
5.6.2 機門指派空間擾動計算方式 81
5.7 小結 83
第六章結論與建議 85
6.1 結論 85
6.2 建議 86
6.3 貢獻 86
參考文獻 88
附錄 92
附錄一機門指派空間擾動值以更換機門次數為計算方式 92
附錄二 2004年9月24日台灣桃園國際機場客運飛航資料表 93
附錄三班機到離延誤分佈型態 96
附錄四班機變動率之計算流程圖 98

參考文獻

1. 汪進財，「機門指派最佳化模式」，運輸計劃季刊，第21卷，第2期，頁247-260，1992。
2. 汪進財、張束珍，「動態機門指派績效評估」，運輸計畫季刊，第25卷，第1期，頁121-144，1996。
3. 汪進財、盧清泉，「臨時飛航事件班機調度因應策略之研究」，運輸計劃季刊，第25卷，第2期，第255-288 頁，1996。
4. 林益生，「隨機環境下多商品、多車種派車問題之研究」，中原大學工業工程學系碩士論文，1998。
5. 侯育周，「隨機性班機到離延誤下動態機門指派之研究」，國立中央大學土木工程學系碩士論文，2007。
6. 陳春益、李宇欣、盧華安，「時空網路應用於機門指派問題之研究」，運輸學刊，第10卷，第3期，頁1-20，1997。
7. 游俊雄、丁國樑「需求反應旅次運載模擬模式應用於捷運營運班表之評估」，運輸計劃季刊，第27卷，第3期，頁489-508，1998。
8. 盧華安，「因應班機延遲之最佳化即時機門指派」，運輸計劃季刊，第30卷第4期，頁849-870，2001。
9. 顏上堯、杜宇平、朱橋榮，「機門數量最少化網路模式之研究」，運輸學刊，第15卷，第2期，頁149-164，2003。
10. 顏上堯、杜宇平、陳怡妃，「因應臨時事件機場共用櫃檯即時指派之研究」，「民航學會/ 航太學會/ 燃燒學會」學術聯合會議研討會論文集，2002。
11. 顏上堯、林忠機，「因應機場突然且暫時關閉之系統性飛航排程」，運輸計畫季刊，第25卷，第2期，頁289-316，1996。
12. 顏上堯、張家銘，「機門指派最佳化之研究」，中國土木水利學刊，第9卷，第3期，頁491-500，1997。
13. 顏上堯、謝宗男，「航空公司意外事件排程與營運擾動之研究」，中華民國運輸學會第15屆論文研討會論文集，2000。
14. 顏上堯、羅智騰，「因應預期性航具維修之系統性飛航排程」，中國土木水利工程學刊，第8卷，第3期，頁447-456，1996。
15. 顏上堯、齊志仁、湯慶輝，「隨機需求下多目標長途客運排程模式之研究」，運輸計畫季刊，第 34卷第 1 期，第93-118頁，2005。
16. Agin, N. and Cullen, D., “An Algorithm for transportation routing and vehicle loading,” Logistics, pp.1-20, North Holland, Amsterdam (1975).
17. Ali, H. and Oh, S.C., “Formulation and solution of a multi-commodity, multi-modal network flow model for disasterrelief operations,” Transportation Research A, Vol. 30, No. 3, pp. 231-250, 1996.
18. Arguello, M.F., Bard, J.F. and Yu, G., "A GRASP for aircraft routing in response to groundings and delays," Journal on Combinatorial Optimization, Vol. 5, pp. 211-228, 1997.
19. Arguello, M.F., Bard, J.F. and Yu, G., "Models and methods for managing airline irregular operations aircraft routing," In G. Yu(ed) , Operations Research in Airline Industry, Kluwer Academic Publishers, Boston, 1997.
20. Anne, M., Cordeau, J. F. and Fran.cois, S., "A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem," Computers & Operations Research Vol. 32, pp.1451–1476,2005
21. Babic, O., Teodorovic, D. and Tosic, V., “Aircraft stand assignment to minimize walking,” transportation engineering, Vol. 110, pp. 55-66, 1984.
22. Berman, O, Larson, R.C. and Chiu, S.S., “Optimal server location on a network operating as a M/G/1 queue,” Operations Research, Vol. 33, pp. 746-770, 1985.
23. Birge, J.R., “Exhausitable recourse models with uncertain returns from exploration investment,” in Ermoliev, Y. and Wets, R. (Ed.), Numerical Techniques for Stochastic Optimization, pp. 481-488, Springer-Verlag, Berlin, 1988.
24. Birge, J.R. and Louveaux, F.V., Introduction to stochastic programming, Springer-Verlag, New York, 1997.
25. Chao, H.P., “Exhaustible resourse models: the value of information,” Operation Research, Vol 29, pp. 903-923, 1981.
26. Charnes, A., Cooper, W.W., Symonds, G.H., “Cost horizons and certainty aquivalents: an approach to stochastic programming of heating oil,” Management Science, Vol. 4, pp.235-263, 1958.
27. Cheng, Y.,”A knowledge-based airport gate assignment system integrated with mathematical programming,” Computers Ind. Eng., Vol. 32,pp. 837-852,1997.
28. Escudero, L.F., Kamesam, P.V., King, A.J., Wets, R.J.-B., “Production planning via scenario modeling,” Annals of Operations Research, Vol. 43, pp. 311–335, 1993.
29. Gosling, G..D., “Design of an expert system for aircraft gate assignment,” Transportation Research, Vol. 24A, pp. 59-69, 1990.
30. Healy, P., “A tool for adjusting the flight schedule during high volume irregular operations,” AGIFORS 32, 1992.
31. Jaillet, P., “A priori solution of a traveling salesman problem in which a random subset of the customers are visited,” Operations Research, Vol. 36, pp. 929-936, 1988.
32. Jarrah, A.I., Yu, G., Krishnamurthy, N. and Pakshit, A., “A decision support framework for airline flight cancellations and delays,” Transportation Science, Vol.27, 1993.
33. Kenyon, A.S. and Morton, D.P., “Stochastic vehicle routing with random travel times,” Transportation Science, Vol. 37, No. 1, pp. 69-82, 2003.
34. List, G.F., Wood, B., Nozick, L.K., Turnquist, M.A., Jones, D.A., Kjeldgaard, E.A. and Lawton, C.R., “Robust optimization for fleet planning under uncertainty,” Transportation Research, part E, Vol. 39, pp. 209-227, 2003.
35. Louveaux F.V. and Smeers, Y., “Stochastic optimization for the introduction of a new energy technology,” Stochastics, 1997.
36. Mangoubi, R.S. and Mathaisel, D.F.X., “Optimizing gate assignment at airport terminals,” Transportation Science, Vol. 19, No. 2, pp. 173-188, 1985.
37. Manne, A.S., “Waiting for the breeder,” Review of Economic Studies Symposium, pp.47-65, 1974.
38. Mulvey, J., Ruszczynski, A., “A new scenario decomposition method for large-scale stochastic optimization,” Operations Research, Vol. 43, No. 3, pp. 477–490, 1995.
39. Mulvey, J.M., Vanderbei, R.J., Zenios, S.A., “Robust optimization of large-scale systems,” Operations Research, Vol. 43, No. 2, pp. 254–281, 1995.
40. Nakazawa, S., “Dynamic scheduling in operation control system,” AGIFORS 31, 1991.
41. Perl J. and Daskin MS. “A warehouse location problem.” Transportation Research B Vol. 19B, No. 5, pp. 381-396, 1985
42. Simpson, R.W., “A review of scheduling and routing model for airline scheduling,” IX AGIFORS Symposium, Broadway, England (1969).
43. Stancu-Minasian, I.M., “Stochastic programming with multiple objective functions,” Editura Academiei, Bucharest, 1984.
44. Soteriou, A.C. and Chase, R.B., “A robust optimization approach for improving service quality,” Manufacturing & Service Operations Management, Vol. 2, No. 3, pp.264–286, 2000.
45. Su, Y.Y. and Srihari, K., “A knowledge based aircraft-gate assignment advisor,” Comps and Ind. Eng., Vol. 25, pp.123-126, 1993.
46. Teodorovic, D. and Stojkovic, G.., “Model for operational daily airline scheduling,” Transportation Planning and Technology, Vol.14, pp.273-285, 1990.
47. Thengvall, B.G., Bard, J.F. and Yu, G., “Balancing user preferences for aircraft schedule recovery during airline irregular operations,” IIE Transactions on Operations Engineering, Vol. 32, pp.181-193, 2000.
48. Thengvall, B.G., Yu, G. and Bard, J.F, “Multiple fleet aircraft schedule recovery following hub closure,” Transportation Research, Vol.35A, pp.289-308, 2001.
49. Wu,T.H., Chinyao, L. and Bai, J.W., “Heuristic solutions to multi-depot location-routing problems,” Computers & Operations Research, Vol. 29, No. 10, pp. 1393-1415, 2002.
50. William, L., C., and Tito, Homem-de-Mello., “Some decomposition methods for revenue management,” Transportation Science, Vol. 41, p. 332, 2007.
51. Vanderstraetan, G. and Bergeron, M., “Automatic assignment of aircraft to gates at a terminal,” Computers and Industrial Engineering, Vol. 14, pp. 15-25, 1988.
52. Yan, S and Huo, C.M., “Optimization of multiple objective gate assignments,” Transportation Research, Vol. 35A, pp. 413-432, 2001.
53. Yan, S. and Lin, C., “Airline scheduling for the temporary closure of airports,” Transportation Science, Vol.31, pp.72-82, 1997.
54. Yan, S. and Tang, C.H., “A heuristic approach for airport gate assignments for stochastic flight delays,” European Journal of Operational Research, Vol. 180, 2, pp. 547-567, 2007
55. Yan, S. and Tu, Y., “Multi-fleet routing and multi-stop flight scheduling for schedule perturbation,” European Journal of Operational Research, Vol.103, pp.155-169, 1997.
56. Yan, S. and Yang, D., “A decision support framework for handling schedule perturbation,” Transportation Research, Vol. 30B, 405-419, 1996.
57. Yan, S. Shieh, C. and Chen, M., “A simulation framework for evaluating airport gate assignments,” Transportation Research, Vol. 36A, pp.885-898, 2002.
58. Yan, S., Tang, C., and Shieh, C., “A simulation framework for evaluating airline temporary schedule adjustments following incidents,” Transportation Planning and Technology, Vol. 28, pp.189-211.2005.
59. Yan, S., Tang, C.H., and Chen, C.H., “Reassignments of common-use checking counters following airport incidents,”Journal of Operational Research Society , 2006
60. Yan, S., Chen, S. C. and Chen, C. H., “Air cargo fleet routing and timetable setting with multiple on-time demands,” Transportation Research Part E, Vol. 42, pp. 409–430, 2006a.
61. Yan, S., Chi, C. J. and Tang, C. H., “Inter-city bus routing and timetablesetting under stochastic demands,” Transportation Research Part A, Vol. 40, pp. 572–586, 2006b.
62. Yu, C. and Li, H., “A robust optimization model for stochastic logistic problems,” International Journal of Production Economics, Vol. 64, pp. 385–397, 2000.
63. Yu, Gu., and Christopher, A.C., “Genetic algorithm approach to aircraft gate reassignment problem,” Journal of Transportation Engineering, Vol. 125, Issue 5, pp. 384-389, 1999.

指導教授

顏上堯(Shang-Yao Yan)

審核日期

2008-7-23

推文