臺灣博碩士論文加值系統

以地震為主之天然災害經常導致嚴重程度災損。此對於特別是在人口高度集中之地區而言，數以千計之民眾將備受影響威脅甚或為死傷，對於重要救災功能之路網與運輸系統更造成巨大之破壞。為改善緊急救援工作效率之目的，有效率地使用有限之工程資源協助路網緊急搶修工作將是首要評估指標。受制於時間以及資源品質與數量，緊急救援管理者必須決定一最適排程計畫提出時間與空間規劃以指派工程資源處理路網搶修作業。如何協助其有效評估與處理搶修工作之災損情資以提升緊急性資源排程決策品質，在在顯示此為一重要課題。
本研究為有效解決此一組合最佳化問題，遂選以基因演算法為架構乃提出兩子模式加以解決相關問題。首先，以模糊數定義方式加以考慮搶修處理時間之模糊性。於演算法設計上整合模糊數排序方法於執行流程中，期許產製一實務可行以資排程決策。其二，以有限資源排程問題角度，採取共生式進化演算法架構為求解演算法機制，有效考慮多重專案與多單位工程資源之路網搶修排程問題。本研究各以設計範例以測試所提演算法之合理性，經由數值結果顯示求解效果良好，此一演算法確實可資路網搶修排程規劃。最後，文末討論未來相關課題之可能應用。

Major earthquakes often cause a high degree of damages. Especially in highly inhabited areas, thousands of people may be affected or killed. Lifeline networks as crucial road networks and transportation systems are damaged and lead to disruptions as well. One important aspect, which helps emergency relief operations improvements after an earthquake, is the performance that crucial road networks how fast to be restored as
possible in the first few days to weeks. The quality of the relief efforts can be improved by effective use of the available technical resources. Because time, quantity and quality of the resources are limiting factors, emergency managers do have to find an optimal schedule for assigning resources in space and time to affected roads. Therefore, the need for a method of scheduling all necessary works systematically in an adequate manner will be urgent.
Scheduling problem is NP-hard in nature. Due to quality of traditional heuristics, two enetic-based solution approaches are formulated and presented to solve in this study. First, decision variable as of duration is defined in fuzzy numbers. A fuzzy number arithmetic and ranking methods are introduced into the first algorithm to help to search potential solutions. Second, based on resource-constrained project scheduling problems (RCPSP) extended to multiple projects and multiple depots considerations, a symbiotic evolutionary algorithm is presented and solved. An efficient coding method for representation on decision variables is introduced and explored. Finally, experimental studies on test networks are conducted to demonstrate the proposed algorithms. Several results from numerical experiments show its validity. It does have some advantages and applicability on emergency restoration planning of damaged road networks.

第 一 章 緒論.........................................1-1
1.1 研究背景與動機....................................1-1
1.2 研究目的..........................................1-3
1.3 研究方法..........................................1-4
1.4 研究流程與架構....................................1-5
第 二 章 國內公路災害搶修作業現況與特性................2-1
2.1 國內公路災害搶修作業情形...........................2-1
2.2 公路搶修作業處理與緊急應變程序.....................2-2
2.3 公路災害搶修作業特性...............................2-6
2.4 小結...............................................2-8
第 三 章 文獻回顧......................................3-1
3.1 維生線網路修復問題.................................3-1
3.1.1 通信電力網路災後修復問題.........................3-1
3.1.2 路網災後修復問題.................................3-3
3.2 專案排程與模糊應用之相關文獻.......................3-8
3.2.1 模糊理論簡介.....................................3-8
3.2.2 排程與模糊專案排程問題...........................3-9
3.3 相關文獻評析.......................................3-10
第 四 章 研究方法與模式架構............................4-1
4.1 問題分析............................................4-1
4.1.1 問題說明..........................................4-1
4.1.2 問題特性..........................................4-2
4.2 基本假設............................................4-5
4.3 模式說明............................................4-7
4.3.1 模式構建想法......................................4-7
4.3.2 概念性模式........................................4-9
4.3.3 模式結構分析......................................4-14
4.4 求解方法.............................................4-15
4.4.1 基因演算法理論簡介.................................4-15
4.4.2 設計理念...........................................4-16
第 五 章 RS-1-GA演算法設計與測試.........................5-1
5.1 編碼與初始群體.......................................5-1
5.1.1 編碼...............................................5-1
5.1.2 初始群體...........................................5-3
5.2 適應值函數...........................................5-4
5.2.1 適應值函數.........................................5-5
5.2.2 模糊數排序.........................................5-5
5.3 運算子...............................................5-6
5.3.1 選擇...............................................5-6
5.3.2 交配...............................................5-7
5.3.3 突變...............................................5-8
5.4 執行流程.............................................5-10
5.5 範例測試與實驗.......................................5-11
5.5.1 範例說明...........................................5-12
5.5.2 實驗設計...........................................5-13
第 六 章 RS-m-GA演算法設計與測試.........................6-1
6.1 編碼概念與SEA架構....................................6-1
6.2 RS-M -GA演算法設計...................................6-2
6.2.1 SEA架構............................................6-2
6.2.2 共生伙伴選擇與適合度評估...........................6-4
6.3 案例研究與實驗.......................................6-4
6.3.1 案例說明...........................................6-4
6.3.2 測例1..............................................6-13
6.3.3 測例2..............................................6-17
第 七 章 結論與建議......................................7-1
7.1 結論.................................................7-1
7.2 建議.................................................7-2
參考文獻...................................................i

一、國內文獻
王擴為，公路搶修決策支援系統中指派模式之研究，國立交通大學資訊管理所碩士論文，民國八十二年。
交通部，財團法人台灣營建研究院，「九二一大地震災後交通設施強化與重建研討會」論文集，台灣台北，民國八十八年
十二月。
交通部公路總局，災害緊急處理與應變計劃，民國八十九年七月。
交通部公路總局，災害防救標準作業手冊，民國九十一年一月。
林豐正，「九二一大地震災後交通設施災損、搶修及復建」，都市交通季刊，第十四卷，第四期，民國八十八年十二月，
第1∼8頁。
林容駿，交通系統災後復舊策略發展模式，台灣工業技術學院營建工程所碩士論文，民國八十五年。
吳心琪，震災後工程搶修作業排程之研究，國立交通大學交通運輸研究所碩士論文，民國八十六年六月。
陳郁文，模糊多目標規劃基因演算法應用於提昇運輸系統災後應變效率之研究，國立交通大學交通運輸研究所博士論文，
民國八十八年七月。(英文)
連振盛，都市地區地震防救災交通系統之交通管制緊急應變計劃之研究，國立交通大學運輸工程與管理學系碩士論文，台
灣新竹，民國九十年六月。
張立偉，災後工程緊急搶修作業排程之研究，淡江大學運輸管理科學系運輸科學碩士班碩士論文，民國九十年六月。
許添本，「九二一集集大地震之交通衝擊與交通應變系統」，都市交通季刊，第十四卷，第四期，民國八十八年十二月，
第9∼21頁。
楊宗岳，「參與行政院921災後重建推動委員會交通組之後感」，台灣公路工程，第二十六卷，第十二期，民國八十九年六
月，第26∼40頁。
鄧文廣，「九二一集集大地震公路災害搶修及復健計劃簡介」，台灣公路工程，第二十七卷，第一期，民國八十九年七月
，第19∼23頁。
錢伯冠，「九二一集集大地震災害谷關工務段災情及搶修報告」，台灣公路工程，第二十六卷，第六期，民國八十八年十
二月月，第28∼35頁。
賴瓊華，完工時間限制限制下模糊計劃評核術之研究，國立成功大學工業管理研究所碩士論文，民國九十年六月。
二、國外文獻
Arimura, M., Tamura, T., and Saito. K.(1999). “Application of Genetic Algorithms model for Road Investment
of Restoration Planning,” Proceedings of the Eastern Asia Society for Transportation Studies, Vol. 2,
pp.55-69.
Auf der Heide, E.(1989). Disaster Response: Principles of Preparation and Coordination, Mosby, ISBN
0801603854. Online Book: http://coe-dmha.org/dr.
Bäck, T., Fogel, D.B., and Michalewicz, Z.(2000). Evolutionary Computation 1: Basic Algorithms and
Operators, IOP Publishing Ltd.
Bäck, T., Fogel, D.B., and Michalewicz, Z.(2000). Evolutionary Computation 2: Advanced Algorithms and
Operators, IOP Publishing Ltd.
Barbarosoğlu, G., Özdamar, L., and Cevik, A.(2002). “An Interactive Approach for Hierarchical Analysis of
Helicopter Logistics in Disaster Relief Operations,” European Journal of Operational Research, No.140,
pp.118-133.
Brown, G.G. and Vassiliou, A.L.(1993).“Optimizing Disaster Relief: Real-Time Operational and Tactical
Decision Support,” Naval Research Logistics, Vol.40, pp.1-23.
Brucker, P.(1998). Scheduling Algorithm, 2nd Revised and Enlarged Edition, Springer-Verlag, New York.
Chanas, S. and Kamburowski, J.(1981).“The use of fuzzy variable in PERT,” Fuzzy Sets and Systems, Vol.5,
pp.11-19.
Chang, S.E. and Nojima, N.(2001).“Measuring post-disaster transportation system performance: the 1995 Kobe
earthquake in comparative perspective,” Transportation Research — Part A, Vol. 35, pp.475-494.
Chang, S.E., Shinozuka, M., and Svekla, W.(1999).“Modeling Post-disaster Urban Lifeline Restoration,”
Optimizing Post-Earthquake Lifeline System Reliability, Proceedings of the Fifth U.S. Conference on
Lifeline Earthquake Engineering, Seattle, WA, August 12-14, pp.602-611.
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, Vol.1, No.2, pp.85-95.
Cook, R.A.(1991). “Loss and Recovery of Critical Lifelines Following Recent Hurricanes,” Technical
Council on Lifeline Earthquake Engineering, ASCE Monograph No.4, Cassaro, M.A.(editor). Proceedings of the
Third U.S. Conference on Lifeline Earthquake Engineering, Los Angeles, California, Aug.
Eguchi, R.T., Goltz, J.D., Seligson, H.A., Flores, P.J., Blais, N.C., Heaton, T.H., and Bortugno, E.(1997).
“Real-time Loss Estimation as An Emergency Response Decision Support System: the Early Post-earthquake
Damage Assessment Tool (EPEDAT).” Earthquake Spectra, Vol.13, No.4, pp. 815-832.
Esogbue, A.O.(1996). “Fuzzy sets modeling and optimization for disaster control systems planning,” Fuzzy
Sets and Systems, No.81, pp.163-183.
Fiedrich, F., Gehbauer, F., and Rickers, U.(2000). “Optimized Resource Allocation for Emergency Response
after Earthquake Disasters,” Safety Science, No.35, pp.41-57.
Fiedrich, F., Gehbauer, F., and Rickers, U.(2000). “Optimized Resource Allocation for Emergency Response
after Earthquake Disasters,” Safety Science, No.35, pp.41-57.
Gen, M. and Cheng, R.(1997). Genetic Algorithms and Engineering Design, John Wiley & Sons.
Gen, M. and Cheng, R.(2000). Genetic Algorithms and Engineering Optimization, John Wiley & Sons.
Guha, S., Moss, A., Naor, J., and Schieber, B.(1999). “Efficient Recovery from Power Outage,” Extended
Summary, Proceedings of ACM Symposium on Theory of Computing.
Haghani, A. and Oh, S.C.(1996). “Formulation and Solution of A Multi-commodity, Multi-modal Network Flow
Model for Disaster Relief Operations,” Transportation Research - A, Vol.30, No.3, pp.231-250.
Hartmann, S.(1998). “A competitive genetic algorithm for resource-constrained project scheduling,” Naval
Research Logistics, Vol.45, pp.733-750.
Hartmann, S.(2002). “A Self-Adapting Genetic Algorithm for Project Scheduling under Resource Constraints,
” Naval Research Logistics, Vol.49, pp.433-449.
Herroelen, W., De Reyck, B., and Demeulemeester, E.(1998). “Resource-constrained project scheduling: a
survey of recent developments,” Computers and Operations Research, Vol.25, pp.279-302.
Kim, Y.K., Park, K., and Ko, J.(2003). “A Symbiotic Evolutionary Algorithm for the Integration of Process
Planning and Job Shop Scheduling,” Computers and Operations Research, Vol.30, pp.1151-1171.
Kaufmann, A. and Gupta, M.(1991). Introduction to Fuzzy Arithmetic, Van Nostrand Reinhold, New York,.
Leu, Sou-Sen(2001). “A GA-based fuzzy optimal model for construction time-cost trade-off,” International
Journal of Project Management, Vol. 19, pp.47-58.
Lorterapong, P. and Moselhi, O.(1996). “Project-network analysis using fuzzy theory,” Journal of
Construction Engineering and Management, pp.308-317.
Machado, P., Tavares, J., Pereira, F.B., and Costa, E.(2002). “Vehicle Routing Problem: Doing it the
Evolutionary Way,” In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002). pp.
690, New York, USA, 9-13 July.
Matthew, B. Wall.(1996). A Genetic Algorithm for Resource-Constrained Scheduling, PhD thesis, Dept. of
Mechanical Engineering, MIT.
Muchalewicz, Z.(1996). Genetic Algorithm + Data Structure = Evolution Programs, 2nd. Ed., Springer-Verlag,
New York.
Meissner, A., Luckenbach, T., Risse, T., Kirste, T., and Kirchner, H.(2002). “Design Challenges for an
Integrated Disaster Management Communication and Information System,” The First IEEE Workshop on Disaster
Recovery Networks (DIREN2002). June 24, New York City.
Noda, S.(1993). “Optimum Post-earthquake Restoration of A Telephone System using Neural Network,” Journal
of Natural Disaster Science, Vol.15, pp.91-111.
Oh, S.C. and Haghani, A.(1997). “Testing and Evaluation of a Multi-commodity Multi-modal Network Flow
Model for Disaster Relief Management,” Journal of Advanced Transportation, Vol.31, No.3, pp.249-282.
Oğuz, C. and Cheung, B.(2002). “A Genetic Algorithm for Flow-shop Scheduling Problems with Multiprocessor
Tasks,” Working Paper No. G-2002-4, Le Cahiers du GERAD, January.
Potter, M.A. and De Jong, K.A.(2000). “Cooperative Coevolution: An Architecture for Evolving Coadapted
Subcomponents,” Evolutionary Computation, Vol.8, No.1, pp.1-29, MIT Press.
Potter, M.A.(1997). The Design and Analysis of a Computational Model of Cooperative Coevolution, PhD thesis
(Advisor: De Jong, K.A.). George Mason University, Fairfax, Virginia.
Rosin, C.D.(1997). Coevolutionary Search among Adversaries, PhD thesis (Advisor: Belew, R.K.). University
of California, San Diego.
Rosin, C.D. and Belew, R.K.(1997). “New Methods for Competitive Coevolution,” Evolutionary Computation,
Vol.5, No.1, pp.1-29, MIT Press.
Sarker, B.R. and Mahankali, S.(1996). “Power Restoration in Emergency Situations,” Computers and
Industrial Engineering, Vol.31, No.1/2, pp.367-370.
Sato, T. and Ichii, K.(1996). “Optimization of Post-earthquake Restoration of Lifeline Networks using
Genetic Algorithms,” Japan Society of Civil Engineers, No. 537/I-25, pp. 245-256.(in Japanese)
Słowiński, R. and Hapke, M.(eds)(2000). Scheduling Under Fuzziness, Physica-Verlag, New York.
Sakawa, M., Inuiquchi, M., Sunada, H. and Sawada, K.(1994). “Fuzzy Multi-objective Combinatorial
Optimization through Revised Genetic Algorithm,” Journal of Japan Society for Fuzzy Theory and Systems,
Vol. 6, No. 1, pp. 177-185.
Sakawa, M., Kubota, R.(2000). “Fuzzy programming for multi-objective job shop scheduling with fuzzy
processing time and fuzzy duedate through genetic algorithms,” European Journal of Operational Research,
No. 120, pp.292-407.
Sato, T., and Ichii, K.(1996). “Optimization of post-earthquake restoration of lifeline networks using
genetic algorithms,” Japan Society of Civil Engineers, No. 537/I-25, pp. 245-256.
Shiromaru, I., Inuiguchi, M., and Sakawa, M.(2000). “A fuzzy satisficing method for electric power plant
coal purchase using genetic algorithms,” European Journal of Operational Research, Vol. 126, pp. 218-230.
Tamura, T., Sugimoto, H. and Kamimae, T.(1994). “Application of Genetic Algorithms to Determining Priority
of Urban Road Improvement,” Japan Society of Civil Engineers, No. 482/IV-22, pp. 37-46. (in Japanese)
Therrien, M. -Ch.,(1995). “Interoganizational networks and decision making in technological disasters,”
Safety Science, No.20, pp.103-113.
Tzeng, G.H. and Chen, Y.W.(1998). “Implementing an Effective Schedule for Reconstructing Post-earthquake
Road-network Based on Asymmetric Traffic Assignment — An Application of Genetic Algorithm,” International
Journal of Operations and Quantitative Management (IJOQM). pp. 229-246.
Weglarz, J.(ed.)(1999). Project Scheduling: Recent Models, Algorithms and Application, Kluwer Academic
Publisher, Boston.
Wiegand, R.P., Liles, W.C., and De Jong, K.A.(2001). “An Empirical Analysis of Collaboration Methods in
Cooperative Coevolutionary Algorithms,” Proceeding of the Genetic and Evolutionary Computation Conference
(GECCO-2001). pp.1235-1245, Morgan Kaufmann Publisher.
Wiegand, R.P., Liles, W.C., and De Jong, K.A.(2002). “The Effects of Representational Bias on
Collaboration Methods in Cooperative Coevolution,” Parallel Problem Solving from Nature VII (PPSN-2002),
Lecture notes in Computer Science, Vol. 2439, pp.257-268, Springer-Verlag.