成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	林秉錚 Lin, Ping-Cheng
論文名稱：	災後管理之管線網路最佳節線修復排程研究 An arc restoration scheduling problem for pipeline networks in post-disaster management
指導教授：	王逸琳 Wang, I-Lin
學位類別：	碩士 Master
系所名稱：	管理學院 - 資訊管理研究所 Institute of Information Management
論文出版年：	2016
畢業學年度：	104
語文別：	中文
論文頁數：	88
中文關鍵詞：	網路修復問題、災後管理、整數規劃、專案排程問題
外文關鍵詞：	Network Restoration, Post-disaster Management, Integer Program, Project Scheduling Problem
相關次數：	點閱：98 下載：19
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

地下管線系統常被用來輸送水、天然氣、電力、或通訊封包等生活必須物資，而其需求主要分佈在管線網路之節線上。倘若地震、颱風等天災或恐怖攻擊等人禍導致網路的節線受損，勢必將對倚賴該毀損管線生活的居民造成極大不便，因此這些管線的修復排程便成為災後管理中非常重要的決策。本研究探討此種必須連通至供給點方能接受物資流量的特殊網路修復問題，假設每條毀損管線所影響的需求以及其修復時間皆為已知，欲求解修復所有毀損管線的最佳排程，以使生活受其影響的居民之總體等待物資時間越短越好。

本研究依實務現況，將需求設定成分佈在節線而非傳統文獻之節點上。先證明該排程問題為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之模式。

Pipeline networks that ship flows of gas, water, electricity, or packets are important for supporting our daily livings. Suppose arcs of a pipeline network are damaged by disasters and the limited resources (equipment, manpower, and time) required to restore each damaged arc have been estimated. We investigate the problem of when and who to restore which arcs such that the flows over pipelines become accessible for people among all arcs at minimum total waiting time in the post-disaster management. We first reduce the original network into an equivalent but smaller one where only damaged arcs are considered. Then, we propose two integer programs (Branch-and-Cut, Multicommodity Network Flows frameworks) for this special resource constrained project scheduling problem. Several valid inequalities are proposed to effectively shorten the computational time for integer programs. We also explain how to deal with more general cases where heterogeneous teams as well as their collaboration are considered for calculating an optimal network restoration schedule. Three fast heuristics are designed: Sequential Segment Heuristic (SSH), Greedy Tree method (GT), and Greedy Connected Component method (GCC), where SSH solves partitioned segments sequentially, and both GT and GCC first determine an arc restoration sequence in different greedy fashions and then assign tasks to different teams by a First-Come First-Served principle. We propose three variants of Genetic Algorithms (GA). Computational experiments indicate our heuristics could calculate solutions within 2% optimality gaps in seconds for large-scale networks. The GAs, on the other hand, perform a little worse with optimality gaps up to 5%.

摘要........................................... I
ABSTRACT....................................... III
誌謝........................................... VIII
目錄........................................... IX
表目錄 ......................................... XIII
圖目錄 ......................................... XV
第一章、緒論 ..................................... 1
1 研究背景與動機............................... 1
2 研究目的................................... 2
3 研究範圍................................... 4
4 論文架構................................... 5
第二章、文獻回顧................................... 6
1 整合網路設計與排程問題(INDS) ..................... 6
1.1 Pm|∑SP|Cmax−Threshold的NP-hard證明 . . . . . . . . . . . . . 8
1.2 INDS相關文獻............................ 10
2 具資源限制下之專案排程問題(RCPSP).................. 14
2.1 符號定義............................... 15
2.2 數學模式............................... 16
3 小結...................................... 17
第三章、網路節線修復問題之整數規劃模式............................. 18
1 問題描述................................... 18
2 問題假設................................... 19
3 NP-hard說明................................. 20
4 網路縮減機制 ................................ 21
5 單一工作隊特例適用RCPSP之推論 .................... 22
6 單一工作隊整數規劃模式(Ms)....................... 23
6.1 符號定義............................... 24
6.2 數學模式............................... 24
7 使用Branch-and-Cut (B&C) 之多工作隊整數規劃模式(Mm B&C) . . . . . . 27
7.1 符號定義............................... 28
7.2 數學模式............................... 28
7.3 有關排除獨立(未與外界連通)子迴圈機制之進階說明 . . . . . . 30
8 使用多商品網路流量 (Multi-commodity Network Flow,MCF) 之多工作隊整數規劃模式(Mm MCF)........................... 32
8.1 符號定義............................... 33
8.2 數學模式............................... 34
8.3 有效不等式 ............................. 35
9 考量工作隊能力不同之模式修改方式 ................... 36
10小結...................................... 38
第四章、節線修復排程演算法之設計................................... 39
1 分段式啟發演算法 (Sequential Segment Heuristic,SSH) . . . . . . . . . . . . . 39
1.1 演算法步驟 ............................. 40
1.2 範例說明............................... 43
2 窮舉法(Brute force method,BF)......................... 47
2.1 方法說明............................... 48
2.2 多組工作隊之修復任務分配方式 ................. 49
3 貪婪式演算法 ................................ 50
3.1 貪婪樹生成法(Greedy tree method,GT) ................ 50
3.2 貪婪連通分量生成法 (Greedy Connected Component Method,GCC) . . 53
4 基因演算法(GeneticAlgorithm,GA) ................... 55
4.1 基於多平行機台 (unrelated parallel machine) 排程問題的基因演算法 ................................. 55
4.2 修改交配策略 ............................ 59
4.3 基因演算法範例說明 ........................ 61
5 小結...................................... 63
第五章、模式與演算法之數值測試及分析 ................................... 64
1 測試網路資料 ................................ 64
2 單工作隊網路測試.............................. 65
2.1 整數規劃模式比較 ......................... 65
2.2 演算法測試 ............................. 66
3 多組工作隊網路測試 ............................ 67
3.1 有效不等式效益測試 ........................ 68
3.2 工作隊數量不同測試 ........................ 69
4 分段式啟發演算法測試 ........................... 72
4.1 nseg數固定 .............................. 72
4.2 α固定................................. 73
5 基因演算法測試 ............................... 73
6 現實大小之網路測試 ............................ 76
7 小結...................................... 80
第六章、結論與未來研究議題建議 ..................................... 81
1 結論...................................... 81
2 建議之未來研究議題................................... 85
參考文獻........................................ 87
                                    

Averbakh, I. (2012). Emergency path restoration problems. Discrete Optimization, 9(1), 58–64.
Averbakh, I., & Pereira, J. (2012). The flowtime network construction problem. IIE Trans- actions, 44(8), 681–694.
Baxter, M., Elgindy, T., Ernst, A. T., Kalinowski, T., & Savelsbergh, M. W. (2014). Incremental network design with shortest paths. European Journal of Operational Re- search, 238(3), 675–684.
Blazewicz, J., Lenstra, J. K., & Kan, A. R. (1983). Scheduling subject to resource con- straints: classification and complexity. Discrete Applied Mathematics, 5(1), 11–24.
Brucker, P. (2007). Scheduling algorithms (Vol. 3). Springer.
Cavdaroglu, B., Hammel, E., Mitchell, J. E., Sharkey, T. C., & Wallace, W. A. (2013). Integrating restoration and scheduling decisions for disrupted interdependent infras-tructure systems. Annals of Operations Research, 203(1), 279–294.
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.
Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109–124.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of discrete mathematics, 5, 287–326.
Huang, T. M. (2015). A multi-mode network restoration problem in post-disaster humanitarian logistics management (Master’s thesis). National Cheng Kung University, Tainan, Taiwan.
Kalinowski, T., Matsypura, D., & Savelsbergh, M. W. (2015). Incremental network design with maximum flows. European Journal of Operational Research, 242(1), 51–62.
Karp, R. M. (1972). Reducibility among combinatorial problems. Complexity of computer computations, 85–103.
Matisziw, T. C., Murray, A. T., & Grubesic, T. H. (2010). Strategic network restoration. Networks and Spatial Economics, 10(3), 345–361.
Nurre, S. G., Cavdaroglu, B., Mitchell, J. E., Sharkey, T. C., & Wallace, 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. (2014). Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules. Networks, 63(4), 306–326.
Padberg, M., & Rinaldi, G. (1991). A branch-and-cut algorithm for the resolution of large- scale symmetric traveling salesman problems. SIAM review, 33(1), 60–100.
Talbot, F. B. (1982). Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case. Management Science, 28(10), 1197–1210.
Vallada, E., & Ruiz, R. (2011). A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Oper- ational Research, 211(3), 612–622.
Wu, M. C. (2010). Biking route planning based on target calorie comsumption (Master’s thesis). National Cheng Kung University, Tainan, Taiwan.
Xu, N., Guikema, S. D., Davidson, R. A., Nozick, L. K., C ̧ag ̆nan, Z., & Vaziri, K. (2007). Optimizing scheduling of post-earthquake electric power restoration tasks. Earthquake engineering & structural dynamics, 36(2), 265–284.

校內：2021-09-01公開
校外：2021-09-01公開

簡易檢索 / 詳目顯示

相關論文