跳到主要內容

臺灣博碩士論文加值系統

(3.236.110.106) 您好!臺灣時間:2021/07/26 00:34
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:梁文榮
研究生(外文):Wen-Jung Lien
論文名稱:基於ACO和PSO的混合算法求解VRPTW問題
論文名稱(外文):A Hybrid Algorithm Based on ACO and PSO for Vehicle Routing Problem with Time Windows
指導教授:陳明賢陳明賢引用關係高有成高有成引用關係
指導教授(外文):Ming-Hsien ChenYucheng Kao
口試委員:陳明賢高有成
口試委員(外文):Ming-Hsien ChenYucheng Kao
口試日期:2015-07-07
學位類別:碩士
校院名稱:大同大學
系所名稱:資訊經營學系(所)
學門:商業及管理學門
學類:一般商業學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:中文
論文頁數:63
中文關鍵詞:巨集啟發式演算法粒子演算法螞蟻最佳化演算法有時窗限制的車輛途程問題
外文關鍵詞:Meta-heuristicParticle Swarm OptimizationAnt Colony OptimizationVehicl Routing Problem with Time Windows
相關次數:
  • 被引用被引用:0
  • 點閱點閱:90
  • 評分評分:
  • 下載下載:9
  • 收藏至我的研究室書目清單書目收藏:0
有時窗限制的車輛途程問題(VRPTW)是一種組合優化的問題。過去已有許多學者對此進行研究,並且嘗試使用巨集啟發式演算法來解決VRPTW問題。本研究利用螞蟻最佳化演算法(ACO)為主架構,並且應用區域搜尋及費洛蒙擾動來解決最低總成本的VRPTW問題。同時針對ACO在寬時窗上表現較差的問題,提出使用每回合螞蟻解為粒子位置,依據粒子演算法(PSO)的速度向量公式的概念,運用全域最佳解(GBest)及區域最佳解(PBest),並保留每隻螞蟻的探索解,來導引出新費落蒙值的方法,並增加探索解空間的變化機率。使用所羅門的56測試題型來進行VRPTW實驗,實驗結果證明,新的算法在求解寬時窗VRPTW時解品質比ACO更好,有12個測試題型的解比所羅門網站上的最佳解更好,並且新的算法在求解窄時窗VRPTW時解品質也不差於ACO,有5個測試題型的解較所羅門網站上所收集的最佳解更好。
The Vehicle Routing Problem with Time Windows(VRPTW) is one of NP-Hard problem. Many researchers have discussed, and tried to solve the VRPTW with meta-heuristic approaches in many years. This study use the Ant Colony Optimization(ACO) as the main structure, and apply the Local Search and Pheromones Disturbance to resolve VRPTW Problem of the minimum of total cost. The Global Best Solution(GBest) and the Particle Best Solution(PBest) will be introduced to tackle with the problem of poor performance on wide time window on ACO by using particle algorithm (PSO) concept of the velocity vector equation. In the mean time, the exploratory solution for conducting new pheromones value will be kept in every single ant. Use "Solomon's fifty-six test case" to carry out VRPTW's experiment. Experimental results show that the new algorithm for solving VRPTW of wide time window solution quality is better than the ACO. There are twelve test solutions better than optimal solution of Solomon website. And the new algorithm for solving VRPTW of narrow time window solution quality is no worse than ACO. There are five test solutions better than optimal solution of Solomon website.
摘要 i
ABSTRACT ii
第一章 簡介 5
1.1 研究背景與動機 5
1.2 研究方法與流程 7
1.3 論文架構 8
第二章 文獻探討 9
2.1 時窗限制車輛途程問題 9
2.2 巨集啟發式演算法 13
2.3 蟻群系統演算法 14
2.4 粒子群演算法 17
2.5 螞蟻最佳化演算法及其改良 18
2.6 ACO及PSO混合演算法 20
第三章 方法論 22
3.1 解決方法的框架 22
3.2 PSACO方法論概念 23
3.3 數學模型 27
3.4 PSACO的演算流程 29
3.5 螞蟻建構途程解 32
3.6 優化最佳途程解 33
3.7 更新GBest及?PBest?^a 35
3.8 費洛蒙更新法則 36
3.9 費洛蒙擾動機制 37
第四章 實驗及比較 38
4.1 SOLOMON VRPTW測試例題 38
4.2 參數設定 39
4.3 ACO、PACO、PSACO的比較 40
4.4 實驗結果及分析 41
4.5 分析 44
第五章 結論 49
5.1 研究貢獻 49
5.2 未來研究方向 51
參考文獻 53
附、PSACO針對Solomon 56題最佳解路線及數據 56
[1]Y. Kao, M.-H. Chen, and Y.-T. Huang, "A Hybrid Algorithm Based on ACO and PSO for Capacitated Vehicle Routing Problems," Mathematical Problems in Engineering, vol. 2012, pp. 1-17, 2012.
[2]G. B. Dantzig and J. H. Ramser, "The truck dispatching problem," Management science, vol. 6, pp. 80-91, 1959.
[3]易德華, "軟時窗車輛巡迴問題之研究, 國立中央大學土木工程研究所碩士論文, 中壢," 1998.
[4]P. Toth and D.Vigo, "The Vehicle Routing Problem: Discrete Mathematics and Applications," presented at the Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2002.
[5]L. Bodin, B. Golden, A. Assad, and M. Ball, "Routing and scheduling of vehicles and crews: The state of the art.," Computers & Operations Research, vol. 10, pp. 63-211, 1983.
[6]S. R. Thangiah, I. H. Osman, and T. Sun, "Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows," Computer Science Department, Slippery Rock University, Technical Report SRU CpSc-TR-94-27, vol. 69, 1994.
[7]R. Baños, J. Ortega, C. Gil, A. Fernández, and F. de Toro, "A Simulated Annealing-based parallel multi-objective approach to vehicle routing problems with time windows," Expert Systems with Applications, vol. 40, pp. 1696-1707, 2013.
[8]S. C. Ho and D. Haugland, "A tabu search heuristic for the vehicle routing problem with time windows and split deliveries," Computers & Operations Research, vol. 31, pp. 1947-1964, 2004.
[9]M. Dorigo, M. Birattari, and T. Stutzle, "Ant colony optimization," IEEE Computational Intelligence Magazine, vol. 1, pp. 28-39, 2006.
[10]J. Kennedy and R. Eberhart, "Particle swarm optimization," in Neural Networks, 1995. Proceedings., IEEE International Conference on., vol. 4, pp. 1942-1948, 1995.
[11]B. Niu, H. Wang, L.-J. Tan, L. Li, and J.-W. Wang, "Vehicle routing problem with time windows based on adaptive bacterial foraging optimization," in Intelligent Computing Theories and Applications, ed: Springer, 2012, pp. 672-679.
[12]Y.-J. Shi, F.-W. Meng, and G.-I. Shen, "A Modified Artificial Bee Colony Algorithm for Vehicle Routing Problems with Time Windows," 2012.
[13]M. Dorigo, V. Maniezzo, A. Colorni, and V. Maniezzo, "Positive feedback as a search strategy," 1991.
[14]M. Dorigo and L. M. Gambardella, "Ant colony system A cooperative learning approach to the traveling salesman problem," Evolutionary Computation, vol. 1, pp. 53-66, 1997.
[15]J. Z. Y.-J. Gong, O. Liu, R.-Z. Huang, and Y.-H. Shi, "Optimizing the Vehicle Routing Problem With Time Windows A Discrete Particle Swarm," IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, vol. 42, 2012.
[16]T. Stutzle and H. Hoos, "MAX-MIN ant system and local search for the traveling salesman problem," in Evolutionary Computation, 1997., IEEE International Conference on, 1997, pp. 309-314.
[17]B. Bullnheimer, R. F. Hartl, and C. Strauss. (1999). Applying the ANT System to the Vehicle Routing Problem.
[18]K. Doerner, M. Gronalt, R. F. Hartl, M. Reimann, C. Strauss, and M. Stummer, SavingsAnts for the vehicle routing problem: Springer, 2002.
[19]陳家和 and 丁慶榮, "應用螞蟻演算法於時窗限制車輛途程問題之研究," 運輸學刊, vol. 17, pp. 261-280, 2005.
[20]Y. Wang, "A Hybrid Approach Based on Ant Colony System for the VRPTW," in Advanced Technology in Teaching-Proceedings of the 2009 3rd International Conference on Teaching and Computational Science (WTCS 2009), pp. 327-333, 2012.
[21]W. Elloumi, N. Rokbani, and A. M. Alimi, "Ant supervised by PSO," in Computational Intelligence and Intelligent Informatics, 2009. ISCIII'09. 4th International Symposium on, 2009, pp. 161-166.
[22]B. Yu, Z. Z. Yang, and B. Z. Yao, "A hybrid algorithm for vehicle routing problem with time windows," Expert Systems with Applications, vol. 38, pp. 435-441, 2011.
[23]Q. Ding, X. Hu, L. Sun, and Y. Wang, "An improved ant colony optimization and its application to vehicle routing problem with time windows," Neurocomputing, vol. 98, pp. 101-107, 2012.
[24]B. van Veen, M. Emmerich, Z. Yang, T. Bäck, and J. Kok, "Ant Colony Algorithms for the Dynamic Vehicle Routing Problem with Time Windows," in Natural and Artificial Computation in Engineering and Medical Applications, ed: Springer, 2013, pp. 1-10.
[25]B. Shuang, J. Chen, and Z. Li, "Study on hybrid PS-ACO algorithm," Applied Intelligence, vol. 34, pp. 64-73, 2011.
[26]J. Müller, "Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows," European Journal of Operational Research, vol. 202, pp. 223-231, 2010.
[27]M. M. Solomon. (2005). VRPTW BENCHMARK PROBLEMS. Available: http://w.cba.neu.edu/~msolomon/home.htm
[28]G. E. Wissenschaft, "Verteilt-parallele metaheuristiken zur tourenplanung," 2000.
[29]Y. Rochat and É. D. Taillard, "Probabilistic diversification and intensification in local search for vehicle routing," Journal of heuristics, vol. 1, pp. 147-167, 1995.
[30]H. Li and A. Lim, "Local search with annealing-like restarts to solve the VRPTW," European Journal of Operational Research, vol. 150, pp. 115-127, 2003.
[31]D. Mester, "An evolutionary strategies algorithm for large scale vehicle routing problem with capacitate and time windows restrictions," in Proceedings of the Conference on Mathematical and Population Genetics, University of Haifa, Israel, 2002.
[32]P. Shaw, "A new local search algorithm providing high quality solutions to vehicle routing problems," APES Group, Dept of Computer Science, University of Strathclyde, Glasgow, Scotland, UK, 1997.
[33]J. Berger and M. Barkaoui, "A parallel hybrid genetic algorithm for the vehicle routing problem with time windows," Computers & Operations Research, vol. 31, pp. 2037-2053, 2004.
[34]J. Homberger and H. Gehring, "Two evolutionary metaheuristics for the vehicle routing problem with time windows," Infor-Information Systems and Operational Research, vol. 37, pp. 297-318, 1999.
[35]L.-M. Rousseau, M. Gendreau, and G. Pesant, "Using constraint-based operators to solve the vehicle routing problem with time windows," Journal of heuristics, vol. 8, pp. 43-58, 2002.
[36]L. Gambardella, E. Taillard, and G. Agazzi, "MACS-VRPTW: A Multiple Ant Colony System For Vehicle Routing Problems With Time Windows in New ideAs in optimization, 1999, Edited by D," ed: Corne, 1999.
[37]R. Bent and P. V. Hentenryck, "A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows," Computers & Operations Research, vol. 33, pp. 875-893, 2006.
[38]G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt, and G. Dueck, "Record breaking optimization results using the ruin and recreate principle," Journal of Computational Physics, vol. 159, pp. 139-171, 2000.
[39]É. Taillard, P. Badeau, M. Gendreau, F. Guertin, and J.-Y. Potvin, "A tabu search heuristic for the vehicle routing problem with soft time windows," Transportation science, vol. 31, pp. 170-186, 1997.
[40]P. Shaw, "Using constraint programming and local search methods to solve vehicle routing problems," in Principles and Practice of Constraint Programming—CP98, ed: Springer, 1998, pp. 417-431.
[41]J.-F. Cordeau, G. Laporte, and A. Mercier, "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational research society, vol. 52, pp. 928-936, 2001.
[42]Z. J. Czech and P. Czarnas, "Parallel simulated annealing for the vehicle routing problem with time windows," in 16th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP 2008), 2002, pp. 0376-0376.
[43]T. Ibaraki, M. Kubo, T. Masuda, T. Uno, and M. Yagiura, "Effective local search algorithms for the vehicle routing problem with general time window constraints," in Proc. of MIC, 2001, pp. 293-297.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關點閱論文