摘 要

近年來國內陸續發生一些重大災難，例如921大地震、八掌溪事件及台中金沙百貨大樓大火等，而這些災害的發生，其共同所面臨問題均是地面交通工具無法直接抵達災難現場，致使搶救不易。而直昇機因具有能突破地形地物障礙、直驅事故現場且快速搜救的優勢，空中直昇機救援則成為其搶救之重要載具。然而往昔直昇機救援之路線規劃大多使用經驗法則，或是依空中救援指揮系統之指揮，因此救援路線規劃多僅是單一路線上之救援行為，另受限於國內救援直昇機數量不足及救援任務之多樣性，致使在大量救援任務於同一時間發生時，無法在搶救過程中發揮最大效益。為求得快速及有效率之路線規劃系統，本文擬利用蟻群演算法具有可搜尋最佳路徑的效果，以建構一空中直昇機之救援路徑規劃模式，文中並以台灣北、中、南及東部等四個地區的直昇機起降點做為路徑選擇之節點，以進行路線模式之實例驗證。由分析結果顯示，本文ACS之模式可依任務需求規畫救援路徑，且使用介面上非常簡便及快速。

ABSTRACT

In recent year, there are many measurable disasters happened consequently, for instance, 921 earthquake, Ba-zhang river accident and the fire accident of Ginza department store in Taichung. The common problem which causes a difficult rescue for these accident is the land traffic equipment. As helicopter owns a character to break through geographical barriers and head to accident scene quickly and directly, it becomes an important equipment for air-to-land rescue. However, there are shortages exist among the helicopter rescue-rules of thumb or single route, Therefore, this article will apply Ant Colony System which able to search the optimize route and construct a plan model for helicopter rescue from the air. In this article, the helicopter terminal from north, middle, south and east area of Taiwan will be chosen as the node for route selection and conducting the route model experiment. The result shows the ACS in this article can be adjusted by different mission request and is easy and convenient to operate.

總 目 錄

摘 要 -------------I
ABSTRACT ----------II
誌 謝 -----------III
目 錄 ------------IV
表 目 錄 --------VI
圖 目 錄 -------VII

第一章 緒論 ------------------------------------1
1-1 研究動機 -----------------------------------1
1-2 研究方法與流程 -----------------------------1
1-3 論文內容 -----------------------------------2
第二章 文獻回顧 --------------------------------4
2-1 空中救護之探討 -----------------------------4
2-1-1 緊急空中救護基本介紹 ---------------------4
2-1-2 空中救護案例回顧 -------------------------5
2-2 旅行推銷員問題(Traveling Salesman Problem, TSP) -----7
2-2-1 TSP定義 ----------------------------------8
2-2-2 TSP解法簡述 ------------------------------8
2-3 巨集啟發式解法(Meta-Heuristic) -------------9
2-3-1 模擬退火法(Simulation Annealing, AS) -----9
2-3-2 禁忌搜尋法(Tabu Search, TS) --------------9
2-3-3 基因演算法(Genetic Algorithm, GA) -------10
2-3-4 蟻群演算法(Ant Colony System, ACS) ------11
第三章 蟻群演算法之應用 -----------------------18
3-1 旅行推銷員問題 ----------------------------18
3-2 蟻群演算法 --------------------------------19
3-2-1 蟻群行為 --------------------------------19
3-2-2 蟻群最佳化演算法之起源 ------------------20
3-2-3 蟻群演算法(ACS) -------------------------20
3-3 ACS系統建構 -------------------------------22
3-3-1 ACS運算流程與架構 -----------------------22
3-3-2 系統建置與程式執行步驟 ------------------23
第四章 案例討論 -------------------------------35
4-1 案例背景說明 ------------------------------35
4-2 ACS系統測試 -------------------------------36
4-3 實例操作分析 ------------------------------37
第五章 結論與建議 -----------------------------58
5-1 結論 --------------------------------------58
5-2 建議 --------------------------------------58
參考文獻 --------------------------------------60
簡 歷 --------------------------------------63

表 目 錄
表2-1 近年災害統計表 --------------------------13
表2-2 國軍支援「嘉義小火車翻覆事件」相對時間表-14
表2-3 金沙百貨大樓空中救援相對時間表 ----------15
表4-1 中部地區直昇機各降落點編號及座標 --------40
表4-2 不同疊代數之搜尋結果 --------------------41
表4-3 北部地區直昇機各降落點編號及座標 --------42
表4-4 南部地區直昇機各降落點編號及座標 --------43
表4-5 東部地區直昇機各降落點編號及座標 --------44
表4-6 各區路線規劃結果 ------------------------45

圖 目 錄
圖1-1 研究流程圖 -------------------------------3
圖2-1 空中勤務總隊機隊分佈圖 ------------------16
圖2-2 常見TSP解法圖 ---------------------------17
圖3-1 螞蟻外出覓食之示意圖 --------------------26
圖3-2 蟻群演算法流程 --------------------------27
圖3-3 進入ACS Project時之畫面 -----------------28
圖3-4 ACS Project執行程式之畫面 ---------------28
圖3-5 匯入地圖之畫面 --------------------------29
圖3-6 輸入景點座標之畫面 ----------------------30
圖3-7 基本參數設定之畫面 ----------------------31
圖3-8 圖表座標設定之畫面 ----------------------31
圖3-9 路徑規劃開始運算弁鉞e面 -----------------31
圖3-10 各疊代中路徑規劃顯示之畫面 -------------32
圖3-11 最佳路徑演變曲線圖 ---------------------32
圖3-12 平均路徑演變曲線圖 ---------------------33
圖3-13 最佳路徑規劃顯示圖 ---------------------33
圖3-14 運算耗時計算之畫面 ---------------------34
圖4-1 中部地區直昇機起降點位置分佈圖 ----------46
圖4-2 最佳路徑規劃演算過程曲線圖 --------------47
圖4-3 平均路徑規劃演算過程曲線圖 --------------48
圖4-4 中部1000次疊代最佳路徑規劃圖 ------------49
圖4-5 中部3000次疊代最佳路徑規劃圖 ------------50
圖4-6 中部5000、10000次疊代最佳路徑規劃圖 -----51
圖4-7 北部地區直昇機起降點位置分佈圖 ----------52
圖4-8 南部地區直昇機起降點位置分佈圖 ----------53
圖4-9 東部地區直昇機起降點位置分佈圖 ----------54
圖4-10 北部最佳路徑規劃圖 ---------------------55
圖4-11 南部最佳路徑規劃圖 ---------------------56
圖4-12 東部最佳路徑規劃圖 ---------------------57

參考文獻

中文部份
1.吳泰熙、張欽智，（1997），以禁忌搜尋法則求解推銷員旅行問題，大業學報，第六卷第一期，頁87-99。

2.陳燁，（2001），帶染交算子的蟻群算法，計算機工程第27卷，第12期，頁74-76。

3.羅中育，（2001），田口品質工程應用於模擬退火法參數組合-以旅行推銷員問題（TSP）為例，國立雲林科技大學工業工程與管理研究所碩士論文。

4.吳怡昌、王文周，（2003），空中搜救與緊急醫療後送作業之生理醫學觀。

5.蘇耿志，（2003），澎湖縣救護直昇機醫療後送之案例分析與離島後送醫療制度之探討，台北醫學大學公共衛生學院傷害防治研究所碩士論文。

6.蔡正發、李文專、杜詩怡、洪振瑋、劉佳宗，（2004），規劃系統設計與實作－以電子商務物流運輸為例，2004全國電信研討會。

7.段海濱，（2005），蟻群演算法原理及其應用，初版，北京，科學出版社，頁39。

8.陳東瑤、王相華、周大慶，（2005），社頂生態旅遊路線整體規劃研究，內政部營建署墾丁國家公園管理處，頁71-74。

9.陳冠樺，（2005），螞蟻記憶系統應用於旅行推銷員問題，逢甲大學交通工程與管理學系碩士論文。

10.馬漢平，（2006），使用直昇機緊急救護高樓火災災民逃生之成效研究，台北醫學大學傷害防治研究所碩士論文。

英文部分
11.Colorni, A and Dorigo, M. and Maniezzo, V. (1991). Distributed optimization by ant colonies , Proceedings of ECAL91-European Conference on Artificial Life. Paris, France: Elsevier Publishing, pp. 134-142.

12.Dantzig, G.. and Fulkerson, R. and Johnson, S. (1954) . Solution of a large-scale traveling saleman problem. Operations Research , Vol. 2, No. 4, pp. 393-410.

13.Dorigo, M and Colorni, A. (1996) .The ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics Part B, Vol. 26, No. 1, pp. 29-41.

14.Dorigo, M. and Gambardella, L. M. (1997). Ant colony system: A Cooperative Learning Approach to the Traveling Salesman Problem IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 29-66.

15.Dorigo, M., Caro G. D. and Gambardella, L. M. (1999). Ant System for Discrete Optimization, Artificial Live, Vol. 15, No. 3, pp. 137-172.

16.Flood, M. M. (1956), The traveling salesman problem. Operations Research , Vol. 4, pp.61-75, 1956.

17.Glover, F. (1977). Heuristic for Integer Programming Using Surrogate Constraints, Decision Science, Vol. 8, pp. 156-166.

18.Garey, M.D. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco.

19.Glover, F.(1986). Tabu Search-Part E, ORSA Journal on Computing, Vol. 1, No. 3, pp. 190-206.

20.Holland, J. (1975). Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, Michigan.

21.Metropolis , N., Rosenbluth, A. Rosenbluth, M., Teller A. and Teller, E.(1953). Equation of State Calculations by Fast Computing Machines, Journal of Chen. Physics, Vol. 21, pp. 1087-1092.

22.Maniezzo, V. and Colorni, A. (1999). The Ant System Applied to the Quadratic Assignment Problem, IEEE Transactions on Knowledge and Data Engineering.

23.Stutzle, T. and HOOS, H. H. (2000). MAX-MIN ant system, Journal of Future Generation Computer Systems, Vol. 10, No. 2, pp. 889-914.

網路部份
24.國防部 http://www.mnd.gov.tw/
25.內政部 http://www.moi.gov.tw/home/home.asp
26.主計處 http://www.dgbas.gov.tw/lp.asp?CtNode=3120&CtUnit=1049&BaseDSD=34
27.The history of the air ambulance http://www.bellhelicopter.textron.com/