道路緊急搶修車輛途程問題之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：25

、訪客IP：3.145.86.42

姓名

何秉珊(Ping-shan Ho) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

道路緊急搶修車輛途程問題之研究
(Network Repairing Construction Routing for Repair Time after Natural Disasters)

相關論文

★ 圖書館系統通閱移送書籍之車輛途程問題	★ 起迄對旅行時間目標下高速公路匝道儀控之研究
★ 結合限制規劃法與螞蟻演算法求解運動排程問題	★ 共同邊界資料包絡分析法在運輸業之應用-以國內航線之經營效率為例
★ 雙北市公車乘客知覺服務品質、知覺價值、滿意度、行為意向路線與乘客之跨層次中介效果與調節式中介效果	★ Investigating the influential factors of public bicycle system and cyclist heterogeneity
★ A Mixed Integer Programming Formulation for the Three-Dimensional Unit Load Device Packing Problem	★ 高速公路旅行時間預測之研究--函數資料分析之應用
★ Behavior Intention and its Influential Factors for Motorcycle Express Service	★ Inferring transportation modes (bus or vehicle) from mobile phone data using support vector machine and deep neural network.
★ 混合羅吉特模型於運具選擇之應用-以中央大學到桃園高鐵站為例	★ Preprocessing of mobile phone signal data for vehicle mode identification using map-matching technique
★ 含額外限制式動態用路人均衡模型之研究	★ 動態起迄旅次矩陣推估模型之研究
★ 動態號誌時制控制模型求解演算法之研究	★ 不同決策變數下動態用路人均衡路徑選擇模型之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

強震發生後，往往對災區造成相當大的破壞，災區居民常陷入孤立無援的困境，亟需外界給予支援與救助，因此在地震發生後，道路「緊急搶修」為搶修單位第一考量的事項。此外，若交通系統受損，導致救援以及緊急物資車隊無法於第一時間順利進入災區，搶救速度受到牽累，救援工作無法順利進行，民眾之生命與財產可能造成難以估計的損失。
緣此，本研究將針對災後道路緊急搶修問題進行研究與探討，根據其問題特性建構數學模型，並發展出一套建構初始途程與途程改善之兩階段啟發式演算法其中，途程改善以螞蟻族群演算法為主軸，並結合路線間1-1節點交換法，以建構出災區內各災點之最佳搶修順序及各工程隊之搶救排程作業。最後，本研究產生12組測試例題，進行例題測試分析，進而提出結論與建議。

摘要(英)

Earthquakes often cause great damage to the transportation infrastructure of the disaster area that isolated the residents of the disaster area. The first priority should be planning emergency repair schedule to repair the damaged transportation infrastructure otherwise food, water, rescue equipment and repair team can not enter the disaster area. Rescuing effort will also be delayed causing immeasurable loss of life and properties.
This research studies the repair schedule with minimized total repair time of damaged transportation system after natural disasters. This problem is a variance of standard vehicle routing problem with time windows. A mixed integer optimization model is also built and a meta-heuristics which consists of tour construction and tour improvement procedure is developed. Tour improvement is based on ant colony system combined with 1-1 exchange method to construct the best repair sequence of each disaster node. Finally, twelve test problems are examined for the purpose of this study, and then recommendations are made from the analysis of those test problems.

關鍵字(中)

★ 車輛途程問題
★ 螞蟻族群演算法
★ 緊急搶修時間

關鍵字(英)

★ Vehicle routing problem
★ Emergency repair time
★ Ant colony system

論文目次

目錄
摘要 I
Abstract II
誌謝 III
目錄 IV
圖目錄 VI
表目錄 VII
第一章緒論 1
1.1研究背景與動機 1
1.2研究目的 1
1.3研究方法與流程 2
第二章國內公路搶修工程單位概況 5
2.1國內公路搶修工程單位概況 5
2.2緊急搶修定義、期程及特性之說明 8
2.2.1緊急搶修定義 8
2.2.2緊急搶修期程 9
2.2.3緊急搶修特性 10
第三章文獻回顧 12
3.1車輛途程問題之相關文獻 12
3.1.1車輛途程問題 12
3.1.2車輛途程問題之分類 13
3.1.3時窗限制車輛途程問題 15
3.1.4 VRP求解方法 16
3.2災後路網緊急搶修相關文獻 32
3.3小結 34
第四章模型建構 37
4.1緊急搶修問題描述 37
4.2緊急搶修問題模型建構 37
4.3時間滾動平面觀念 39
4.4研究假設 41
4.5符號說明 42
4.6數學模型 43
4.6案例圖解說明 45
第五章求解演算法 47
5.1演算法架構 47
5.2緊急搶修問題求解方法 48
5.2.1搶修的時窗限制 48
5.2.2即時性需求與臨界點 48
5.3綜合求解流程 49
5.4路線建構 50
5.5路線改善 53
5.5.1螞蟻族群演算法 53
5.5.2傳統區域搜尋法 58
第六章範例測試與分析 62
6.1測試例題之建立 62
6.2範例測試結果 62
6.2.1初始解之產生 63
6.2.2初始解之改善 63
第七章結論與建議 72
7.1結論 72
7.2建議 73
參考文獻 74
附錄ㄧ 80

參考文獻

1. 王元鵬(2006)，仿水流離散優化演算法，國立台灣大學工業工程研究所碩士論文，台北。
2. 王在莒(2003)，非都會區公路之震災緊急搶修排程，國立交通大學交通運輸研究所博士論文，台北。
3. 王福聖(2008)，不精確資訊下震災路網搶修排程與民眾對搶修時間可忍受度之研究，國立中央大學土木工程系碩士論文，中壢。
4. 台灣省政府(1993)，防救天然災害及善後處理辦法。
5. 交通部中央氣象局(2000)，地震震度分級表，http://www.cwb.gov.tw/。
6. 交通部公路總局(2000)，災害緊急處理與應變計畫。
7. 交通部公路總局(2002)，公路災害緊急處理與應變計畫。
8. 交通部公路總局(2002)，災害防救標準作業手冊。
9. 交通部公路總局(2007)，各區工程處地理轄區，http://www.thb.gov.tw/index.htm。
10. 朱文正(2003)，考量旅行時間可靠度之車輛途程問題-螞蟻族群演算法之應用，國立交通大學交通運輸研究所碩士論文，台北。
11. 行政院主計處(1999)，www.dgbas.gov.tw。
12. 吳心琪(1996)，震災後公路網搶修工程排程之研究，國立交通大學交通運輸研究所碩士論文，台北。
13. 李志華(2003)，基因演算法於震災路網搶修排程問題之研究，國立成功大學交通管理科學系碩士論文，台南。
14. 李佳蓮(2006)，車輛排程問題的廣域搜尋解法，國立成功大學土木工程研究所碩士論文，台南。
15. 林依潔(2003)，整合模糊理論與螞蟻演算法於含時間窗限制之車輛途程問題，國立台北科技大學生產系統工程與管理研究所碩士論文，台北。
16. 林宗漢(2007)，應用螞蟻演算法探討卡車與拖車途程問題，國立高雄第一科技大學運籌管理所碩士論文，高雄。
17. 施佑林(2003)，災後工程搶修作業暨賑災物流排程之研究，國立中央大學土木工程研究所碩士論文，中壢。
18. 張立偉(2001)，災後工程緊急搶修作業排程之研究，淡江大學運輸管理學系運輸科學碩士班碩士論文，台北。
19. 許家筠(2008)，時窗限制虛擬場站接駁補貨車輛途程問題之研究，國立中央大學土木工程系碩士論文，中壢。
20. 陳信宇(2000)，震災物流系統之決策模式，國立交通大學交通運輸研究所碩士論文，台北。
21. 陳家和(2005)，應用螞蟻演算法於時窗限制車輛途程問題之研究，運輸學刊，第三期，第十七卷，頁261-280。
22. 陳國清(1996)，成本擾動法與兩極跳躍法於TSP問題應用之研究，交通大學交通運輸研究所畢業專題研究報告，台北。
23. 黃亦琇(2000)，震災道路系統評估指標之建立，國立交通大學交通運輸研究所碩士論文，台北。
24. 楊宗岳(2000)，參與行政院921災後重建推動委員會交通組之後感，臺灣公路工程，第二十六卷，第十二期，頁26-40。
25. 詹達穎、林佑昇(2006)，車輛途程問題之研究-結合基因演算法與螞蟻演算法求解，第十三屆三軍官校基礎學術研討會，頁9-18。
26. 韓復華、卓裕仁(1996)，門檻接受法、成本擾動法與搜尋空間平滑法在車輛路線問題之應用研究與比較分析，運輸學刊，第九卷，第三期，頁103-129。
27. 藍武王(2000)，大地震的防災應變：道路系統管理相關課題，臺灣公路工程，第二十六卷，第九期，頁2-8。
28. 羅敏華(2003)，蟻群最佳化演算法於載重限制之車輛途程問題的研究，私立元智大學工業工程與管理研究所碩士論文，中壢。
29. Bella, J., and McMullen, P. (2004), “Ant Colony Optimization Techniques for the Vehicle Routing Problem,” Advanced Engineering Informatics 18, pp. 41–48.
30. Bielli, M., Caramia, M., and Carotenuto, P. (2002), “Genetic Algorithms in Bus Network Optimization,” Transportation Research, Part C. Vol. 10, pp. 19-34.
31. Birbil, S.I., and Fang, S.C. (2003), “Electromagnetism-like Mechanism for Global Optimization,” Journal of Global Optimization, Vol. 25, pp. 263-282.
32. Bodin, L., Golden, B., Assad, A., and Ball, M. (1983), “Routing and Scheduling of Vehicles and Crews,” Computers and Operations Research, Vol. 10, No. 2, pp. 63-211.
33. Bräysy, O., and Gendreau, M. (2005a), “Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms,” Transportation Science, Vol. 39, No. 1, pp. 104-118.
34. Bräysy, O., and Gendreau, M. (2005b), “Vehicle Routing Problem with Time Windows, Part II: Metaheuristics,” Transportation Science, Vol. 39, No. 1, pp. 119-139.
35. Bullnheimer, B., Hart1, R.F., and Strauss, C. (1999), “An Improved Ant System for the Vehicle Routing Problem”, Annals of Operations Research, Vol. 89, pp. 319-328.
36. Bullnheimer, B., Hartl, R.F., and Strauss, C. (1997), “ A New Rank-Based Version of the Ant System：A Computational Study,” Technical Report POM 3, Institute of Management Science,University of Vienna. Accepted for publication in the central European journal for Operations Research and Economics.
37. Charon, I., and Hurdy, O. (1993), “The Noising Method: A New Method for Combinatorial Optimization,” Operations Research Letters, Vol. 14, pp. 133-137.
38. Che-Fu Hsueh, Huey-Kuo Chen and Huey-Wen Chou, 2008, “Vehicle Routing for Rescue Operation in Natural Disasters,” In Tonci Caric and Hrvoje Gold (Ed), Vehicle Routing Problem, ISBN 978-3-902613-30-1, I-Tech Education and Publishing KG, Vienna, Austria, pp.71-84.
39. Clarke, G., and Wright, J.W. (1964), “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, No. 4, pp. 568-581.
40. Dantzig, G., and Ramser, J. (1959), “The Truck Dispatching Problem,” Management Science 6, pp. 80-91.
41. Dorigo, M., and Gambardella, L.M. (1997), “Ant Colonies for the Traveling Salesman Problem,” BioSystems, Vol. 43, pp. 73-81.
42. Dorigo, M., and Gambardella, L.M. (1997), “Ant Colony System: A Cooperative Learning Approach to The Traveling Saleman Problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53-66.
43. Dorigo, M., Caro, G.D and Gambardella, L.M. (1999), “Ant Algorithms for Discrete Optimization,” Artificial Life, Vol. 5, No. 2, pp. 137–172.
44. Dorigo, M., Maniezzo, V. and Colorni, A. (1991), The Ant System: An Autocatalytic Optimizing Process, Technical Report, pp. 91-016 Revised, Politecnico di Milano, Italy.
45. 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, Vol. 26, No. 1, pp. 29-42.
46. Dueck, G. (1993), “New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel,” Journal of Computational Physics, Vol. 104, pp. 86-92.
47. Dueck, G., and Scheuer, T. (1990), “Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing,” Journal of Computational Physics, Vol. 90, pp.161-175.
48. Eberhart, R.C., and Kennedy, J. (1995), “Particle Swarm Optimization,” In proceedings of IEEE International Conference on Neural Networks, Vol. 4, pp. 1942-1948.
49. FEMA (1996), Guide for All-Hazard Emergency Operation Planning-State and Local Guide (SlG-101), pp. 444-446.
50. Fiedrich, F., Gehbauer, F., and Rickers, U. (2000), “Optimized Resource Allocation for Emergency Response after Earthquake Disasters,” Safety Science, Vol. 35, pp. 41-57.
51. Gambardella, L.M., Taillard, È.D., and Dorigo, M. (1998), Ant Colonies for The QAP, Technical Report IDSIA No. 4-97 Revised, IDSIA, Lugano, Switzerland.
52. Garey, M.R., and Johnson, D.S. (1979), Computers and Intractability-A Guide to the Theory of NP-Completeness, Series of Books in the Mathematical Sciences. W. H. Freeman and Co. New York, NY , USA.
53. Geem, Z.W., and Kim, J.H. (2001), “A New Heuristic Optimization Algorithm: Harmony Search,” Simulation, pp. 60-68.
54. Gillett, B., and Miller, L. (1974), “A Heuristic Algorithm for the Vehicle Dispatch Problem,” Operations Research, Vol. 22, pp. 340-349.
55. Glover, F. (1989), “Tabu Search, Part I,” ORSA Journal on Computing, Vol. 1, No. 3, pp. 190-206.
56. Gu, J., and Huang, X. (1994), “Efficient Local Search with Search Space Smoothing: A Case Study of the Traveling Salesman Problem (TSP),” IEEE Transaction on Systems, Man and Cybernetics, Vol. 24, pp. 728-739.
57. Holland, J.H. (1975), Adaptation in Natural and Artificial System, University of Michigan Press.
58. Hsueh, C.F., Chen H.K., and Chou, H.W. (2007), Vehicle Routing for Relief Logistics in Natural Disasters, Working Paper at National Central University, Jungli, Taiwan.
59. Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P. (1983), “Optimization by Simulated Annealing,” Science, Vol. 220, pp. 671-680.
60. Knox, J., and Glover, F. (1989), Comparative Testing of Traveling Salesman Heuristics Derived from Tabu Search, Genetic Algorithms and Simulated Annealing, Technical report, Center for Applied Artificial Intelligence, University of Colorado, Boulder, CO.
61. Liao, H.K. (2005), A Study on Network Reconstruction and Relief Logistics, Master Thesis at National Central University, Jungli, Taiwan.
62. Lin, S. (1965), “Computer Solutions of the Traveling Salesman Problem,” Bell Syst. Tech. J., Vol. 44, pp. 2245-2269.
63. Lin, S., and Kernighan, B. (1973), “An Effective Heuristic Algorithm for the Traveling Salesman Problem,” Operations Research, Vol. 21, pp. 498-516.
64. Maniezzo,V. (1998), Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem, Technical Report CSR 1, C.L. in Scienze dell Informazione,Universita di Bologna, Sede di Cesena, Ttaly.
65. Mazzeo, S., and Loiseau, I. (2004), “An Ant Colony Algorithm for the Capacitated Vehicle Routing,” Electronic Notes in Discrete Mathematics 18, pp 181-186.
66. McMullen, P.R.(2001), “An Ant Colony Optimization Approach to Addressing a JIT Sequencing Problem with Multiple Objectives,” Artificial Intelligence in Engineering 15, pp. 309-317.
67. Mladenović, N., and Hansen, P. (1997), “Variable Neighborhood Search for the p-median,” Location Science, Vol. 5, No. 4, pp. 207-226.
68. Mole, R.H., and Jameson, S.R. (1976), “A Sequential Route-Building Algorithm Employing a Generalised Savings Critenon,” Operational Research., Quarterly, 27, pp. 503-511.
69. Or, I. (1976), Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Blood Banking, Ph.D. Thesis, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, USA.
70. Osman, I.H, and Kelly, J.P. (1996), “Meta-Heuristics: An Overview,” In OSman I.H. and Kelly J.P. (Eds), Meta-Heuristics: Theory and Applications, Kluwer Academic Publishers, Boston, London, Dordrecht, pp. 1-21.
71. Potvin, J.Y., and Bengio, S. (1996), “The Vehicle Routing Problem with Time Windows Part :Genetic Search,” Informs Journal on Computing, Vol. 8, No. 2, pp. 165-172.
72. Potvin, J.Y., and Rousseau, J.M. (1995), “An Exchange Heuristic for Routing Problems with Time Windows,” Journal of the Operational Research Society 46, pp. 1433-1446.
73. Psaraftis, H.N. (1995), “Dynamic Vehicle Routing: Status and Prospect,” Annals of Operations Research, Vol. 61, pp. 143-164.
74. Reeves, C.R. (1993), “Improving the Efficiency of Tabu Search for Machine Sequencing Problems,” Journal of the Operation Research Society, Vol. 44, No. 4, pp. 375-382.
75. Reimann, M., Stummer, M., and Doerner, K. (2002), “A Savings Based Ant System For The Vehicle Routing Problem,” In: Langdon WB et al., editors. Proceedings of the Genetic and Evolutionary Computation Conference (GECOO). San Francisco: Morgan Kaufmaan.
76. Solomon, M.M. (1983), Vehicle Routing and Scheduling with Time Windows Constraints: Models and Algorithms, Ph.D. Dissertation, Dept. of Decision Sciences, University of Pennsylvania, Pennsylvania, USA.
77. Solomon, M.M. (1986), “On the Worst-case Performance of Some Heuristics for the Vehicle Routing and Scheduling Problem with Time Windows Constraints,” Networks, Vol. 16, pp. 161-174.
78. Solomon, M.M., and Desrosiers, J. (1988), “Time windows constrained routing and scheduling problems,” Transportation Science, Vol. 22, pp. 1-13.
79. Stützle,T. (1997), MAX-MIN Ant System for Quadratic Assignment Problems, Technical Report AIDA 4, Intellectics Group, Department of Computer Science, Darmstadt University of Technology, Germany, July.
80. Taillard, E.D., and Gambardella, L.M. (1997), Adaptive Memories for the Quadratic Assignment Problem, Technical Report IDSIA, pp. 87-97.

指導教授

陳惠國(Huey-kuo Chen)

審核日期

2009-1-12

推文