跳到主要內容

臺灣博碩士論文加值系統

(100.28.2.72) 您好!臺灣時間:2024/06/16 06:29
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:黃珊珊
研究生(外文):Shan-Shan Huang
論文名稱:橋樑檢測路程規劃
論文名稱(外文):Solving the Bridge Inspection Routing Problem by Ant Colony Optimization
指導教授:黃山琿黃山琿引用關係
指導教授(外文):Shan﹣Huen Huang
學位類別:碩士
校院名稱:國立高雄第一科技大學
系所名稱:運籌管理研究所
學門:商業及管理學門
學類:行銷與流通學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:中文
論文頁數:47
中文關鍵詞:路徑規劃蟻群演算法橋樑檢測
外文關鍵詞:Bridge inspectionAnt Colony OptimizationRouting problem
相關次數:
  • 被引用被引用:0
  • 點閱點閱:160
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
摘要
本研究主要探討橋樑檢測的路徑問題。檢測團隊必須皆由同一個場站 (Depot)出發,檢測結束後再返回到該場站 (Depot)。由於檢測作業需耗費幾個工作日來完成,因此檢測團隊需在外地住宿。這種多個可住宿地點成為特殊類型的路徑規劃。本研究提出兩種不同的方案進行闡述與探討:在方案一是由一組檢測團隊進行全部橋樑檢測作業;在方案二則為在給定的天數內完成所有的橋樑須檢測,其兩種方案主要目的皆在找出最佳路徑使其總成本花費最小化,其中包括移動成本和住宿成本。本研究採用蟻群演算法求其解。並加入局部搜尋的方式來改善解的品質,並以三組範例進行測試來驗證本研究演算法的求解能力,最後,透過測試例題找出蟻群演算法的最佳變數組合。
Abstract
This thesis presents a research regarding the routing problem of bridge inspection. A bridge inspection team has to depart from the depot then visits bridges and eventually back to the depot. This may take several days for one inspection team. They have to find accommodations during the inspection period. This working style makes this problem a special type of vehicle routing problem. Two kinds of scenarios are made for the bridge inspection problem. One is containing only one inspection team and the other has a specific length of inspection period. The goal of this problem is to figure out the best route that minimizes the total cost including travel cost and accommodation cost. This research employs Ant Colony Optimization algorithm for solving the problem. In addition, a local search method is proposed to help in improving the solutions. Three datasets of benchmarks are generated to estimate the performance of the proposed solving process. The best combination of the variables for ACO is found first then the solving process is applied onto the benchmarks. The output results show that the solving process can yield promising solutions within reasonable time.
目錄
摘要.............i
Abstract........ii
致謝............iii
目錄............iv
圖目錄..........vi
表目錄..........vi
第一章 緒論......1
第一節 研究背景...1
第二節 研究目的...2
第三節 研究架構...3
第二章 文獻回顧...4
第一節 橋樑檢測種類與項目...4
第二節 路徑規劃...7
第三節 最佳化演算法...10
第三章 問題描述和模型建構...14
第一節 問題描述...14
第二節 模型建構...17
第四章 研究方法...21
第五章 研究結果...24
第一節 蟻群演算法在BIRP上的應用...24
第二節 局部搜尋...28
第三節 例題測試與探討...30
第四節 敏感度分析 ...38
第六章 結論...40
第一節 結論...40
第二節 貢獻...41
第三節 建議...41
參考文獻...42
中文文獻
[1]交通部,2013,交通部公路總局公路養護手冊
[2]柴志傑,2009,臺灣地區橋梁目視檢測行程最佳化之研究,國立中央大學營建管理研究所碩士論文
[3]蔡志強,2004,「以蟻群系統建立物流宅配最佳化配送路徑規劃」,國立屏東科技大學工業管理所碩士論文
外文文獻
[1]Attiratanasunthron, N., and Fakcharoenphol, J. (2008). A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs. Information Processing Letters, 105(3), 88-92.
[2]Azadeh, A., Farahani, M. H., Eivazy, H., Nazari-Shirkouhi, S.,and Asadipour, G. (2013). A hybrid meta-heuristic algorithm for optimization of crew scheduling. Applied Soft Computing, 13(1), 158-164.
[3]Bautista, J., Fernández, E.,and Pereira, J. (2008). Solving an urban waste collection problem using ants heuristics. Computers & Operations Research, 35(9), 3020-3033.
[4]Bernd, B., Richard , F. H.,and Christine, S. (1999). An Improved Ant System Algorithm for the Vehicle Routing Problem. Annals of Operations Research 89:319-328.
[5]Camelia, M., Pintea, P.C. , and Camelia, C. ( 2013). The Generalized Traveling Salesman Problem solved with Ant Algorithms. J Univers Comput Sci 2013; 13(7)rem.
[6]Ding, Q.,Hu, X.,Sun, L.,and Wang, Y.(2012). An improved ant colony optimization and its application to vehicle routing problem with time windows. Neurocomputing, 98, 101-107.
[7]Donati, A. V., Montemanni, R., Casagrande, N., Rizzoli, A. E.,and Gambardella, L. M. (2008). Time dependent vehicle routing problem with a multi ant colony system. European journal of operational research, 185(3), 1174-1191.
[8]Dorigo, M. (1992). Optimization, learning and natural algorithms. Ph. D. Thesis, Politecnico di Milano, Italy.
[9]Dorigo, M.,and Gambardella, L.M.(1997). “Ant Colony System: a Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary.
[10]Dorigo, M.,and Blum, C.(2005). Ant colony optimization theory: A survey. Theoretical computer science, 344(2), 243-278.
[11]Dorigo, M., Bonabeau, E.,and Theraulaz, G.(2000). Ant algorithms and stigmergy. Future Generation Computer System; 16 (8): 851–871.
[12]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(2), pp. 29-41.
[13]Frangopol, D. M.(1999). Life-cycle cost analysis for bridges. In Bridge safety and reliability. ASCE (pp. 210-236).
[14]Fuellerer, G., Doerner, K. F., Hartl, R. F., and Iori, M. (2010). Metaheuristics for vehicle routing problems with three-dimensional loading constraints. European Journal of Operational Research, 201(3), 751-759.
[15]Francis, P., and Smilowitz, K. (2006). Modeling techniques for periodic vehicle routing problems, Transport. Res. B 40(10) 872884
[16]Gambardella, L. M.,Taillard, T.,and Agazzi, G.(1999). MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows. Mcgraw-Hill''S Advanced Topics In Computer Science Series: New ideas in optimization. 63-76.
[17]García-Martínez, C., Cordón, O.,and Herrera, F.(2007). A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP. European Journal of Operational Research, 180(1), 116-148.
[18]Ghoseiri, K.,and Nadjari, B.(2010). An ant colony optimization algorithm for the bi-objective shortest path problem. Applied Soft Computing; 10:1237-1246.
[19]Giosa, I.D., Tansini, I.L., and Viera I.O. (2002). New assignment algorithms for the multi-depot vehicle routing problem, J. Oper. Res. Soc. 53 977-984.
[20]Hoff, A., Gribkovskaia, I., Laporte, G.,and Lokketangen, A. (2007). Lasso solution strategies for the vehicle routing problem with pickups and deliveries, Eur. J. Oper. Res. 192 (3) 755-766.
[21]Hlaing, Z. C. S. S., and Khine, M. A. (2011). Solving traveling salesman problem by using improved ant colony optimization algorithm. International Journal of Information and Education Technology, 1(5), 404-409.
[22]Huang, S. H.,and Lin, P. C. (2010). A modified ant colony optimization algorithm for multi-item inventory routing problems with demand uncertainty. Transportation Research Part E: Logistics and Transportation Review, 46(5), 598-611.
[23]Huang, S. H., and Lin, P. C.(2012). Multi-treatment capacitated arc routing of construction machinery in Taiwan''s smooth road project. Automation in Construction, 21, 210-218.
[24]Huang, S.H., Yang, T.H.,and Wang, R.T.(2011). Ant colony optimization for railway driver crew scheduling: from modeling to implementation. Journal of the Chinese Institute of Industrial Engineers; 28(6):437-449.
[25]John, E. B., and Patrick, R. M. (2009). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics;18:41-48
[26]Jose, B. E., Juan F. J., and Jose M. G.( 2015). Ant Colony Extended: Experiments on the Travelling Salesman Problem. Expert Systems with Applications 2015;42:390-410.
[27]Jun-man, K.,and Yi, Z. (2012). Application of an improved ant colony optimization on generalized traveling salesman problem. Energy Procedia, 17, 319-325.
[28]Laporte, G.,Nobert, Y.,and Desrochers, M.(1985). Optimal routing under capacity and distance restrictions, Oper. Res. 33 1050-1073.
[29]Li, X.,Baki, M.F.,and Aneja, YP. (2011).Flow shop scheduling to minimize the total completion time with a permanently present operator: models and ant colony optimization metaheuristic. Computers & Operations Research; 38:152-164.
[30]Marco, D., and Gambardella, L.M.(1997).“Ant Colonies for The Travelling Salesman Problem, “ BioSystems 43, pp. 73-81,.
[31]Michalis, M.,and Yang, S.G.(2013).Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors. Applied Soft Computing ;13:4023-4037
[32]Mostafa, M., Ömer, K. B.,and Halife, K.(2015).A new hybrid method based on Particle Swarm Optimization, Ant Colony Optimization and 3-Opt algorithms for Traveling Salesman Problem. Applied Soft Computing;30:484-490.
[33]Pradhananga, R., Taniguchi, E., and Yamada, T. (2010). Ant colony system based routing and scheduling for hazardous material transportation. Procedia Social and Behavioral Sciences; 2:6097-6108.
[34]Reihaneh, M., and Karapetyan, D. (2012). An efficient hybrid ant colony system for the generalized traveling salesman problem. arXiv preprint arXiv:1206.1579.
[35]Reimann, M., Doerner, K., and Hartl, R. F. (2004). D-ants: Savings based ants divide and conquer the vehicle routing problem. Computers & Operations Research, 31(4), 563-591.
[36]Santos, L., Coutinho-Rodrigues, J.,and Current, J.R.(2010).An improved ant colony optimization based algorithm for the capacitated arc routing problem. Transportation Research Part B; 44:246-266.
[37]Sudholt, D.,and Thyssen, C.(2012).Running time analysis of ant colony optimization for shortest path problems. Journal of Discrete Algorithms; 10:165-180.
[38]Toth, P., and Vigo, D.(1999). A heuristic algorithm for the symmetric and asymmetric vehicle routingproblems with backhauls, Eur. J. Oper. Res. 113528-543.
[39]Wang, H.,and Shen, J. (2007).Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints. Applied Mathematics and Computation; 190:1237-1249.
[40]Xiaoxia, Z.,and Lixin, T. (2009). A new hybrid ant colony optimization algorithm for the vehicle routing problem. Pattern Recognition Letters;30:848-855
[41]Yagmahan, B.,and Yenisey, M.M.(2008). Ant colony optimization for multi-objective flow shop scheduling problem. Computers & Industrial Engineering; 54:411-420.
[42]Yu, F., Li,Y.,and Wu,T. J. (2010). A temporal ant colony optimization approach to the shortest path problem in dynamic scale-free networks. Physica A; 389:629-636
[43]Yu, B., Yang, Z. Z., and Yao, B. (2009). An improved ant colony optimization for vehicle routing problem. European journal of operational research, 1961, 171-176.
[44]Yang, J., Shi, X.H., Marchese, M., and Liang, Y.C. (2008). An ant colony optimization method for generalized TSP problem. Progress in Natural Science;18:1417-1422
[45]Zhang, X.,and Wang, J.Q. (2012). Hybrid Ant Algorithm and Applications for Vehicle Routing Problem. Physics Procedia;25:1892-1899
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊