臺灣博碩士論文加值系統

飛航網路的規劃直接關係到航空公司運行的成本及服務的水準，為航空業的重要議題。軸輻式路網(hub-and-spoke network)的應用，除簡化路網複雜度外，並可讓路網內的轉運站具有集中旅客或貨物的功能，形成規模經濟的效益，進而減低單位運輸成本。因此近年來成為各家航空公司規劃路網的主流。由於軸輻式路網的設計為一混合整數規劃問題(mixed integer program)，應用於求解實際飛航路網時，問題規模通常都相當龐大，造成求解上的困難。傳統求解軸輻式路網的方法，最常使用到的有：窮舉法、分枝界限法(branch and bound)…等，在小型問題上，求解時間尚能維持在合理範圍內。然而，當問題規模龐大時，則不易迅速有效的求解。本研究跳脫傳統解法的思考方式，利用基因演算法(genetic algorithm)，針對軸輻式網路規劃問題，發展一有效的求解步驟。以兩岸航空客運實際資料為例，對真實的大型路網進行測試，並將求解的品質及效率，與GAMS最佳化軟體所得的結果，做一比較分析。最後利用所發展的基因演算法，對模式進行敏感度分析及不同的情境測試。

Hub-and-Spoke network systems are widely studied in the research of location problems. Such problem involves locating the hubs and determining the network structure. The problem is usually formulated as a large mixed integer program. It is difficult to obtain the optimal solution within reasonable time due to inherent complexity. Therefore, it requires an efficient solution algorithm to solve the real-world problem. This research applied Genetic Algorithm to solve the hub-and-spoke network problem. The real data for the air passengers between Taiwan and Mainland China was used to test the performance of the proposed algorithm. The result was also compared with that obtained from the solver supported by GAMS commercial software. Preliminary result shows that Genetic Algorithm is efficient and effective for solving the hub-and-spoke problem.

摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
第一章　緒論 1
1.1研究背景與動機 1
1.2研究目的與範圍 2
1.3研究方法 2
第二章　文獻回顧 4
2.1軸輻式路網研究議題 4
2.1.1軸輻式路網介紹 4
2.1.2軸輻式路網文獻分類與回顧 5
2.2啟發式演算法研究課題 8
2.2.1啟發式解法之應用 8
2.2.2基因演算法之應用 9
2.3基因演算法 13
2.3.1基因演算法的步驟 14
2.4小結 18
第三章　求解軸輻式網路模式之研究方法 19
3.1問題描述與模式假設 19
3.2軸輻式航空網路基本模式定義 21
3.3軸輻式航空網路完整模式定義 22
3.4基因演算法導入航空路網之方法 25
3.4.1基本模式應用基因演算法求解步驟 25
3.4.2完整模式應用基因演算法求解步驟 29
3.5問題規模 32
3.6小結 33
第四章　實例測試 34
4.1輸入資料 35
4.1.1推估台灣與大陸通航機場間的旅客量 36
4.1.1.1大陸與台灣通航機場之選取 36
4.1.1.2推估從台灣到大陸的旅客量 37
4.1.1.3推估從大陸到台灣的旅客量 38
4.1.1.4推估大陸機場間旅客量 39
4.1.2轉運站設置成本之估算 39
4.1.3總成本之估算 40
4.2模式情境測試 40
4.2.1情境測試之項目介紹 40
4.2.2運算情境之參數設定 43
4.3基本模式之實例分析 44
4.3.1對稱型路網之測試結果 44
4.3.2不對稱型路網之測試結果 48
4.3.3兩型態路網之綜合比較分析 50
4.4完整模式之實例分析 51
4.4.1策略一：轉運站考慮進、入境與轉運方式之測試結果 51
4.4.1.1對稱型路網之測試結果 51
4.4.1.2不對稱型路網之測試結果 58
4.4.1.3兩型態路網之綜合比較分析 60
4.4.2策略二：轉運站只考慮轉口方式之測試結果 61
4.4.2.1對稱型路網之測試結果 61
4.4.2.2不對稱型路網之測試結果 63
4.4.2.3兩型態路網之綜合比較分析 64
4.5完整模式之香港機場現況分析 65
4.5.1香港機場旅客需求測試 65
4.5.2透過香港機場轉運旅客需求測試 67
4.6敏感度分析 69
4.6.1轉運站變動最大容量限制 70
4.6.2轉運站變動設置成本 72
4.6.3轉運站變動折扣係數 值 73
4.6.4基因演算法之完整模式給定與隨機產生轉運站數目 74
4.6.5基因演算法之變動參數值趨勢 75
第五章　結論與建議 78
5.1結論 78
5.1.1基本模式結論 78
5.1.2完整模式 79
5.2建議 81
參考文獻 83
附錄 88
附錄一：機場順序符號對照表 88
附錄二：基本模式對稱型路網輸出結果（求解一次） 89
附錄三：基本模式不對稱型路網輸出結果（求解一次） 97
附錄四：完整模式策略一對稱型路網輸出結果（求解一次） 105
附錄五：完整模式策略一不對稱型路網輸出結果（求解一次） 109
附錄六：完整模式策略二對稱型路網輸出結果（求解一次） 111
附錄七：完整模式策略二不對稱型路網輸出結果（求解一次） 112
附錄八：加入香港機場旅客需求測試（求解一次） 113
附錄九：台灣與大陸旅客需透過香港機場轉運測試（求解一次） 114
附錄十：最佳化軟體(GAMS)求解基本模式最佳解之誤差比 115
附錄十一：最佳化軟體(GAMS)求解完整模式最佳解之誤差比 117
附錄十二：基本模式對稱型路網求解品質輸出結果(求解十次) 118
附錄十三：完整模式對稱型路網求解品質輸出結果(求解十次) 122

1. 中國民用航空總局規劃發展財務司，民國九十四年，從統計看民航2005，北京中國民航出版社。
2. 中國民用航空總局規劃發展財務司，民國九十三年，從統計看民航2004，北京中國民航出版社。
3. 中國民用航空總局規劃發展財務司，民國九十二年，從統計看民航2003，北京中國民航出版社。
4. 中國民用航空總局規劃發展財務司，民國九十一年，從統計看民航2002，北京中國民航出版社。
5. 中國民用航空總局規劃發展財務司，民國九十○年，從統計看民航2001，北京中國民航出版社。
6. 中國民用航空總局規劃發展財務司，民國八十九年，從統計看民航2000，北京中國民航出版社。
7. 中國民用航空總局規劃發展財務司，民國八十八年，從統計看民航1999，北京中國民航出版社。
8. 中國國家旅遊局，民國九十四年，中國旅遊年鑑2005，中國旅遊出版社。
9. 中共中央政府，民國八十九年，展望十五，http://big51.china.com.cn/ch-15/plan2.htm。
10. 中華航空股份有限公司編印，民國九十三年，華航2004財務年報，中華航空股份有限公司出版，http://www.china-airlines.com/ch/about/94ap.pdf。
11. 行政院大陸委員會，民國九十五年，兩岸經濟統計月報，第156期，行政院大陸委員會出版，http://www.mac.gov.tw/big5/statistic/em/156/19.pdf。
12. 朱冠文、張玉君、劉昭榮、陳文富、許美惠、石仲豪、陳世泉、劉亦群、曾琬芸、葉南廷，民國八十七年，赴港澳地區國際空運旅客特性調查與分析，交通部運輸研究所及鼎漢國際工程顧問公司。
13. 林正章、陳英傑，民國88年，兩岸航空貨運直航航線規劃之研究，中華民國第四屆運輸網路研討會，第1-11頁。
14. 許巧鶯、蕭國洲，民國87年，廠商以航空貨運中心為轉運站之研究，運輸計劃季刊，第27卷，第二期，第213-244頁。
15. 許巧鶯、王志青，民國86年，軸輻航空貨運網路之直接與轉運路線選擇，運輸計劃季刊，第26卷，第一期，第95-118頁。
16. 張國振，民國93年，城際客運營運路線之規劃與設計-遺傳演算法之應用，國立暨南國際大學土木工程研究所碩士論文。
17. 曾國雄、王日昌、黃明居，民國85年，以基因演算法與樣板路徑求解旅行推銷員問題，運輸計畫季刊，第25卷，第3期，第493-516頁。
18. 黃玉真，民國93年，探討多期配送系統設計問題之研究-以預算與服務水準條件限制之角度，高雄第一科技大學運輸與倉儲營運研究所碩士論文。
19. 楊大輝、蕭凱陽、李綺容，民國93年，考量直航轉運並行之軸輻式航空網路模型，運輸計畫季刊，第33卷，第4期，第603-624頁。
20. 歐陽餘慶、林國顯、朱冠文、呂蕙美、張玉君、鄭樂堯、林弘基、洪清貴、畢金菱、吳雅惠、吳心琪、江芷瑛，民國八十九年，兩岸航空客運市場之研究，交通部運輸研究所及亞聯工程顧問有限公司。
21. 陳建國，民國93年，利用基因演算法於KNN近似查詢之種類型資料對映演算法，國立嘉義大學運輸與工程研究所碩士論文。
22. 謝國倫，民國89年，基因演算法應用於捷運轉乘公車區位路徑問題之研究，淡江大學運輸管理學研究所碩士論文。
23. 盧建宏，民國93年，應用基因演算法求解二階層設施區位選擇問題，嘉義大學運輸與物流工程研究所碩士論文。
24. 盧華安、陳羿中，民國94年，建構我國國際航空貨運網路之研究-以單一全貨機機種為例，民航季刊，第7卷，第二期，第89-120頁。
25. 藍武王、邱裕鈞，民國89年，線性軸輻路網接駁/轉運區位、路線與排班之規劃-遺傳演算法之應用，運輸計畫季刊，第29卷，第三期，第465-498頁。
26. 劉曉君，民國90年，轉接點位址問題之啟發解法，大葉大學工業工程學系碩士班論文。
27. 蕭凱陽，民國92年，航空轉運站之選擇與營運網路規劃-以兩岸航空貨物為例，國立嘉義大學運輸與工程研究所碩士論文。
28. 顏上堯、黃武強，民國85年，配合轉運中心之飛航定線與航次頻率規劃，運輸計劃季刊，第25卷，第四期，第681-708頁。
29. 鐘元享、陳正芳，民國93年，多重分派p-轉接點中位問題的啟發式解法，第一屆台灣作業研究學會學術研討會暨2004年科技與管理學術研討會。
30. Aykin, T., 1995b.The Hub Location and Routing Problem, European Journal of Operations Research,83：200-219.
31. Abdinnour-Helm, S., 1998.A Hybrid Heuristic for The Uncapacitated Hub Location Problem, European Journal of Operational Research,106：489-499.
32. Alp, O., Erkut, E., and Drezner, Z., 2003. An Efficient Genetic Algorithm for The P-Median problem, Annuals of Operations Research,122：21-42.
33. Beasley, J.E., and Chu, P.C., 1996.A Genetic Algorithm for The Set Covering Problem, European Journal of Operational Research,94：392-404.
34. Bryan, D. E., and O’Kelly, M. E., 1999.Hub-and-Spoke Network in Air Transportation: An Analytical Review, Journal of Regional Science,39(2)：275-29.
35. Campbell, J.f., 1994b.Integer Programming Formulations of Discrete Hub Location Problems, European Journal of Operational Researc,72：387-405.
36. Campbell, J. F., 1996.Hub Location and The P-Hub Median Problem, Operations Research,44：923-935.
37. Correa, E.S., Steiner, M. T. A., Freitas, A. A. and Carnieri, C., 2001,A Genetic Algorithm for The P-median Problem, 2001 Genetic and Evolutionary Computation Conference (GECCO-2001)：1268-1275.
38. Cheung, B. K. –S., Langevin, A., and Villeneuve, B., 2001.High Performing Evolutionary Techniquew for Solving Complex Location Problems in Industrial System Design, Journal of Intelligent Manufacturing,18(4)：455-466.
39. Dvorett, J., 1999.Compatibility-Based Genetic Algorithm: A New Approach to The P-Median Problem, Department of Industrial Engineering and Management Sciences Northwestern University, Evanston, IL60208：1-17.
40. Ernst, A. T., and Krishnamoorthy, M., 1998.Exact and Heuristic Algorithms for The Uncapacitated Multiple allocation P-Hub Median Problem, European Journal of Operational Research,104：100-112.
41. Goldberg, D. E, 1989.Genetic Algorithms in Search, Optimization, and Machine Learning? Addison-Wesley.
42. Gen, M., Cheng, R., and Oren, S. S., 2001.Network Design Techniques Using Adapted Genetic Algorithms. Advances in Engineering Software,32：731-744.
43. GEATbx: Genetic and Evolutionary Algorithm Toolbox for Use with Matlab. http://www.geatbx.com/。
44. Holland, J. H., 1975.Adaptation in Nature and Artificial Systems, University of Michigan press, Ann Arbor.
45. Houck, C.R., Joines, J.A., and Kay ,M.G., 1996.Comparison of Genetic Algorithms, Random Restart and Two-Opt Switching for Solving Large Location-Allocation Problems, Computers and Operations Research,23(6)：587-596.
46. Jaillet, P., Song, G., and Yu, G., 1996.Airline Network Design and Hub Location Problems, Location Science,4(3)：195-212.
47. Jaramillo, J.H., Bhadury, J., and Batta, R., 2002.On The Use of Genetic Algorithms to Solve Location Problem, Computers and Operations Research,29：761-779.
48. Koumousis, V. K., and Georgiou, P. G, 1994.Genetic Algorithms in Discrete Optimization of Steel Truss Roofs, Journal Computing in Civil Engineering, ASCE,8(3)：309-325.
49. Klincewicz, J. G., 1996.A Dual Algorithm for The Uncapacitated Hub Location Problem, Location Science,4(3)：173-184.
50. Leclerc, F., and Potvin J. Y., 1997.Genetic Algorithms for Vehicle Dispatching, International Transportation Operational Research,4(5/6)：391-400.
51. Min, H., Ko H. J., and Ko. C. S., 2006.A Genetic Algorithm Approach to Developing The Multi-Echelon Reverse Logistics Network for Product Returns, The International Journal of Management Science Omega,34：56-69.
52. O’Kelly, M. E., 1986.The Location of Interacting Hub Facilities, Transportation Science,20(2)：92-106.
53. O’Kelly, M. E., 1987.A Quadratic Integer Program for The Location of Interacting Hub Facilities, European Journal of Operational Research,32：393-404.
54. O’Kelly, M. E., 1992.Hub Facility Location with Fixed Costs, Regional Science :The Journal of the RSAI,71(3)：293-306.
55. O’Kelly, M. E., Bryan, D., Skorin-Kapov, D., and Skorin-Kapov, J., 1996.Hub Network Design with Single and Multiple Allocation: A Computional Study, Location Science,4(3)：125-138.
56. O’Kelly, M. E., and Bryan, D. L., 1998.Hub Location with Flow Economies of Scale, Transportation Research B,32(8)：605-616.
57. O’Kelly, M. E., 1998.A geographer’s analysis of hub-and-spoke networks, Journal of Transportation Geography,6(3)：171-186.
58. Pattnaik, S. B., Mohan, S., and Tom, V. M., 1998.Urban Bus Transit Route Network Design Using Genetic Algorithm, Journal of Transportation Engineering,124(4)：368-375.
59. Rolland, E., Schiliing, D. A., Current, J. R., 1996.An Efficient Tabu Search Procedure for The P-Median Problem, European Journal of Operational Research,96：329-342.
60. Song, G., 1995.Integeer Linear Programming Models for Airline Network Design Problem. PHD dissertation, MSIS Department, The University of Texas at Austin.
61. Skorin-Kapov, D., Skorin-Kapov, J., and O’Kelly, M. E., 1996.Tight Linear Programming Relaxation of Uncapacitated P-Hub Median Problems, European Journal of Operational Research,94：582-593.
62. Skorin-Kapov, D., and Skorin-Kapov, J., 1994.On Tabu Search for The Location of Interacting Hub Facilities, European Journal of Operational Research,73：502-509.
63. Sohn, J., and Park, Sungsoo., 1998.Efficient Solution Procedure and Reduced Size Formulations for P-Hub Location Problems, European Journal of Operational Research,108：118-126.
64. Sasaki, M., Suzuki, A. and Drezner, Z., 1999.On the Selection of Hub Airports for an Airline Hub-and-Spoke System, Computers & Operations Research,26：1411-1422.
65. Tom, V. M., and Mohan, S., 2003.Transit Route Network Design Using Frequency Coded Genetic Algorithm, Journal of Transportation Engineering,129(2)：186-195.
66. Topcuoglu, H., Corut, F., Ermis, M., and Yilmaz, G., 2005.Solving the Uncapacitated Hub Location Problem Using Genetic Algorithms, Computers & Operations Research,32：967-984.
67. Wang, Q. J., 1997.Using Genetic Algorithm to Optimise Model Parameters, Environmental Modeling & Software,12(1)：27-34.