埋在地下的多類管線若因天災人禍而造成毀損，將導致民生需求之水、電、瓦斯等物資無法以地下管線輸送給居民。修復這些毀損的多類管線皆需要歷經開挖、修復、及回填等多項工程。由於此類管線經常埋在道路下，在其開挖後但尚未回填的期間極可能造成交通壅塞不便，特別當類型不同的管線可能個別需要特定修復技能、且可能隸屬不同公司的修復工作隊時，如何合宜地安排開挖與各類管線修復等各項工程之進行時程，以讓各段節線上的民眾等待水、電、瓦斯等物資的時間以及因維修造成之交通不便時間總和越短越好，是災後管理中的重要議題，也是本研究主要探討的管線網路修復排程問題。
本研究之主要貢獻在於首度將同段節線的道路開挖、多類型管線修復、以及對交通不便的影響性一併列入排程考慮，首先我們以單類管線修復排程文獻的整數規劃模式為基礎，將此排程問題視為一個具資源限制下之專案排程問題(Resource Constrained Project Scheduling Problem，RCPSP)，並推導出一個時空網路中基於多商品流量的排程整數規劃模式；為能更有效地求解，我們設計兩種貪婪演算法，依排程當下各節線各類型管線的物資連通狀態，優先選取至少一端未連通的毀損邊界節線，來進行各類開挖及修復工程；為能再更進一步改善求解品質，我們亦參考平行機台文獻中的基因演算法，修改成符合本研究題目的流程。測試結果顯示本研究所提出之貪婪演算法的確能有效地在短時間內獲得品質還好的可行解，若以其當最佳化軟體GUROBI或基因演算法的初始解，亦可幫助提早收斂求解過程。然而可能因為本問題困難度實在太高，目前為止我們所發展的基因演算法疊代多次之後仍不易跳脫出貪婪演算法所獲得的初始解，最後我們提出包括納入道路開挖而未修復的時間上限、如何偵測評估毀損狀況排程等數個富挑戰性的研究議題。

This thesis investigates how to effectively restore damaged underground pipeline networks in post-disaster management. Suppose the location and restoration time for each damaged arc of different commodities (water, gas, electricity, …, etc.), as well as the number of excavation and restoration teams for different commodity networks, have been estimated. The arc restoration scheduling problem seeks the optimal restoration schedule that effectively assigns restoration teams of different commodities to restore all the damaged arcs in specific time and order, so that the total waiting time of all demands of all commodities, including the induced traffic inconvenience, can be minimized. We view this NP-hard problem as a specialized resource constrained project scheduling problem with network structure. It is especially difficult since the precedence relations between arcs are not clear, and highly dependent on the earlier scheduling decisions. In addition, the excavation has to be done before any restoration tasks, yet parallel pipeline restorations of different commodities on the same arc can be conducted at the same time.
We propose an integer programming formulation and derive a few valid inequalities in the hope to shorten the solution time. Two greedy heuristic algorithms, Generic Greedy Algorithm (GGA) and Boundary Greedy Algorithm (BGA), are designed to calculate good scheduling decisions in greedy fashions. BGA performs better than GGA since it selects boundary arcs of shorter restoration time or larger demands to restore. A Genetic Algorithm (GA) modified from previous works in parallel machine scheduling has been implemented. We have generated random networks of tree or general topologies. The computational experiments indicate the integer programming formulation solved by GUROBI, a state-of-the-art solver, is too time consuming. BGA produces better schedules than GGA. Using the BGA solution as a start for GA and GUROBI does improve the qualities of solutions, but then we are troubled in getting off local optimum.

Coelho, J. ,& Vanhoucke,M., (2011) , “Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers,” European Journal of Operational Research, 213(1) , 73-82.
Heath, E.A. , & Mitchell, J.E. , & Sharkey, T.C, (2016) , “Applying ranking and selection procedures to long-term mitigation for improved network restoration,” Journal on Computational Optimization, 4(3) ,447-481.
Averbakha, I. ,& Pereira, J. , (2012) , “The flowtime network construction problem,” IIE Transactions, 44(8) , 681-694.
Nurre,S.G. ,& Sharkey,T.C., (2014) , “Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules,” Networks, 63(4) , 306-336.
Averbakha, I. , (2012) , “Emergency path restoration problems,” Discrete Optimization, 9 , 58-64.
Nurre,S.G. ,& Cavdaroglua,B. ,& Mitchellb,J.E. ,& Sharkeya,T.C. ,& Wallacea,.W.A. , (2012) , “Restoring infrastructure systems: An integrated network design and scheduling (INDS) problem,” European Journal of Operational Research, 223(3) , 794-806

Nurre,S.G. ,& Sharkey,T.C. , (2015) , “Online Integrated Network Design and Scheduling Problems with Flexible Release Dates,”
Tabucchi,T. ,& Davidson,R. ,& Brink,S.(2010) , “Simulation of post-earthquake water supply system restoration,” Civil Engineering and Environmental Systems, 27(4) , 263-279
Hung,T.M.(2015) , “A multi-mode network restoration problem in post-disaster humanitarian logistics management,” National Cheng Kung University, Tainan, Taiwan.
Lin,P.C. , (2016) , “An arc restoration scheduling problem for pipeline networks in post-disaster management,” National Cheng Kung University, Tainan, Taiwan.
Vallada, E., & Ruiz, R. , (2011) , “A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times., ”European Journal of Operational Research, 211(3) , 612-622
Debels,D.,& Vanhoucke,V. , (2005) , “A bi-population based genetic algorithm for the resource-constrained project scheduling problem,” Lecture Notes in Computer Science, 3484, 378-387.
Brucker,P. ,& Knust,S. ,& Schoo,A. ,& Thiele,O. , (1998) , “A branch and bound algorithm for the resource-constrained project scheduling problem,” European Journal of Operational Research , 107 ,272-288
Vallada,E.,& Rubén,R. , (2011) , “A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times,” European Journal of Operational Research , 211 ,612-622
Valls,V.,& Ballesti ́n,F. , & Quintanilla,S. , (2008) , “A hybrid genetic algorithm for the resource-constrained project scheduling problem,” European Journal of Operational Research , 185 ,495-508