生命探測器於都市震災搜救之最佳路徑規劃

本研究針對生命探測器於都市震災搜救之路徑問題發展求解演算法，並且採用雲端運算架構中軟體即服務(Software as a Service, SaaS)之概念，在Google App Engine (GAE)平台上開發與部署生命探測器搜救路徑規劃之雲端服務。考量生命探測器具有一有效偵測半徑，在此半徑範圍內的倒塌建築物皆可被完全偵測，生命探測器搜救路徑問題之求解目標為在最短時間內偵測完所有給定之災區點。此問題可以定義為足夠接近鄉村郵差問題，為NP-Hard，所以本研究發展以區域搜尋為基礎之三種巨集啟發式演算法：模擬退火法、禁忌演算法、迭代貪婪法，利用Java電腦程式語言實現，並在數個實際的都市街道路網中測試演算法效能，結果發現禁忌演算法的求解效能最佳。最後，將所發展的演算法部署到GAE平台，建立生命探測器搜救路徑規劃雲端服務，使得第一線消防隊員可透過無線網路使用此服務，以充份發揮在雲端平台上強大儲存、運算與地圖顯示功能。

關鍵字

生命探測器；路徑規劃；災害搜救；雲端運算； Google App Engine

並列摘要

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.

並列關鍵字

Life detectors ； Path planning ； Disaster search and rescue ； Cloud Computing ； Google App Engine

參考文獻

[4] 古澤民，穩健節點p中心模式於緊急救災物資配送中心區位選擇之應用，碩士論文，臺北科技大學工業工程與管理研究所，台北，2011。

[5] 吳泰熙，以禁忌搜尋法則求解推銷員旅行問題，大葉學報，第六卷，第一期，1997，第87-99頁。

[6] FEMA(Federal Emergency Management Agency), http://www.fema.gov/about/femaorg.shtm, 2003.

[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.

國際替代計量

生命探測器於都市震災搜救之最佳路徑規劃

全文下載

主題瀏覽