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

This thesis investigates a network restoration problem, the first step in humanitarian logistics management, where the time and resources for restoring broken roads (arcs) are given, and the objective is to access all shelters (nodes) as soon as possible. Compared with literature, we are the first to consider multiple modes of network restoration, including multiple teams and team collaboration. Our proposed integer program formulation is based on the resource constrained project scheduling problem, but is much more challenging since no clear precedence relations can be defined in a general network. Several effective heuristics are proposed to calculate good initial solutions, more accurate estimation on the bounds of planning horizon, and feasible solutions of good qualities efficiently. Computational experiments have been conducted over random network families of grid, tree, and path shapes. The results indicate our proposed sequential segment heuristics that partition the planning horizon into segments and iteratively calculate local optimal schedules for each segment can calculate a good solution of small optimality gap within much shorter time than the integer program.

Aksu, D.T. and L. Ozdamar, (2014), “A mathematical model for post-disaster road restoration: Enabling accessibility and evacuation,” Transportation Research Part E: Logistics and Transportation Review, 61, 56-67.
Altay, N. and W.G. Green III, (2006), “OR／MS research in disaster operations management,” European Journal of Operational Research, 175(1), 475-493.
Averbakha, I., (2012), “Emergency path restoration problems,” Discrete Optimization, 9, 58-64.
Averbakha, I. and J. Pereira, (2012), “The flowtime network construction problem,” IIE Transactions, 44(8), 681-694.
Blazewicz, J., J.K. Lenstra and A.H.G. Rinnooy Kan, (1983), “Scheduling subject to resource constraints Classification and complexity,” Discrete Applied Mathematics, 5(1), 11-24.
Brucker, P., (2007), Scheduling algorithm5th, Springer Press, New York.
Coelho, J. and M. Vanhoucke, (2011), “Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers,” European Journal of Operational Research, 213(1), 73-82.
Debels, D. and M. Vanhoucke, (2005), “A bi-population based genetic algorithm for the resource-constrained project scheduling problem,” Lecture Notes in Computer Science, 3484, 378-387.
Debels, D. and M. Vanhoucke, (2007), “A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem,” Operations Research, 55(3), 457-469.
Hartmann, S. and D. Briskorn, (2010), “A survey of variants and extensions of the resource-constrained project scheduling problem,” European Journal of Operational Research, 207(1), 1-14.
Krüger, D. and A. Scholl, (2010), “Managing and modelling general resource transfers in (multi-)project scheduling,” OR Spectrum, 32(2), 369-394.
Li, K.Y. and R.J. Willis, (1992), “An iterative scheduling technique for resource-constrained project scheduling,” European Journal of Operational Research, 56(3), 370-379.
Liberatore, F., M.T. Ortuño, G. Tirado, B. Vitoriano and M.P. Scaparra, (2014), “A hierarchical compromise model for the joint optimization of recovery operations and distribution of emergency goods in humanitarian logistics,” Computers & Operations Research, 42, 3-13.
Matisziw, T.C., A.T. Murray and T.H. Grubesic, (2010), “Strategic network restoration,” Networks and Spatial Economics, 10(3), 345-361.
Meshkovskiy, K.A. and A.Y. Rokotyan, (1992), “Restoration of communications network connectivity following the failure of transmission junctions and lines,” Telecommunications and Radio Engineering, 47, 1-5.
Mingozzi, A., V. Maniezzo, S. Ricciardelli and L. Bianco, (1998), “An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation,” Management Science, 44(5), 714-729.
Nurre, S.G., B. Cavdaroglu, J.E. Mitchell, T.C. Sharkey and W.A. Wallace, (2012), “Restoring infrastructure systems: An integrated network design and scheduling (INDS) problem,” European Journal of Operational Research, 223(3), 794-806.
Talbot, F.B., (1982), “Resource-constrained project scheduling with time-resource tradeoffs - the nonpreemptive case,” Management Science, 28, 1197-1210.
Ven Peteghem, V. and M. Vanhoucke, (2010), “A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem,” European Journal of Operational Research, 201(2), 409-418.
Yan, S. and Y.L. Shih, (2009), “Optimal scheduling of emergency roadway repair and subsequent relief distribution,” Computers & Operations Research, 36(6), 2049-2065.