災後管理之管線網路最佳節線修復排程研究

Abstract

地下管線系統常被用來輸送水、天然氣、電力、或通訊封包等生活必須物資，而其需求主要分佈在管線網路之節線上。倘若地震、颱風等天災或恐怖攻擊等人禍導致網路的節線受損，勢必將對倚賴該毀損管線生活的居民造成極大不便，因此這些管線的修復排程便成為災後管理中非常重要的決策。本研究探討此種必須連通至供給點方能接受物資流量的特殊網路修復問題，假設每條毀損管線所影響的需求以及其修復時間皆為已知，欲求解修復所有毀損管線的最佳排程，以使生活受其影響的居民之總體等待物資時間越短越好。 本研究依實務現況，將需求設定成分佈在節線而非傳統文獻之節點上。先證明該排程問題為NP-hard，再提出一網路縮減機制整合未毀損節線的效能，將原網路簡化成較小但僅包含受損節線的等效網路，以提高其最佳修復排程之求解效率。針對以單一工作隊來修復所有毀損管線的特例，本研究以「具資源限制下之專案排程問題」(Resource Constrained Project Scheduling Problem，RCPSP)為基礎，提出自可連通供給點的節點開始修復的整數規劃模式；而在考量多組工作隊修復模式時，為了確保修復過程中已與外界連通節點或節線的「持續連通性」（該節點或節線在後續的修復過程中應持續保持與供給點的連通），我們提出兩個整數規劃模式：(1)利用Branch-and-Cut(B&C)架構之模式，在求解過程中一遇到獨立子迴圈即產生新限制式排除之，直至該整數規劃解不含獨立子迴圈之排程為止，以及(2)使用多商品網路流量(Multi-Commodity Network Flows，MCF)之模式，以各節點是否已收到供給點提供的單位虛擬流量來判斷當下是否已連通外界，再推導可加速其求解之有效不等式(Valid Inequality)，並將其延伸成可處理不同修復能力的多組工作隊修復排程數學模式。 為了解決當網路規模變大導致整數規劃模式求解緩慢的問題，本研究設計了「分段式啟發演算法」(Sequential Segment Heuristic，SSH)，將總修復時間切成多個較小求解區段(Time Horizon)再依序求解之；而針對單一工作隊的特例則設計了「貪婪樹生成法」(Greedy Tree method，GT)、「貪婪連通分量生成法」(Greedy Connected Component method，GCC)等兩種貪婪式演算法，以不同的貪婪法則決定各節線修復順序，與 「窮舉法」(Brute Force method)比較後得知GT與GCC在求解樹狀與一般網路時皆可在短時間內求出近似最佳解，而GT在稍加修正後亦可處理一般網路測資；以上針對單一工作隊所求解而得的管線修復排程皆可再進一步加上多組工作隊的指派決策，以處理多組工作隊修復排程問題。此外，鑑於多組工作隊修復排程問題與平行機台排程問題相關，本研究亦參考常用於平行機台排程的基因演算法流程，以各工作隊預計修復之節線編號依序排列成染色體，設計三個基因演算法：(1)使用平行機台排程文獻建議的交配與突變策略，(2)與(3)則改良(1)交配與突變後染色體的節線排序方式，讓較接近供給點的節線較能優先被修復。 在測試過數組隨機產生的樹狀網路(Tree Graph)、一般網路(General Graph)以及較符合現實情況大小的網路後，我們推薦使用SSH與GCC等兩種啟發式演算法以在短時間內求得品質不錯(Optimality Gap <2%)的近似最佳解；基因演算法雖在求解一般網路時表現尚可(數秒內Optimality Gap約 <4%)，但求解樹狀網路之效果不佳；而最佳解則建議使用MCF之模式。

Date of Award	2016 Aug 24
Original language	Chinese
Supervisor	I-Lin Wang (Supervisor)