跳到主要內容

臺灣博碩士論文加值系統

(3.235.60.144) 您好!臺灣時間:2021/07/27 01:51
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:胡書豪
研究生(外文):Shu-Hao Hu
論文名稱:生命探測器於都市震災搜救之最佳路徑規劃
論文名稱(外文):Optimal Life Detector Rescue Routing for Urban Earthquake Disasters
指導教授:盧宗成盧宗成引用關係
口試委員:蘇昭銘吳建文王晉元
口試日期:2012-06-28
學位類別:碩士
校院名稱:國立臺北科技大學
系所名稱:資訊與運籌管理研究所
學門:商業及管理學門
學類:財務金融學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:51
中文關鍵詞:生命探測器路徑規劃災害搜救雲端運算Google App Engine
外文關鍵詞:Life detectorsPath planningDisaster search and rescueCloud ComputingGoogle App Engine
相關次數:
  • 被引用被引用:0
  • 點閱點閱:227
  • 評分評分:
  • 下載下載:2
  • 收藏至我的研究室書目清單書目收藏:0
本研究針對生命探測器於都市震災搜救之路徑問題發展求解演算法,並且採用雲端運算架構中軟體即服務(Software as a Service, SaaS)之概念,在Google App Engine (GAE)平台上開發與部署生命探測器搜救路徑規劃之雲端服務。考量生命探測器具有一有效偵測半徑,在此半徑範圍內的倒塌建築物皆可被完全偵測,生命探測器搜救路徑問題之求解目標為在最短時間內偵測完所有給定之災區點。此問題可以定義為足夠接近鄉村郵差問題,為NP-Hard,所以本研究發展以區域搜尋為基礎之三種巨集啟發式演算法:模擬退火法、禁忌演算法、迭代貪婪法,利用Java電腦程式語言實現,並在數個實際的都市街道路網中測試演算法效能,結果發現禁忌演算法的求解效能最佳。最後,將所發展的演算法部署到GAE平台,建立生命探測器搜救路徑規劃雲端服務,使得第一線消防隊員可透過無線網路使用此服務,以充份發揮在雲端平台上強大儲存、運算與地圖顯示功能。

This study proposes solution algorithms for the life detector search and rescue routing (LDSRR) problem in urban earthquake rescue, and develops and deploys a cloud service of life detector search and rescue routing on the Google App Engine (GAE) platform, according to the software as a service (SaaS) concept of Cloud Computing. Considering that life detectors having an effective detection radius, all collapsed buildings within this radius can be completely detected. The objective of solving LDSRR problem is to find a shortest rescue path that detects all (given) collapsed building in an urban street network. This problem can be considered as the close enough rural postman problem (CERPP), which is NP-Hard, so this study develops three local search-based meta-heuristics: Simulated Annealing, Tabu Search, Iterated Greedy. The three algorithms were implemented using Java computer language and tested on several real street networks. Computational results showed that Tabu Search outperforms the other two methods on all the test networks. Finally, the developed algorithms were deployed on the GAE platform, establishing the life detector search and rescue routing service. First-line fire fighters can use this service via wireless communication, fully utilizing the powerful storage, computing and map-displaying capabilities of the cloud platform.

摘 要 II
目錄 V
表目錄 VII
圖目錄 VIII
第一章 序論 1
1.1 研究動機與目的 1
1.2 問題描述 3
1.3 研究方法與流程 3
第二章 文獻探討 6
2.1 災害搜救裝備介紹 6
2.1.1 生命偵測儀 6
2.1.2 心跳生命探測器 8
2.2 緊急救災相關文獻 10
2.3 鄉村郵差問題文獻 11
2.4 足夠接近路徑問題文獻 12
2.5 雲端運算 13
2.5.1 雲端運算概念 13
2.5.2 雲端運算服務介紹 14
2.5.3 Google App Engine介紹 15
2.5.4 雲端運算應用於供應鏈與物流管理 17
第三章 研究方法 18
3.1 問題描述 18
3.2 啟發式演算法基本架構 19
3.3 選擇必走街道集合之策略 19
3.4 初始解產生方法 22
3.5 產生鄰近解之方法 23
3.6 巨集啟發式演算法 26
3.6.1 模擬退火法介紹 26
3.6.2 禁忌搜尋法介紹 29
3.6.3 迭代貪婪法介紹 32
3.7 生命探測器搜救路徑規劃之雲端服務 32
3.7.1 服務需求 32
3.7.2 系統架構 33
第四章 實驗結果與分析 35
4.1 實驗設計 35
4.2 鄰近解產生策略測試結果 36
4.3 演算法於不同路網求解結果 39
4.4 生命探測器偵測半徑對求解績效之敏感度分析 41
4.5 雲端服務的操作流程展示 42
第五章 結論與建議 47
5.1 結論 47
5.2 未來研究方向與建議 48
參考文獻 49



[1]防災國家型科技計畫(NAPHM),防災國家型科技計畫規劃報告,第一期,1997,第5頁。
[2]內政部消防署,裝備櫥窗-生命偵測儀介紹,http://enews.nfa.gov.tw/issue/980917/images/tool.htm, 2009。
[3]內政部消防署,裝備櫥窗-心跳生命探測器介紹,http://enews.nfa.gov.tw/issue/980205/images/tool.htm, 2009。
[4]古澤民,穩健節點p中心模式於緊急救災物資配送中心區位選擇之應用,碩士論文,臺北科技大學工業工程與管理研究所,台北,2011。
[5]吳泰熙,以禁忌搜尋法則求解推銷員旅行問題,大葉學報,第六卷,第一期,1997,第87-99頁。
[6]FEMA(Federal Emergency Management Agency), http://www.fema.gov/about/femaorg.shtm, 2003.
[7]Google App Engine Developer''s Guide https://developers.google.com/appengine/docs/, 2012
[8]J. Dong, N. Yang and M. Chen (2007), "Heuristic approaches for a TSP variant: the automatic meter reading shortest tour problem," Operations Research/Computer Science Interfaces Series, vol. 37, pp.145-163
[9]G. Barbarosoglu, L. Ozdamar and A. Cevik, "An interactive approach for hierarchical analysis of helicopter logistics in disaster relief operations," European Journal of Operational Research, vol.140, 2002, pp. 118–133.
[10]G. Barbarosoglu and Y. Arda," A two-stage stochastic programming framework for transportation planning in disaster response," Journal of the Operational Research Society, vol. 55, 2004, pp. 43–53.
[11]G. Groves and J. V. Vuuren, "Efficient heuristics for the Rural Postman Problem," Operations Research Society of SA, vol.21, no.1, 2005, pp. 33–51.
[12]I. D. Bodin and S. J. Kursh, "A Detailed Description of a Computer System for the Routing and Scheduling of Street Sweeper," Compus. & Opns. Res. vol.6, 1979, pp.181-198.
[13]I. Sungur, F. Ordonez and M. Dessouky, "A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty," IIE Transactions, vol.40, 2008, pp. 509–523.
[14]J. B. Sheu, "An emergency logistics distribution approach for quick response to urgent relief demand in disasters", Transportation Research Part E, vol. 43, 2007, pp. 687-709.
[15]J. Dong, N. Yang and M. Chen, "Heuristic Approaches for a TSP Variant:the Automatic Meter Reading Shortest Tour Problem," 2007.
[16]J. Majumdar and A.K. Bhunia, "Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times, "Journal of Computational and Applied Mathematics, vol. 235, 2011, pp. 3063–3078.
[17]J. K. Lenstra and K. Rinnooy, "On General Routing Problem," Networks, Vol.6, 1976, pp. 273-280.
[18]J. Leukel, S. Kirn, and T. Schlegel, "Supply Chain as a Service: A Cloud Perspective on Supply Chain Systems," European Journal of Operational Research, vol. 179, 2007, pp. 1177–1193
[19]J. K. Lenstra, and A. H. G. Rinnooy Kan. G, On General Routing Problems. Networks 6, 2007, pp. 273-280.
[20]K. C. Ying, Z. J. Lee, C. C. Lu, and S. W. Lin, "Metaheuristics for scheduling a no-wait flowshop manufacturing cell with sequence dependent family setups" vol. 58, 2012, pp. 671-682.
[21]L. W. Jacobs, M. J. Brusco, "A local-search heuristic for large set-covering problems., " Nav Res Log vol. 42 1995, pp.1129–1140
[22]M. J. Kang and C. G. Han, "Solving the rural postman problem using a Genetic algorithm with graph transformation," SAC ''98 Proceedings of the 1998 ACM symposium on Applied Computing, 1998, pp. 356-360
[23]R. Shuttleworth, B. L. Golden, S. Smith, and E. Wasil, "Advances in Meter Reading:Heuristic Solution of the Close Enough Traveling Salesman Problem over a Street Network," Operations Research / Computer Science Interfaces Series, vol.43, 2008, pp.487-501.
[24]W. Yi and L. Ozdamar, "A dynamic logistics coordination model for evacuation and support in disaster response activities," European Journal of Operational Research, vol.179, 2007, pp. 1177-1193.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top