透過您的圖書館登入
IP:52.23.231.207
  • 學位論文

考量建築資訊模型與多路徑旅行銷售員問題之建築物室內搜救路線找尋

The Interior Patrol Routing Problem Considering Building Information Models and the Multiple Traveling Salesman Problem

指導教授 : 陳柏華

摘要


建築物緊急災難處理中,若有良好的室內搜尋動作,救難效率可得到提升。而搜救過程中若可即時回報,亦可讓指揮者作出更有效之進階救災部署與決策。「第一次搜尋(Primary Search)」為在救災中,人員進入災區後快速地進行各空間的巡邏查看、緊急搶救與回報。儘管其重要性在許多國內外消防專家訪問以及救災指導手冊中提及,卻因規範模糊及現場缺乏詳盡的執行準則而未被落實。本研究以取得之建築物資訊模型(Building Information Models)進行複雜或大型建物室內路網之自動生成,並導入多路徑「旅行者銷售員問題(Traveling Salesman Problem)」進行巡邏路徑的最佳搜尋。由於模型計算複雜及為求方法能於緊急情境下使用,本研究結合欄位生成(Column Generation)與分支定界(Branch and Bound)演算法提升求解效率。而本研究最後提供之分群分類啟發式演算法,可達成研究最終目標「大尺度下快速求解」,並可由前述之方法及案例中驗證其表現。本研究目的在於緊急事件中,利用已知的建築物資訊模型與現場情況調整,快速提供救災團體「建物內第一次搜救之優良路徑」;旨在提升救難效率並減少人員損失,研究成果亦可為救災演練之使用。此外,本文探討之方法未來亦可用於其他建築物業相關之管理等。

並列摘要


During building emergencies, such as a fire disaster, an effective interior search could both enhance the efficiency of the rescue mission and help the incident commander make better further decisions on allocation of resources. The “primary search” of an emergency is the rapid search in every space to find victims and the gaining of situational awareness. However, due to ambiguous rules and lack of guidelines, an effective primary search is difficult to be performed in practice. As a result, to quickly find a set of interior patrol routes for rescue teams to conduct primary search, this research built the interior network with the given building information models (BIMs), and introduced the multiple traveling salesman problem (MTSP) to describe such situations. Moreover, to deal with the computational complexity and meet the objective of utilizations under real-time, we developed a column generation and branch and bound based algorithm to enhance the solution efficiency. A heuristic method was also introduced and tested to provide good solutions and performed well in the case study. The proposed method was recommended to be utilized in large scale buildings under emergency situations. As this study expects to both enhance the quality of rescue missions and reduce casualties, the method could be used to find interior patrol routes on-site, to practice drills beforehand, and to be applied to other construction-related tasks that requires operational efficiency of routing.

參考文獻


[1] R. Eadie, M. Browne, H. Odeyinka, C. McKeown, and S. McNiff, “BIM implementation throughout the UK construction project lifecycle: An analysis,” Autom. Constr., vol. 36, pp. 145–151, 2013.
[2] H. J. G. pd. Haynes, “Fire Loss in the United States During 2015,” 2016.
[3] P. R. Leblanc and J. L. Molis, “Firefighter Fatalities in the United States-2016,” 2017.
[4] J. K. Lenstra and A. H. G. Rinnooy-Kan, “Complexity of Vehicle Routing and Scheduling Problems,” Networks, vol. 11, no. 2, pp. 221–227, 1979.
[5] J. Hartmanis and J. Van Leeuwen, Combinatorial Optimization — Eureka, You Shrink!, vol. 2570. 2003.

延伸閱讀