整合航空客運與貨運之飛航排程暨班次表建立之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：19

、訪客IP：3.135.183.187

姓名

陳宇軒(Yu-Hsuan Chen) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

整合航空客運與貨運之飛航排程暨班次表建立之研究
(An Integrated Model Combine Passengers and Freight for Airline Fleet Routing and Timetable Planning)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

飛航排程對航空業者營運影響甚鉅，其排程之結果不但攸關設備之使用效率、左右班次表之擬訂與人員之調度，更重要的，將進而直接影響及業者之獲利能力、服務水準與市場之競爭能力等。近年來，航空公司在機型上除使用客、貨機以外，開始有使用客貨兩用的機型，其可同時支援客機與貨機的排程規劃。然目前國內業者在實務作業上，主要仍以人工及試誤的方式，規劃客機、貨機及客貨機之排程。做法上首先擬定出客機與客貨機的飛航排程，再根據初擬的客貨機排程，考量市場潛在的貨物需求，進行貨機的排程規劃。繼而修正原先初擬之客貨機排程，以此反覆試誤方式，求得客機、貨機與客貨機三者最終可行之班次表與飛航排程。由於此方法不具系統性分析，以致無法有效掌握客機、貨機與客貨機排程間之相關性，因此其排程之效率常易隨系統規模之增大而降低，進而導致營運績效之不佳。
緣此，本研究以航空業者立場，在給定的營運資料下，包括機隊規模、航權、可用時間帶、相關飛航成本等，以營運利潤最大化為目標，並考量相關營運限制，構建一整合客機、貨機與客貨機的飛航排程模式。此模式能於未來實務的應用上，提供航空業一短期排程暨班次表建立之輔助規劃工具。本研究利用網路動技巧構建模式，模式中含有多個人流、物流與機流時空網路，以定式旅客、貨物與飛機在時空中的流動情況。此模式可定式為一整數多重貨物網路流動問題，屬NP-hard問題，尤其是應用於實際問題時，規模甚為龐大，在求解上更難於以往傳統之飛航排程規劃問題。為有效求解大規模問題，本研究利用拉氏鬆弛法暨次梯度法、網路單體法、及自行發展之啟發式解法，配合數學規劃軟體CPLEX求解模式。最後，為測試模式及求解演算法之績效，本研究以一國籍航空公司之營運資料為例，進行測試與分析，進而提出結論及建議。

摘要(英)

Fleet routing and flight scheduling are important in airline operations. They always affect the usage efficiency of facilities and crew scheduling. Furthermore, they are essential to carriers’ profitability, level of service and competitive capability in the market. Recently, besides passenger flights and cargo flights, some airlines introduced combi flights in their flight scheduling. The combi flights combine passengers and cargos in one flight and can supple passenger flights and cargo flights during a carrier’s regular operation. However, the carriers in Taiwan currently adopt a try-and-error method to determine the schedules of passenger flights, cargo flight and combi flights. The method starts by manually determining the passenger and combi flight schedules together. Based on the passenger and combi flight schedules and the projected cargo demand, the cargo flight schedule is then determined. Thereafter, the combi flight schedule is modified by considering the cargo flight schedule and the passenger flight schedule is revised in accordance with the combi flight schedule. The process is repeated until the final fleet routing and timetables are obtained. Since such a method without systemic analyses cannot effectively manage the interrelationship among the passenger, cargo and combi flight schedules, the performance of the obtained schedules would easily decrease as the system scale is enlarged. As a result, the operating performance could possibly be inferior.
Therefore, given the operating data, including fleet size, airport flight quota and available time slots, related flight cost, on the basis of the carrier’s perspective, this research tries to develop a scheduling model by integrating passenger, cargo and combi flight schedules, with the objective of maximizing the operating profit, subject to the related operating constraints. The model is a useful planning tool for airlines to determine a suitable fleet routing and timetables in their short-term operations. We employ network flow techniques to construct the model, which include passenger-flow, cargo-flow and fleet-flow networks in order to formulate the flows of passengers, cargos and fleet in the dimensions of time and space. The model is formulated as an integer multiple commodity network flow problem that is characterized as an NP-hard problem. Since the real problem size is huge, this model is harder to solve than the conventional passenger flight scheduling problems in the past. A Lagrangian relaxation-based algorithm, coupled with a subgradient method, the network simplex method and a heuristic for upper bound solution, is suggested to solve the problem. Finally, to evaluate the model and the solution algorithm, we perform a case study by using the real operating data from a major Taiwan airline.

關鍵字(中)

★ 拉氏演算法
★ 多重貨物網路流動問題
★ 時空網路
★ 客貨機
★ 飛航排程

關鍵字(英)

★ Lagrangian relaxation-based algorithm
★ fleet routing
★ combi flight
★ time-space network
★ multiple commodity network flow problem

論文目次

第一章緒論 1
1.1研究背景與動機 1
1.2研究目的與範圍 2
1.3研究方法與程式架構 3
第二章文獻回顧 4
2.1短期航空排程相關文獻 4
2.2分解式演算法（DECOMPOSITION ALGORITHM）求解模式相關文獻 7
2.3小結 10
第三章模式構建 11
3.1模式假設 11
3.2模式架構 13
3.2.1網路設計考量因素 13
3.2.2機流時空網路 16
3.2.3人流時空網路 22
3.2.4物流時空網路 25
3.2.5排程營運限制 28
3.3數學定式 29
3.3.1符號說明 29
3.3.2數學定式 30
3.4小結 33
第四章求解演算法設計 34
4.1 演算法一(FF) 35
4.1.1 目標值下限 36
4.1.2 目標值上限解 39
4.1.3 收斂機制 45
4.2 演算法二(PF) 47
4.3單機定線 53
4.4 其他演算法說明 54
4.5 小結 54
第五章實例研究 55
5.1 輸入資料 55
5.1.1航線資料 55
5.1.2機場起降時間帶及航權限制 57
5.1.3航機種類及機隊規模 59
5.1.4起迄資料 60
5.1.5成本資料 61
5.1.6運價資料 63
5.2 輸出資料 64
5.2.1 實例結果輸出 64
5.2.2 測試例結果輸出 68
5.3 單機定線 75
5.4 敏感度分析 77
5.4.1 票價 77
5.4.2 旅次需求 81
5.5 小結 85
第六章結論與建議 86
6.1結論 86
6.2 建議 87
6.3 貢獻 87
參考文獻 88
附錄一 CPLEX CALLABLE LIBRARY CODE 91

參考文獻

1. 朱純孝，「考慮旅客偏好下航空公司班表與票價訂定之研究」，碩士論文，國立成功大學交通運輸管理系，1999。
2. 余秀梅，「多元商品模式應用在動態貨櫃調度問題之研究」，碩士論文，國立成功大學交通管理科學研究所，1994。
3. 陳世欽，「多時效性貨物需求下飛航排程暨班次表建立之研究」，碩士論文，國立中央大學土木工程學系，2003。
4. 黃武強，「配合空運中心之客運航線與頻次規劃研究」，碩士論文，國立中央大學土木工程研究所，1995。
5. 劉得昌，「國內航線旅次需求型態推估與班次起飛時間之訂定」，博士論文，國立交通大學交通運輸研究，2000。
6. 劉得昌，「實用班機排程方法」，碩士論文，國立交大交通運輸研究所，1993。
7. 顏上堯、杜宇平、陳怡妃，「因應臨時事件機場共用櫃檯即時指派之研究」，「民航學會/ 航太學會/ 燃燒學會」學術聯合會議研討會論文集，2002。
8. 顏上堯與王中瑞，「飛航網路定線與班次頻次數之規劃」，中華民國運輸學會第十屆論文研討會論文集，1995。
9. 顏上堯與何淑萍，「飛航排程暨班次表之建立」，運輸計劃季刊，第二十三卷，第一期，第73-90頁，1994。
10. 顏上堯與翁綵穗，「季節轉換間緩衝期飛航排程之研究」，運輸計劃季刊，第三十卷，第四期，第891-922頁，2001。
11. 顏上堯與曾志煌，「單機種機隊排程與班次整合之研究」，運輸計劃季刊，第二十八卷，第四期，第635-658頁，1999。
12. 顏上堯與楊慧華，「多機種飛航排程規劃」，運輸計劃季刊，第二十四卷，第二期，第195-220頁，1995。
13. Abara, J., “Applying Integer Linear Programming to the Fleet Assignment Problem,” Interfaces, Vol. 19, pp. 20-28, 1989.
14. Agin, N. and Cullen, D., “An Algorithm for Transportation Routing and Vehicle Loading,” in Geisler, M. (Ed.), Logistics, pp.1-20, North Holland, Amsterdam, 1975.
15. Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P. and Vance, P. H., “Branch-and-Price: Column Generation for Solving Huge Integer Programs,” Operations Research, Vol. 46, pp. 316-329, 1998.
16. Benders J. F., “Partitioning Procedures for Solving Mixed-variables Programming Problems,” Numerische Mathematik, 4:238-252, 1962.
17. Camerini, P. K., Fratta, L. and Maffioli, F., “On Improving Relaxation Methods by Modified Gradient Techniques,” Mathematical Programming Study, Vol. 3, pp. 6-25, 1975.
18. Carter, E. C. and Morlok, E. K., “Planning An Air Transport Network in Appalachia,” Transportation Engineering Journal of ASCE, Vol. 101, pp. 569-588, 1972.
19. Chen, C. Y. and Kornhauser, A. L., ”Decomposition of Convex Mulitcommodity Network Flow Problem,” Report SOR-90-19, Dept. of Civil Engineering and Operations Research, Princeton University, Princeton, NJ, 1990.
20. Chih, K. C. K., “A Real Time Dynamic Optimal Freight Car Management Simulation Model of Multiple Railroad, Mulitcommodity Temporal Spatial Flow Problem,” Ph.D. Dissertation, Princeton University, Princeton, NJ, 1986.
21. Clarke, L.W., Hane, C. A., Johnson, E. L. and Nemhauser, G. L., “Maintenance and Crew Considerations in Fleet Assignment,” Transportation Science, Vol.30, pp. 249-260, 1996.
22. Desaulniers, G., Desrosiers, J., Dumas Y., Solomon, M. M. and Soumis, F., “Daily Aircraft Routing and Scheduling,” Management Science, Vol. 43, pp. 841-855, 1997.
23. Dobson, G. and Lederer, P. J., “Airline Scheduling and Routing in a Hub-and-spoke System,” Transportation Science, Vol. 27, No. 3, pp. 281-297, 1993.
24. Fisher, M. L., “The Lagrangian Relaxation Method for Solving Integer Programming Problem,” Management Science, Vol. 27, pp. 1-18, 1981.
25. Hane, C. A., Barnhart, C., Johnson, E. L., Marsten, R., Nemhauser, G. L. and Sigismondi, G., “The Fleet Assignment Problem: Solving a Large-Scale Integer Program,” Mathematical Programming Study, Vol. 70, pp. 211-232, 1995.
26. Kennington, J. L. and Shalby, M., “An Effective Subgradient Procedure for Minimum Cost Multicommodity Flow Problem,” Management Science, Vol.23, pp.994-1004, 1997.
27. Kennington, J. L. and Helgason, R. V., “Algorithms for Network Programming,” Wiley, NJ, 1980.
28. Lamatsch, A, “An Approach to Vehicle Scheduling with Depot Capacity Constraints,” in Desrochers, M. and Rousseau, J. M.（eds.）, Computer Aided Transit Scheduling, Lecture Notes in Economics and Mathematical System 386, Springer Verlag, Berlin, Heidelberg, pp. 181-195, 1992.
29. Lee, B. C., “Routing Problem With Service Choices, Flight Transportation Laboratory,” Report R86-4, Massachusetts Institute of Technology, MA, 1986.
30. Levin, A., “Scheduling and Fleet Routing Models for Transportation Systems,” Transportation Science, Vol. 5, pp. 232-255, 1971.
31. Levin, A., “Some Fleet Routing and Scheduling Problems for Air Transportation Systems,” Flight Transportation Laboratory Report R68-5, Massachusetts Institute of Technology, MA, 1969.
32. Mesquita, M. and Paixao, J., “Multiple Depot Vehicle Scheduling Problem: a New Heuristic Based on Quasi-Assignment Algorithm,” in Desrochers, M. and Rousseau, J. M.（eds.）, Computer Aided Transit Scheduling, Lecture Notes in Economics and Mathematical System 386, Springer Verlag, Berlin, Heidelberg, pp. 181-195, 1992.
33. Powell, W. B. and Ioannis, A. K., “Shipment Routing Algorithms with Tree Constraints,” Transportation Science, Vol. 26, pp. 230-245, 1992.
34. Shan, Y. S., “A Dynamic Mulitcommodity Network Flow Model for Real Time Optimal Real Freight Car Management,” Ph.D. Dissertation, Princeton University, Princeton, NJ, 1985.
35. Simpson, R. W., “A Review of Scheduling and Routing Model for Airline Scheduling,” IX AGIFORS Symposium Broadway, England, 1969.
36. Teodorovic, D., “Airline Operations Research,” Gordon and Breach Science Publishers, New York, 1988.
37. Teodorovic, D. and Guberinic, S., “Optimal Dispatching Strategy on an Airline Network after a Schedule Perturbation,” European Journal of Operational Research 15, 178-182, 1984.
38. Teodorovic, D., “Multiattribute Aircraft Choice for Airline Networks,” Journal of Transportation Engineering, Vol. 112, pp. 634-646, 1986.
39. Yan, S. and Yang, D., “A Decision Support Framework for Handling Schedule Perturbation,” Transportation Research, Vol.30B, 405-419, 1996.

指導教授

顏上堯(Shang-Yao Yan)

審核日期

2004-7-16

推文