整合供需面飛航排程暨班次表規劃之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：10

、訪客IP：18.191.28.133

姓名

曾志煌(Jyh-Hwang Tseng) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

整合供需面飛航排程暨班次表規劃之研究
(An Integrated Model for Airline Fleet Routing and Timetable Planning)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

本研究因而以數學規劃方法構建一直截整合旅次需求與航次供給之多機種多停靠飛航排程模式，並進一步發展其求解演算法，以幫助業者求得最佳的機隊排程與班次表。本研究模式係以多重時空網路來定式人旅次流動與飛機流動，是為一較特殊之整數多重貨物網路流動問題；數學上係屬於NP-hard 性質之問題。研究中係利用拉氏鬆弛法、次梯度法、網路單體法、流量分解法與最小成本流量推擠法等綜合發展一拉氏演算法（Lagrangian relaxation-based algorithm）求解；另本研究以一本國航空公司之國內客運營運資料進行模式之實證，並以C語言撰寫電腦演算法與實證架構。模式實證之收斂效果尚稱理想，期能於未來實務應用上提供航空業者作為有效改善營運績效之輔助規劃工具。

摘要(英)

This research therefore developed an integrated model and a solution algorithm to help carriers simultaneously solve for better fleet routes and proper timetables. In order to directly manage the interrelationships between trip demand and flight supply, a time-space network technique was applied to modeling the movements of aircraft and passenger flows. Mathematically, the model was formulated as a special integer multiple commodity network flow problem which was categorized as an NP-hard problem. A Lagrangian relaxation-based algorithm was developed to efficiently solve the problem on the basis of Lagrangian relaxation, the sub-gradient method, the network simplex method, the least cost flow augmenting algorithm and the flow decomposition algorithm. To show how well the model and the solution algorithm could be applied in the real world, a case study regarding the domestic operations of a major Taiwan airline was performed by using the C computer language. The admirable outcome has shown the model’s good performance. Presumably, the results are practically helpful for airlines in Taiwan to improve their operations.

關鍵字(中)

★ 時空網路
★ 整數多重貨物網路流動問題
★ 拉氏鬆弛法
★ 最小成本流量推擠法

關鍵字(英)

★ time-space network
★ integer multiple commodity network flow problem
★ Lagrangian relaxation
★ the least cost flow augmenting algorithm

論文目次

封面
摘要
Abstract
誌謝
章節目錄
表目錄
圖目錄
第一章　緒論
１．１　研究背景與動機
１．２　研究目的與範圍
１．３　研究方法與流程
第二章　文獻回顧
２．１　模式建立類
２．２　模式求解類
２．３　其他類
２．４　小結
第三章　模式建立
３．１　模式架構
３．２　模式假設
３．３　模式組成
３．４　數學定式
３．５　網路設計
３．６　小結
第四章　模式求解
４．１　模式存在理論最佳解
４．２　求解架構
４．３　求解目標值下限
４．４　求解目標值上限
４．５　收斂機制
４．６　單機定線
４．７　正確解求解測試
４．８　小結
第五章　實例研究
５．１　輸入資料
５．２　輸出資料
５．３　敏感度分析
５．４　模式應用
５．５　小結
第六章　結論與建議
６．１　結論
６．２　貢獻
６．３　建議
附錄

參考文獻

1. 中華航空公司八十五年度年報，CHINA AIRLINES ANNUAL REPORT 1996，台北，民國八十六年。
2.「民用航空器使用航空站、飛行場及助航設備收費標準」，交通部，民國八十四年。
3. 杜宇平，航具暫時短缺時多機種飛航排程，國立中央大學土木工程研究所碩士論文，民國八十三年六月。
4. 沈志展，民航空運排程分析模式之應用，國立交通大學交通運輸研究碩士論文，民國八十年六月。
5. 林信得、凌鳳儀，「航空運輸學」，文笙書局，台北，民國八十二年。
6.「南部國際機場發展計畫」，交通部運輸研究所，台北，民國八十二年。
7. 凌鳳儀，「航空運輸總論」，文笙書局，台北，民國八十七年。
8.「國內航線機場時間帶管理實施要點」，交通部民用航空局，民國八十四年。
9.「國內機場航空器起降額度管理要點」，交通部民用航空局，民國八十六年。
10. 黃武強，配合空運中心之客運航線與頻次規劃研究，國立中央大學土木工程研究所碩士論文，民國八十四年六月。
11. 賈凱傑、陳齊邦，「開放天空政策下國內空運市場的競爭障礙」，中華民國運輸學會第十四屆論文研討會論文集，民國八十八年十二月。
12.「運輸資料分析」，交通部運輸研究所，台北，民國八十六年。
13. 劉得昌，實用班機排程方法，國立交通大學交通運輸研究所碩士論文，民國八十二年六月。
14. 顏上堯、何淑萍，「飛航排程暨班次表之建立」，運輸計劃季刊，第二十三卷，第一期，第73-90頁，民國八十三年。
15. 顏上堯、楊大輝，「航空運具故障時系統性飛航排程」，運輸計劃季刊，第二十三卷，第四期，第407-426頁，民國八十三年。
16. 顏上堯、楊慧華，「多機種飛航排程規劃」，運輸計劃季刊，第二十四卷，第二期，第195-220頁，民國八十四年。
17. 顏上堯、林忠機，「因應機場突然且暫時關閉之系統性飛航排程」，運輸計劃季刊，第二十五卷，第二期，第289-316頁，民國八十五年。
18. 顏上堯、羅智騰，「因應預期性航具維修之系統性飛航排程」，中國土木水利工程學刊，民國八十五年。
19. 顏上堯，王中瑞(a)，「飛航定線與班次表之建立」，八十四年電子計算機於土木水利工程應用論文研討會論文集，第907-918頁，中壢，民國八十四年。
20. 顏上堯、王中瑞(b)，「飛航網路定線與班次頻次數之規劃」，中華民國運輸學會第十屆論文研討會論文集，第57-63頁，台北，民國八十四年。
21. 顏上堯、曾志煌，「飛航排程與班次表整合規劃模式之建立」，中華民國運輸學會第九屆論文研討會論文集，第231-237頁，台北，民國八十三年。
22. 顏上堯、曾志煌，「單機種機隊排程與班次整合之研究」，運輸計劃季刊，第二十八卷，第四期，第635-658頁，民國八十八年。
23. Abara, J., “Applying Integer Linear Programming to the Fleet Assignment Problem”, Interfaces, Vol. 19, pp.20-28, 1989.
24. 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.
25. Ahuja, R. K., Magnanti, T. L. and Orlin, J. B., Network Flows, Theory, Algorithms, and Applications, Prentice Hall, New Jersey, 1993.
26. Balakrishnan, A., Chien, T. W. and Wong, R. T., “Selecting Aircraft Routes for Long-Haul Operations: A Formulation and Solution Method”, Transportation Research, Vol. 24B, pp. 57-72, 1990.
27. Ball, M. O., Magnanti, T. L., Monma, C. L. and Nemhauser, G. L., “Network Routing”, Handbooks in Operations Research and Management Science, Vol. 8, 1995.
28. 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”, Operation Research, Vol. 46, pp. 316-329, 1998.
29. 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.
30. 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.
31. 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.
32. De Vany, A. S. and Garges, E. H., “A Forecast of Air Travel and Airport and Airway Use in 1980”, Transportation Research, Vol. 6, pp. 1-18, 1972.
33. 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.
34. Etschmaier, M. and Mathaisel, D., Aircraft Scheduling : The State of the Art. AGIFORS XXIV, pp.181-209, 1984.
35. Fisher, M. L., “The Lagrangian Relaxation Method for Solving Integer Programming Problem”, Management Science, Vol. 27, pp. 1-18, 1981.
36. Fisher, M. L., “An Application Oriented Guide to Lagrangian Relaxation”, Interfaces, Vol. 15, pp.10-21, 1985.
37. Garey, M. R. and Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman & Company, San Francisco, 1979.
38. Ghobrial, A. A., Analysis of the Air Network Structure: The Hubbing Phenomenon. Ph.D. Dissertation, University of California, Berkeley, 1983.
39. Gordon,W. and de Neufville, R., “Design of Air Transportation Networks”, Transportation Research, Vol. 7, pp. 207-222, 1973.
40. 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.
41. Hyman, W. and Gordon, L., “Commercial Airline Scheduling Technique”, Transportation Research, Vol. 12, pp. 23-29, 1978.
42. Jarrah, A. I., Yu, G., Krishnamurthy, N. and Rakshit, A., “A Decision Support Framework for Airline Flight Cancellations and Delays”, Transportation Science, Vol. 27, pp. 266-280, 1993.
43. Kanafani, A., “Aircraft Technology and Network Structure in Short-Haul Air Transportation”, Transportation Research, Vol. 15A, pp. 305-314, 1981.
44. Kanafani, A., Transportation Demand Analysis, McGraw-Hill, New York, 1983.
45. Kennington, J. L. and Helgason, R. V., Algorithms for Network Programming, John Wiley, New York, 1980.
46. 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.
47. Lee, B. C., Routing Problem With Service Choices, Flight Transportation Laboratory, Report R86-4, Massachusetts Institute of Technology, MA, 1986.
48. Levin, A., Some Fleet Routing and Scheduling Problems for Air Transportation Systems, Flight Transportation Laboratory, Report R68-5, Massachusetts Institute of Technology, MA, 1969.
49. Levin, A., “Scheduling and Fleet Routing Models for Transportation Systems”, Transportation Science, Vol 5, pp. 232-255, 1971.
50. LINGO Optimization Modeling Language, LINDO System Inc., 1994.
51. 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.
52. Powell, W. B., “Analysis of Airline Operating Strategies Under Stochastic Demand”, Transportation Research, Vol 16B, pp. 31-43, 1982.
53. Powell, W. B., “A Review of Sensitivity Results for Linear Networks and a New Aapproximation to Reduce the Effects of Degeneracy”, Transportation Science, Vol 23, pp. 231-243, 1989.
54. Powell, W. B. and Ioannis, A. K., “Shipment Routing Algorithms with Tree Constraints”, Transportation Science, Vol 26, pp. 230-245, 1992.
55. Simpson, R.W., Scheduling and Fleet Routing Models for Airline Systems, Flight Transportation Laboratory, Report R68-3, Massachusetts Institute of Technology, MA, 1969.
56. Simpson, R.W., “A Review of Scheduling and Routing Model for Airline Scheduling,” IX AGIFORS Symposium, Broadway, England, October 1969.
57. Soumis, F., Ferl, J. A. and Rousseau, J. M., “MAPUM: A Model for Assigning Passengers to a Flight Schedule”, Transportation Research, Vol. 15A, pp.155-162, 1981.
58. Subramanian, R., Scheff, R. P., Quillinan, J. D., Wiper, D. S. and Marsten, R. E., “Coldstart: Fleet Assignment at Delta Air Lines”, Interface, Vol. 24, pp.104-120, 1994.
59. Svanberg, K. and Baathe, O., “Computational Experiments with Different Subgradient Techniques”, TRITA-MAT-1985-3, 1985.
60. Swan, W. M., A Systems Analysis of Scheduled Air Transportation Networks, Flight Transportation Laboratory, Report R79-5, Massachusetts Institute of Technology, 1979.
61. Teodorovic, D., “Flight Frequency Determination”, Journal of Transportation Engineering, Vol. 109, pp. 747-757, 1983
62. Teodorovic, D., “Multiattribute Aircraft Choice for Airline Networks”, Journal of Transportation Engineering, Vol. 112, pp. 634-646, 1986.
63. Teodorovic, D., Airline Operations Research, Gordon and Breach Science Publishers, New York, 1988.
64. Teodorovic, D. and Guberinic, S., “Optimal Dispatching Strategy on an Airline Network After a Schedule Perturbation”, European Journal of Operational Research, Vol. 15, No. 2, pp. 178-182, 1984.
65. Teodorovic, D. and Krcmar-Nozic, E., “Multicriteria Model to Determine Flight Frequencies on an Airline Network Under Competitive Conditions”, Transportation Science, Vol. 23, pp. 14-25, 1989.
66. Yan, S., Intermodal Pricing and Operations Using Network Flow Techniques, Ph.D. Dissertation, Department of Civil Engineering, Massachusetts Institute of Technology, 1991.
67. Yan, S., “Approximating Reduced Costs under Degeneracy in a Network Flow Problem with Side Constraints”, Networks, Vol. 27, pp. 267-278, 1996.
68. Yan, S., Bernstein, D. and Sheffi, Y., “Intermodal Pricing Using Network Flow Techniques”, Transportation Research, Vol. 29B, pp. 171-180, 1995.
69. Yan, S. and Yang, D. H., “A Decision Support Framework for Handling Schedule Perturbation”, Transportation Research, Vol. 30B, pp. 405-419, 1996.
70. Yan, S. and Young, H. F., “A Decision Support Framework for Multi-Fleet Routing and Multi-Stop Flight Scheduling”, Transportation Research, Vol. 30A, pp. 379-398, 1996.

指導教授

顏上堯(Shang-Yao Yan)

審核日期

2000-7-10

推文