供需面大型擾動下災後公路搶修排程模式暨求解演算法之研究; Optimal Scheduling and Solution Algorithms for the Highway Emergency Repair Problem under Large-Scale Supply-Demand Perturbations

NCU Institutional Repository > 工學院 > 土木工程研究所 > 博碩士論文 > Item 987654321/43323

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/43323

題名:	供需面大型擾動下災後公路搶修排程模式暨求解演算法之研究;Optimal Scheduling and Solution Algorithms for the Highway Emergency Repair Problem under Large-Scale Supply-Demand Perturbations
作者:	施佑林;Yu-Lin Shih
貢獻者:	土木工程研究所
關鍵詞:	時空網路;供需面大型擾動;災後公路搶修排程;螞蟻族群演算法;門檻值接受法;large-scale supply-demand perturbation;emergency repair;threshold accepting algorithm;ant colony system algorithm;time-space network
日期:	2010-07-26
上傳時間:	2010-12-08 13:34:32 (UTC+8)
出版者:	國立中央大學
摘要:	天然災害常發生並造成生命與財產的重大損失，如地震、火山爆發、土石流等。1999年的921集集大地震，其所造成的災害和政府之救援效率等問題，凸顯出大型災害緊急應變作業之重要性。以往工程單位的實務搶修上，一般是由決策者依經驗進行規劃，但憑經驗的指派方式卻缺乏系統最佳化分析，故決策雖可行，但並非最佳及最有效率之決策。近來曾有研究針對搶修工作隊排程發展一最佳化模式，以有系統性的解決災後搶修工作隊指派問題。然而，其無法在短時間內求得最佳解。因此本研究先針對此一問題發展一求解演算法。再者，實際上災害發生後，常會發生二次災害、三次災害等不確定因素，其將造成災點搶修延誤或產生新的災點等大規模擾動事件，其將擾亂原先的工作隊搶修排程，進而影響後續搶救資源指派的績效。除了上述需求面的大型擾動問題之外，供給面之大型擾動問題亦會擾亂原先的工作隊搶修排程，如非災區之縣市、中央政府以及軍方亦可能會陸續增派支援工作隊到災區進行搶修，以加速災區的復原工作。緣此，本研究針對此問題發展一供需面大型擾動下災後公路搶修排程最佳化模式與求解演算法。本研究分為三個部份。第一部份先針對災後公路搶修排程模式，利用螞蟻族群演算法並結合門檻值接受法，發展一求解演算法以求解此問題。為測試本研究演算法之效率，本研究以類似集集大地震相同規模之災害為例，做一較接近實際狀況之範例研究，測試分析本研究所發展之演算法的求解績效。第二部份利用時空網路流動技巧，構建供需面擾動下災後公路搶修排程作業之數學模式，並以C程式語言並配合CPLEX數學規劃軟體，發展一啟發式演算法求解模式，以改善求解效率。為評估此演算法之求解績效，本研究進行一範例研究，測試模式與啟發解法的績效，初步結果甚佳，可為學術界與實務界之參考。第三部份則針對此一搶修排程擾動問題，探討其特性，並參考螞蟻族群演算法之搜尋觀念，並加入門檻值接受法之演算特色，並根據其目標特性，發展三個有效率之混合式全域搜尋演算法。為評估此三個演算法之求解績效，本研究以類似921集集大地震相同規模之災害為例，做一較接近實際狀況之範例研究，測試分析本研究所發展之演算法的求解績效，其結果甚佳，可為學術界與實務界之參考。 Natural disasters, such as earthquakes, volcanic eruption, mudflows and landslides, have significant devastating effects in terms of human injuries and property damages. The 1999 Chi-chi earthquake not only indicated the low efficiency of the government for dealing with the rescue operations but also revealed the importance of the emergency repair. In the past, the emergency repair was usually planned by decision makers according to their own experiences, lacking of systematic analyses. The resultant operation could possibly be a feasible yet inferior. Recent research has developed a model that finds the optimal work team routes for emergency road repairs to improve scheduling efficiently. However, it is difficult to optimally solve the problem within the shortest possible period of time. Therefore, we first develop a solution algorithm for this problem. Furthermore, a major disaster leads to subsequent “secondary” or “tertiary disasters” in practice, which delays the repair time or generates new damaged points. These large-scale perturbation problems will disrupt the original work teams’ repair schedule and will affect the follow-up resource assignment. In addition to the large-scale demand-side perturbation, the large-scale supply-side perturbation also affects the original schedule. For example, new work teams could be later supported by government, military or civil agencies, for more effective emergency repair. Therefore, we develop a model and solution algorithms for the highway emergency repair problem under large-scale supply-demand perturbations. This dissertation consists of three essays. In the first essay, an ant colony system algorithm is employed, along with the threshold accepting technique, to develop an ACS-based hybrid algorithm capable of efficiently solving an emergency roadway repair time-space network flow problem. To test how well the algorithm may be applied to actual operations, a case study is carried out using data from the Chi-Chi earthquake in Taiwan. In the second essay, we develop a model and solution algorithms for the highway emergency repair problem under large-scale supply-demand perturbations. We employ the time-space network flow technique to develop a model that can help the authority decide on the best adjustment of highway emergency repair schedule. We use the C computer language, coupled with the CPLEX mathematical programming solver, to develop a heuristic algorithm for efficiently solving this problem. To evaluate the solution algorithms, we perform a case study. The results are good, showing that the model and heuristic algorithm could be useful. In the third essay, based on the problem’s characteristics, and ant colony system algorithm, we further develop three global search algorithms, coupled with the techniques of the threshold accepting algorithm and efficiently solve the problem. To evaluate the solution algorithms, we perform a case study on a scale similar to that of Chi-chi earthquake. The results are good, showing that the model and the algorithms may be useful in practice.
顯示於類別:	[土木工程研究所] 博碩士論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	663	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....