考慮多種修復方式之網路重建問題–以災後緊急救援物流管理之路網重建為例

Abstract

災後的道路網路修復問題為災後緊急救援管理的首要任務，如何指派適當的修復人力於適當時機修復適當的損壞路段，是災後能否迅速進入災區疏散、收容與撤離災民的重要關鍵。本研究將探討在掌握道路網之實際毀損情況下，如何動員現有的資源進行最有效率之緊急搶修計劃，並且決定工作隊等資源之修復路徑、各毀損道路之最佳修復方式及最佳的作業排程。有別於過去文獻，本研究首度考慮各路段有多種不同的修復方式、修復工作隊能力與可用資源亦可能不同、以及修復團隊能否合作等因素，提出具多種修復方式的緊急道路維修問題。 針對單一與無限組工作隊等兩種特例，本研究證明其可被轉換成最小展開樹問題（Minimum spanning tree MST）及最短路徑樹問題（Shortest path tree SPT）求解；接著，將探討介於一組至無限多組工作隊之一般情況，並以具資源限制下之專案排程問題（Resource Constrained Project Scheduling Problem RCPSP）為基礎以提出一整數規劃模式求解此NP-hard問題，其主要困難點在於一般網路的路段間並不存在明顯的先後時序關係。由於該整數規劃模式在求解規模龐大的網路重建問題時經常耗時甚久，故本研究提出數個加速求解技巧與演算法來計算更佳的初始解、估算更精準的完工時間、以及能更快地收斂出品質更好的可行解。其中，本研究所設計的分段式啟發演算法先將問題依時間切成數段，再由近而遠先求解較近災點的搶通方式，以其為基礎再逐漸擴張搶通範圍直到全部災點皆搶通為止；該演算法在我們測試過的三類不同形狀的數十個隨機路網後，皆能在極短時間內得到跟最佳解品質相近的可行解，優於最佳化軟體Gurobi的求解速度，也遠勝另外設計的粒子群演算法之求解表現。本研究所提出之方法除了可應用於災後路網重建問題外，亦可應用於災後或一般通訊網路重建等相關的網路修復問題。

Date of Award	2015 Sept 8
Original language	Chinese
Supervisor	I-Lin Wang (Supervisor)