日常生活中有許多服務必須在特定的地點與設施上進行，譬如自動櫃員機（ATM）、通信基地台、交通場站等皆可視為某些服務系統網路之節點。而各節點上的服務需求量除可能依時而變外，可再分為「單一節點」與「起訖組合」兩類，前者之服務需求僅發生在該節點上（譬如銀行、ATM等）；而後者則有賴起訖兩節點皆無故障時，方能滿足其起訖需求（譬如機場、YouBike租借站等）。假設各節點或起訖組合之依時變化需求量皆為已知或可被預測，但部分（或全部）的節點卻因天災人禍而毀損故障時，在故障期間於這些節點所發生之需求量將被捨棄（譬如某ATM當機導致無法領錢；或YouBike場站故障導致無法租還車等）。由於修復系統之人力或機具資源相對有限（假設共有K組維修團隊），本研究探討之節點修復排程問題旨在探討如何有效地指揮調度K組維修團隊去修復毀損之節點，以儘快讓更多人能更早享受原有之服務，極大化修復過程中可提供的服務效益。
由於我們考量K組維修團隊之各隊將逐一修復所有之故障節點，此與文獻中的K組旅行維修員問題（k-Traveling Repairmen Problem，k-TRP）相似，但本研究的目標函式還多考慮了節點需求的因時變動與即時性，較已為NP-hard之k-TRP更符合實務需求，因此其挑戰性與困難度亦更高。在可得理論精確解之數學規劃模式設計方面，我們提出三種整數規劃模式：(1)含排除子迴圈限制式(subtour elimination)之模式；(2)以時空網路(Time-Space Network)為基礎建構之模式，而後又可再依是否考慮旅行時間而再細分成「特例模式」及「一般模式」兩類；(3)以層空網路(Level-Space Network)為基礎建構之模式，其中(1)(3)可由k-TRP之數學模式為基礎來建構而得。
隨著網路規模擴大，數學規劃模式之求解過程極為耗時，因此本研究又提出結合貪婪演算法(Greedy Algorithm)與模式求解的數學啟發式演算法（Matheuristics），以優先修復最小損失需求的節點為選取機制，同時考量節點維修時間、旅行時間及依時而變之需求量，以演算法求得之數組層空網路路徑為基礎，反向建構出其對應之限縮模式網路，再進一步提出該網路以節線或路徑為變數等兩種整數規劃模式求解。
最後進行數學模式及演算法測試，若忽略節點間之旅行時間，則「單一節點」與「起訖組合」兩類問題之測試結果顯示，以時空網路為基礎所建構之模式有最好的求解表現；而在限縮模式網路下，則以路徑為變數所建構之模式求解效率較佳，針對單一節點需求類型問題，可在短時間內求得近似最佳解(Gap<1%)，但仍無法處理較大規模問題。至於起訖組合需求類型，大概只能靠貪婪演算法之解再以模擬退火法進一步改善之。因為我們建構限縮模式的數學啟發式演算法十分創新，希望未來能再利用類似想法處理其它類似的路徑規劃或排程問題。

We investigate node restoration scheduling problems for damaged service networks. Suppose all or some nodes in a service network are damaged by man-made or natural disasters, and the forecasted time-dependent demands on single nodes or between node pairs are known beforehand. We seek mathematical models and solution methods to schedule k teams to restore all damaged nodes, so that the demands after restoration can be maximized. Two demand types are considered: (1) node-only type, and (2) Origin-Destination (OD) pair type. The former focuses on demands at single working node only, whereas the latter considers demands between OD node pairs. Our problems are NP-hard, since the NP-hard k-Traveling Repairmen Problem corresponds to a special case of ours. Three integer programming models based on Subtour Elimination, Time-Space network, and Level-Space network are proposed, but very time consuming. We give an effective greedy heuristics, and use it to design matheheuristics that construct reduced formulations in both arc and path forms. Finally we give a Simulated Annealing heuristic (SA) to deal with larger problems. Computational experiments indicate the time-space models are the best to calculate the exact optimal solutions for node-only demand type problems of small to medium sizes. Our matheuristics, especially the path-form ones, can improve the solution quality of greedy heuristic for larger problems. For OD pair demand type problems, only the greedy heuristic, further improvable by SA, can deal with problems of medium to large sizes.

Averbakh, I. (2012). Emergency path restoration problems. Discrete Optimization, 9(1), 58-64.
Angel-Bello, F., Alvarez, A., & García, I. (2013). Two improved formulations for the minimum latency problem. Applied Mathematical Modelling, 37(4), 2257-2266.
Angel-Bello, F., Cardona-Valdés, Y., & Álvarez, A. (2017). Mixed integer formulations for the multiple minimum latency problem. Operational Research, 1-30.
Baez, S., Angel-Bello, F., & Alvarez, A. (2016). Time-dependent formulations for minimizing total completion time in a parallel machine scheduling problem with dependent setup times. IFAC-PapersOnLine, 49(12), 857-862.
Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3), 209-219.
Dewilde, T., Cattrysse, D., Coene, S., Spieksma, F. C., & Vansteenwegen, P. (2013). Heuristics for the traveling repairman problem with profits. Computers & Operations Research, 40(7), 1700-1707.
Fakcharoenphol, J., Harrelson, C., & Rao, S. (2003). The k-traveling repairman problem. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms (pp. 655-664). Society for Industrial and Applied Mathematics.
Jothi, R., & Raghavachari, B. (2007). Approximating the k-traveling repairman problem with repairtimes. Journal of Discrete Algorithms, 5(2), 293-303.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
Matisziw, T. C., Murray, A. T., & Grubesic, T. H. (2010). Strategic network restoration. Networks and Spatial Economics, 10(3), 345-361.
Luo, Z., Qin, H., & Lim, A. (2014). Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints. European Journal of Operational Research, 234(1), 49-60.
Nucamendi-Guillén, S., Martínez-Salazar, I., Angel-Bello, F., & Moreno-Vega, J. M. (2016). A mixed integer formulation and an efficient metaheuristic procedure for the k-Travelling Repairmen Problem. Journal of the Operational Research Society, 67(8), 1121-1134.
Sahni, S., & Gonzalez, T. (1976). P-complete approximation problems. Journal of the ACM (JACM), 23(3), 555-565.
Xu, N., Guikema, S. D., Davidson, R. A., Nozick, L. K., Çağnan, Z., & Vaziri, K. (2007). Optimizing scheduling of post‐earthquake electric power restoration tasks. Earthquake engineering & structural dynamics, 36(2), 265-284.