 |
|
|
|
以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：18 、訪客IP：18.219.22.169
姓名 施佑林(Yu-Lin Shih) 查詢紙本館藏 畢業系所 土木工程學系 論文名稱 供需面大型擾動下災後公路搶修排程模式暨求解演算法之研究
(Optimal Scheduling and Solution Algorithms for the Highway Emergency Repair Problem under Large-Scale Supply-Demand Perturbations)相關論文 檔案 [Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
摘要(中) 天然災害常發生並造成生命與財產的重大損失，如地震、火山爆發、土石流等。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.
關鍵字(中) ★ 時空網路
★ 供需面大型擾動
★ 災後公路搶修排程
★ 螞蟻族群演算法
★ 門檻值接受法關鍵字(英) ★ large-scale supply-demand perturbation
★ emergency repair
★ threshold accepting algorithm
★ ant colony system algorithm
★ time-space network論文目次 摘要 i
Abstract ii
誌謝 iii
Contents iv
List of Tables vii
List of Figures ix
Chapter 1 Introduction 1
Chapter 2 Essay 1: An Ant Colony System-Based Hybrid Algorithm for an Emergency Roadway Repair Time-Space Network Flow Problem 5
2.1. Introduction 5
2.2. The model 8
2.2.1 Emergency repair time-space network 8
2.2.2 The model formulation 9
2.3. Development of an Ant Colony System-Based Hybrid Algorithm (ACSB) 10
2.3.1 Generation of an initial solution 11
2.3.2 Generation of feasible solutions 12
2.3.3 State transition rule 14
2.3.4 Dynamic time-space roadway network updating rule 15
2.3.5 Local search 16
2.3.6 Pheromone updating rules 16
2.3.7 Path-and-time tracing method 17
2.3.8 TA strategy 18
2.3.9 Stopping criterion 18
2.4. Numerical tests 18
2.4.1 Data analysis and test results 19
2.4.2 ACSB parameters 21
2.4.2.1 Number of ants 21
2.4.2.2 State transition rule parameters 21
2.4.2.3 Pheromone updating rule parameters 22
2.4.2.4 TA strategy parameters 23
2.4.2.5 Stopping criterion parameter SU 23
2.4.3 Evaluation for different roadway network patterns 25
2.5. Conclusions and Suggestions 30
Chapter 3 Essay 2: Optimal Scheduling for Highway Emergency Repair Problems under Large-Scale Supply-Demand Perturbations 33
3.1. Introduction 33
3.2. The Time-Space network design 35
3.2.1 Real practices and Modeling issues 35
3.2.2 Time-space network for emergency repair under large-scale supply-demand perturbations 38
3.3. The model and the algorithm 44
3.3.1 The model 44
3.3.2. Segmenting optimization algorithm (SOPT) 50
3.4. Case study 51
3.4.1 Data analysis and test results 51
3.4.2 The total number of back-up work teams 53
3.4.3 The number of back-up work teams at each intersection 54
3.4.4 The perturbation tolerance 55
3.4.5 Tolerable perturbation time 55
3.5. Conclusions and discussion 56
Chapter 4 Essay 3: Hybrid Global Search Algorithms for Highway Emergency Repair Problems under Large-Scale Supply-Demand Perturbations 58
4.1. Introduction 58
4.2. The model 59
4.2.1 Time-space network for emergency repair under large-scale supply-demand perturbations 60
4.2.2 The model formulation 61
4.3. Development of the Ant Colony System Based Hybrid Algorithms 63
4.3.1 HGS-I algorithm 63
4.3.1.1 Generation of feasible solutions 65
4.3.2 HGS-II algorithm 67
4.3.2.1 Generation of feasible solutions 68
4.3.3 HGS-III algorithm 70
4.3.3.1 Generation of feasible solutions 71
4.4. Case Study 73
4.4.1 Data analysis and test results 73
4.4.2 HGS parameters 75
4.4.2.1 Number of ants 76
4.4.2.2 The state transition rule parameters 77
4.4.2.3 The pheromone updating rule parameters 77
4.4.2.4 TA strategy parameters 78
4.4.2.5 Stopping criterion parameter 79
4.4.2.6 Extra parameters for HGS-III 79
4.4.2.7 Combinational of the individually best parameters 80
4.4.3 Scenario analysis for different supply-demand situations 82
4.5. Conclusions and Suggestions 85
Chapter 5 Conclusions, Suggestions and Contributions 87
5.1 Conclusions 87
5.2 Suggestions 88
5.3 Contributions 89
References 90
Appendix 1: The emergency repair model by Yan and Shih (2007) 93
Appendix 2: Test results for HGS parameters 97
參考文獻 Abachizadeh M., and Tahani M., 2009. An ant colony optimization approach to multi-objective optimal design of symmetric hybrid laminates for maximum fundamental frequency and minimum cost. Struct Multidisc Optim, 37, 367–376.
Ardekani SA, Hobeika A. Logistics problems in the aftermath of the 1985 Mexico city earthquake. Transportation Quarterly 1988; 42: 107-124.
Ardekani SA. Transportation operations following the 1989 Loma Prieta earthquake. Transportation Quarterly 1992; 46: 219-233.
Arimura M., Tamura T. and Saito K., 1999. Application of genetic algorithms model for road investment of restoration planning. Journal of the 2nd Eastern Asia Society for Transportation Studies, 55-69.
Barbarosoğlu G, Őzdamar L, Çevik A. An interactive approch for hierarchical analysis of helicopter logistics in disaster relief operations. European Journal of Operational Research 2002; 140(1): 118-133.
Brown G.G., Vassiliou AL. Optimizing disaster relief: real-time operational and tactical decision support. Naval Research Logistics 1993; 40: 1-23.
Bullnheimer B., Hartl R.F. and Strauss C., 1999. Applying the ant system to the vehicle routing problem. In: S. Voss, S. Martello, I.H. Osman and C. Roucairol, eds. Meta-heuristics: advances and trends in local search paradigms for optimization. Kluwer: Boston.
Chen Y.W. and Tzeng G.H., 1999. A fuzzy multi-objective model for reconstructing the post-quake road-network by genetic algorithm. International Journal of Fuzzy Systems, 1(2): 85-95.
Chen, C.H., Yan, S. and Tseng, C.H., 2010. Inter-city bus scheduling for allied carriers. Transportmetrica , 6(3) , 161-185.
Cluskey, J.M., 1979. Road form and townscape. Architectural Press.
Costa D. and Hertz A., 1997. Ants can colour graphs. Journal of the Computer Science, 34, 39-53.
Di Caro, G. and Dorigo, M., 1998. AntNet: dic control for communications networks. Journal of Artificial Intelligence Research, 9, 317-365.
Dorigo, M and Gambardella, L.M., 1997a. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.
Dorigo, M. and Gambardella, L.M., 1996. A study of some properties of ant-Q. Proceedings of PPSN IV-Fourth International Conference on Parallel Problem Solving From Nature, September 22-27, 1996, Berlin, Germany, Berlin: Springer-Verlag, 656-665.
Dorigo, M. and Gambardella, L.M., 1997b. Ant colonies for the traveling salesman problem. BioSystems, 43, 73-81.
Dorigo, M., Maniezzo, V. and Colorni, A., 1996. The ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1), 29-41.
Dueck, G. and Scheuer, T., 1990. Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics, 90, 161-175.
Feng, C.M. and Wang, T.C., 2003. Highway emergency rehabilitation scheduling in post-earthquake 72 hours. Journal of the 5th Eastern Asia Society for Transportation Studies, 3276-3285.
Feng, C.M. and Wang, T.C., 2005. Seismic emergency rehabilitation scheduling for rural highways. Transportation Planning Journal, 34(2), 177-210 (in Chinese).
Fiedrich, F., Gehbauer, F. and Rickers, U., 2000. Optimized resource allocation for emergency response after earthquake disasters. Safety Science, 35, 41-57.
Garey, M.R. and Johnson, D.S., 1979. Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman & Company, San Francisco.
Haghani A, Oh S., 1996. Formulation and solution of a multi- commodity, multi-modal network flow model for disaster relief operations. Transportation Research Part A, 30(3), 231-250.
Hobeika AG, Ardekani SA, Han DL., 1988. Logistics decisions following urban disasters. Microcomputers in Civil Engineering, 3(1), 13-27.
Kemball-Cook D, Stephenson R. Lessons in logistics from Somalia. Disasters 1984; 8: 57-66.
Knott R., 1988. Vehicle scheduling for emergency relief management: a knowledge-based approach. Disasters, 12, 285-293.
Kolahan, F., Abachizadeh, M. and Soheili, S., 2006. A comparison between ant colony and tabu search algorithms for job shop scheduling with sequence-dependent setups. WSEAS transactions on systems, 12(5), 2819–2824.
Kuntz, P. and Snyers, D., 1997. Emergent colonization and graph partitioning. Proceedings of the 3th International Conference on Simulation of Adaptive Behavior: From Animals to Animate 3, The MIT Press, Cambridge, MA.
Montemanni, R., Gambardella, L.M., Rizzoli, A.E. and Donati, A.V., 2005. Ant colony system for a dynamic vehicle routing problem. Journal of Combinatorial Optimization, 10, 327-343.
Moore, E.F., 1957. The shortest path through a maze. Proceedings of an International Symposium on the Theory of Switching, Harvard University Press, Cambridge, Massachusetts, 285-292.
Oh SC, Haghani A. Testing and evaluating of a multi-commodity network flow model for disaster relief management. Journal of Advanced Transportation 1996; 31(2): 249-282.
Sato, T. and Ichii, K., 1996. Optimization of post-earthquake restoration of lifeline networks using genetic algorithms. Japan Society of Civil Engineers, 537 (I-35), 245-256.
Serra, M. and Venini, P., 2006. On some applications of ant colony optimization metaheuristic to plane truss optimization. Structural and Multidisciplinary Optimization, 32(6), 499–506.
Shyu, S.J., Yin, P.Y. and Lin B.M.T., 2004. An ant colony optimization algorithm for the minimum weight vertex cover problem. Annals of Operations Research, 131, 283-304.
Stützl, T. and Dorigo, M., 1999. ACO algorithms for the quadratic assignment problem. In D. Corne and F. Glover, eds. New Ideas in Optimization. McGraw-Hill.
Talbi, E.G., Roux, O., Fonlupt, C. and Robillard, D., 2001. Parallel ant colonies for the quadratic assignment problem. Future Generation Computer Systems, 17, 441–449.
Tamura, T., Sugimoto, H. and Kamimae, T., 1994. Application of genetic algorithms to determining priority of urban road improvement. Japan Society of Civil Engineers, 482(IV-22), 37-46.
Yan, S. and Shih, Y.L., 2007. A time-space network model for work team scheduling after a major disaster. Journal of the Chinese Institute of Engineers, 30(1), 63-75.
Yan, S. and Shih, Y.L., 2009. Optimal scheduling of emergency roadway repair and subsequent relief distribution. Computers & Operations Research, 36(6), 2049-2065.
Yan, S., Juang, D.H., Chen, C.R. and Lai, W.S., 2005. Global and local search algorithms for concave cost transshipment problems. Journal of Global Optimization, 33(1), 123-156.
Yan, S., Lai, W. and Chen, M., 2008. Production scheduling and truck dispatching of ready mixed concrete. Transportation Research Part E, 44(1), 164-179.
Yan, S., Lo, S.C. and Gu, W.F., 1994. The comparison of complexity and real computation time on various shortest path algorithms. Transportation, 24, 11-24 (in Chinese).
Yan, S., Tang, C.H. and Lee, M.C., 2007. A flight scheduling model for Taiwan airlines under market competitions. OMEGA - The International Journal of Management Science, 35, 61-74.
指導教授 顏上堯(Shangyao Yan) 審核日期 2010-7-26 推文 plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
網路書籤 Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit