(3.210.184.142) 您好!臺灣時間:2021/05/12 03:38
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:謝富任
研究生(外文):Fu Ren Hsieh
論文名稱:植基於粒子群優化法結合啟發式演算法求解物流車輛路由最佳化問題之研究
論文名稱(外文):A combination of particle swarm optimization and heuristic algorithm for solving vehicle routing problem
指導教授:陳瑞茂
指導教授(外文):Ruey Maw Chen
學位類別:碩士
校院名稱:國立勤益科技大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:中文
論文頁數:83
中文關鍵詞:超啟發式演算法最佳化粒子群優化法物流管理排程問題車輛路由問題
外文關鍵詞:Meta-heuristicOptimizationParticle Swarm Optimization (PSO)Logistics ManagementScheduling problemVehicle Routing Problem (VRP)
相關次數:
  • 被引用被引用:0
  • 點閱點閱:151
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
工業發展帶動了經濟的成長,物流產業的運作與發展跟著活絡。作業研究中(Operation Research, OR),有一種以實際的物流問題所定義的排程問題(Scheduling problem)稱之為車輛路由問題(Vehicle Routing Problem, VRP)。根據限制條件與需求考量的差異,也定義出各種不同的車輛路由問題,此類問題已被證實為難以求得最佳解的NP-hard問題。
近年來超啟發式演算法(Meta-heuristic)被廣泛地用於求解NP問題上,本文以超啟發式演算法中的粒子群優化法(Particle Swarm Optimization, PSO)為基礎,結合其他啟發式演算法(Heuristic algorithm)與區域搜尋法(Local search)求解車輛路由問題,最佳化其排程結果,並設計出一圖形化使用者介面(Graphical User Interface, GUI)以利於演算法參數之調整與結果顯示。
在本文將使用OR Library中的具容量限制之車輛路由問題(Capacitated Vehicle Routing Problem, CVRP)題庫做為測試例題。最後與其他文獻比較以顯示本文設計之演算法可以有效的解決車輛路由問題。

The industry develops vigorously, therefore aroused the growth of economy. Increasingly, the operation and development of logistics industry are prosperous. In operations research, a kind of scheduling problem is similar to logistics problem which is called vehicle routing problem (VRP). The VRP has been confirmed to NP-hard. Furthermore according to different conditions and restrictions, the VRP can be subdivided into many different types.
Recently, the meta-heuristic algorithms have been widely applied to solve NP problems. And the particle swarm optimization (PSO) is one of the meta-heuristic algorithms. In this thesis, the proposed scheme is PSO-based and involve with other heuristics and local search for solving VRP and to optimize the scheduling result.
In order to conveniently set the algorithm’s parameters and display the result the Graphical User Interface (GUI) is provided. In this thesis, the benchmark for experiment is the Capacitated Vehicle Routing Problem (CVRP) instances of OR Library. Finally, the simulate results will be compare with other researches. The simulate results indicate that the proposed scheme is sound for solving the VRP.

摘 要 I
ABSTRACT II
誌謝 III
目錄 IV
表目錄 VI
圖目錄 VII
第一章 緒論 8
1.1 研究背景 8
1.2 研究目的 10
1.3 研究方法及流程 12
第二章 排程問題 15
2.1 排程問題簡介 15
2.2 排程問題應用 16
2.3 規劃排程之方法簡介 17
第三章 車輛路由問題 21
3.1 車輛路由問題之演進 21
3.2 各類車輛路由問題之介紹 23
3.3 車輛路由問題之求解策略 32
第四章 粒子群優化法求解具容量限制之車輛路由問題 35
4.1 超啟發式演算法 35
4.2 粒子群優化法求解車輛路由問題 37
4.2.1 粒子群優化法簡介 37
4.2.2 編碼方式 40
4.2.3 強化粒子群優化法及結合其他啟發式演算法 41
4.2.4 粒子群優化法結合啟發式演算法求解車輛路由問題流程圖 59
第五章 效能分析與實作 60
5.1 題型介紹 60
5.2 數據測試 64
5.2.1 初始解 65
5.2.2 慣性權重w 66
5.2.3 通訊拓樸 67
5.2.4 局部搜尋(local search)與路徑再建構(Path relink) 68
5.3 效能比較 70
5.4 使用者介面實作 74
第六章 結論與後續研究 77
參考文獻 79


[1] R. Ruiz, and T. Stützle, "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem", European Journal of Operational Research, Vol. 177, pp. 2033-2049, 2007.
[2] L. Wang, L. Zhang, and D. Z. Zheng, "An effective hybrid genetic algorithm for flow shop scheduling with limited buffers", Comput. Oper. Res., Vol. 33, pp. 2960-2971, 2006.
[3] V. Ciesielski, and P. Scerri, "Real time genetic scheduling of aircraft landing times", Proceedings of The 1998 IEEE International Conference on Evolutionary Computation, pp. 360-364, 1998.
[4] A. P. Saraf, and G. L. Slater, "An efficient combinatorial optimization algorithm for optimal scheduling of aircraft arrivals at congested airports", 2006 IEEE Aerospace Conference, pages 11, 2006.
[5] T. W. Chiang, and H. Y. Hau, "Railway Scheduling System Using Repair-based Approach", Seventh International Conference on Tools with Artificial Intelligence, pp. 71, 1995.
[6] 劉慧燕, "不定期船運船舶排程問題之研究", 國立成功大學交通管理學系博士論文
[7] Vejzovic, Zanin, Humo, and Emir, "A Software Solution for A Mathematical Model of Classroom-Period Schedule De-fragmentation", The International Conference on Computer as a Tool EUROCON 2007, pp. 2034-2038, 2007.
[8] R. M. Chen and C. M. Wang, "Project Scheduling Heuristics Based Standard PSO for Task-Resource Assignment in Heterogeneous Grid", Abstract and Applied Analysis, Vol. 2011, Article ID 589862, 20 pages, 2011.
[9] K. Ross, and N. Bambo, "Dynamic quality of service control in packet switch scheduling", IEEE International Conference on Communications 2005 (ICC 2005) Vol. 1, pp. 396-401, 2005.
[10] K. Decker, and J. Li, "Coordinated hospital patient scheduling", Proceedings of International Conference on Multi Agent Systems, pp. 104-111, 1998.
[11] M. Ohki, A. Morimoto, and K. Miyake, "Nurse Scheduling by Using Cooperative GA with Efficient Mutation and Mountain-Climbing Operators", The 3rd International IEEE Conference on Intelligent Systems, pp. 164-169, 2006.
[12] C. W. Spry, and M. A. Lawley, "Evaluating hospital pharmacy staffing and work scheduling using simulation", Proceedings of the Winter Simulation Conference, pp. 4-8, 2005.
[13] R. Kolisch, and S. Hartmann, "Heuristic Algorithms for Solving the Resource-Constrained Project Scheduling Problem: Classification and Computational Analysis", Algorithms and applications, pp. 147–178, 1999.
[14] R. Kolisch, and S. Hartmann, "Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem", European Journal of Operational Research, Vol. 127, Issue 2, pp. 394-407, 2000.
[15] R. Kolisch and S. Hartmann, "Experimental investigation of heuristics for resource-constrained project scheduling: An update", European Journal of Operational Research, Vol. 174, pp. 23-37, 2006.
[16] R. M. Chen, "Particle Swarm Optimization with Justification and Designed Mechanisms for Resource-Constrained Project Scheduling Problem", Expert Systems With Applications, Vol. 38, No. 6, pp. 7102-7111, 2011.
[17] C. W. Chiang, Y. Q. Huang, and W. Y. Wang, "Ant colony optimization with parameter adaptation for multi-mode resource-constrained project scheduling", J. Intell. Fuzzy Syst., Vol. 19, pp. 345-358, 2008.
[18] J. Alcaraz, C. Maroto, and R. Ruiz, "Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms", Journal of the Operational Research Society, 54, pp. 614-626, 2003.
[19] N. Damak, B. Jarboui, P. Siarry, and T. Loukil, "Differential evolution for solving multi-mode resource-constrained project scheduling problems", Computers and Operations Research, Vol. 36, pp. 2653-2659, 2009
[20] S. Elloumi, and P. Fortemps, "A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem", European Journal of Operational Research, Vol. 205, pp. 31-41, 2010
[21] A. Lova, , P. Tormos, , M. Cervantes, , and F. Barber, "An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes", International Journal of Production Economics, Vol. 117, pp. 302-316, 2009.
[22] M. Ranjbar, B. D. Reyck, and F. Kianfar, "A hybrid scatter-search for the discrete time/resource trade-o_ problem in project scheduling", European Journal of Operational Research, Vol. 193, pp. 35-48, 2009.
[23] V. V. Peteghem, and M. Vanhoucke," A genetic algorithm for the preemptive and non-preemtive multi-mode resource-constrained project scheduling problem", European Journal of Operational Research, Vol. 201, pp. 409-418, 2010
[24] T. Wauters, , K. Verbeeck, , G. V. Berghe, and P. D. Causmaecker, "Learning agents for the multi-mode project scheduling problem", Journal of the Operational Research Society, Vol. 62, pp. 281-290, 2011
[25] 曾垂紀, "馬來西亞南北高速公路融資方案方式專案研究", 高鐵籌備處研究報告(1996)中收錄, 1996
[26] P. Mandal, and A. Gunasekaran, "Issues in implementing ERP: A case study", European Journal of Operational Research, Vol. 146, Issue 2, pp. 274-283, 2003.
[27] 蔡登茂, "專案資源需求規劃與排程問題之研究" , 中華民國管理科學學會
[28] 宋祚忠, 楊劍東,及蒲創城, "造船廠船段組合作業排程問題之研究"
[29] A. V. Breedam, "An Analysis of the Behavior of Heuristics for the Vehicle Routing Problem for a Selection of Problems with Vehicle-Related. Customer-Related, and Time-Related Constraints", University of Antwerp, 1994.
[30] G. A. P. Kinderwater, and M. W. P. Savelsbergh, "Vehicle Routing: Handling Edge Exchanges", Local Search in Combinatorial Optimization Wiley, Chichester, 1997.
[31] J. Renaud, and F. F. Boctor, "A Sweep-Based Algorithm for the Fleet Size and Mix Vehicle Routing Problem", European Journal of Operational Research, Vol. 140, pp. 618-628, 2002.
[32] A. Munawar, M. Wahib, M. Munetomo, and K. Akama, "Implementation and Optimization of cGA+LS to solve Capacitated VRP over Cell/B.E.", International Journal of Advancements in Computing Technology, Vol. 1, No. 2, pp. 16-28, 2009.
[33] B. M. Baker, M. A. Ayechew, "A genetic algorithm for the vehicle routing problem", Computers &; Operations Research, Vol. 30, pp. 787-800, 2003.
[34] I. H. Osman, "Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem", Annals of Operations Research, Vol. 41, pp. 421-451, 1993.
[35] P. Badeau, M. Gendreau, F. Guertin, J. Y. Potvin, É. D. Taillard, "A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows", Transportation Research, pp. 109-122, 1997.
[36] A. L. Chen, G. K. Yang, and Z. M. Wu, "Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem", Journal of Zhejiang University SCIENCE A, Vol. 4, pp. 607-614, 2006.
[37] Z. Wang, M. Zhou, J. Li, and J. Fan, "Research in Capacitated Vehicle Routing Problem Based on Modified Hybrid Particle Swarm Optimization", Intelligent Computing and Intelligent Systems, Vol. 3, pp. 289-293, 2009
[38] B. Yu, Z. Z. Yang, and B. Yao, "An improved ant colony optimization for vehicle routing problem", European Journal of Operational Research, Vol. 196, pp. 171-176, 2009.
[39] P. Yang, Y. M. Qian, "A Particle Swarm Optimization to Vehicle Routing Problem with Fuzzy Demands", Journal of Convergence Information Technology, Vol. 5, No. 6, pp. 112-119, 2010.
[40] J. Kennedy, and R. Eberhart, "Particle swarm optimization", IEEE international conference on neural networks, Vol. 4, pp. 1942-1948, 1995.
[41] J. Kennedy, and R. C. Eberhard, "A Discrete Binary Version of the Particle Swarm Algorithm", IEEE Conference on Systems, Man, and Cybernetics, Piscataway 5, pp.4104–4109, 1997.
[42] D. Bratton, and J. Kennedy, "Defining a Standard for Particle Swarm Optimization", IEEE Swarm Intelligence Symposium, pp. 120-127, 2007.
[43] B. Liu, L. Wang, and Y. H. Jin, "An Effective PSO-Based Memetic Algorithm for Flow Shop Scheduling", IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, Vol. 37, No. 1, 2007.
[44] J. K. Lenstra, and A. H. G. R. Kan, "Complexity of vehicle routing and scheduling problems", Networks, pp. 221-227, 1981
[45] M. D. Groot, "Optimal Statistical Decisions", Wiley Classics Library, ISBN 0-471-68029-X, 2004.
[46] Z. Michalewicz, and D. B. Forgel, "How to Solve It: Modern Heuristics", Springer, ISBN 3-540-660615, 2004
[47] A. Schrijver, "Theory of Linear and Integer Programming", John Wiley and Sons, ISBN 0-471-98232-6, 1998.
[48] I. Sabuncuoglu, B. Gurgun, "A neural network model for scheduling problems", European Journal of Operational Research, Vol. 93, pp. 288-299, 1993
[49] G. B. Dantzig, J. H. Ramser, "The Truck Dispatching Problem", Management Science, Vol. 6, No.1, pp. 80-91, 1959
[50] G. Laporte, "The vehicle routing problem: An overview of exact and approximate algorithms", European Journal of Operational Research, Vol. 59, pp. 345-358, 1992
[51] J. Lysgaard, A. N. Letchford, and R. W. Eglese, "A new branch-and-cut algorithm for the capacitated vehicle routing problem", Mathematical Programming, Vol. 100, pp. 423-445, 2004
[52] R. Fukasawa, H. Longo, and J. Lysgaard, "Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem", Mathematical Programming, Vol. 106, pp. 491-511, 2006.
[53] M. Gendreau, and G. L. R. Séguin, "An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers", Transportation Science, Vol. 29, No. 2, pp. 143-155, 1995.
[54] I. H. Osman, and G. Laporte, "Metaheuristics:A bibliography", Springer, Vol. 63, pp. 511-623, 1996
[55] Metaheuristics Network:www. Metaheuristics.net/
[56] L. Bodin , B. L. Golden, A. Assad, M. Ball, "Routing and Scheduling of Vehicles and Crews", Comput. &; Ops Res, Vol. 10, No.2, pp. 63- 211, 1983
[57] K. Lei, Y. Qiu, and Y. He, "A new adaptive well-chosen inertia weight strategy to automatically harmonize global and local search ability in particle swarm optimization", ISSCAA, pp.977-980, 2006.
[58] K. C. Lee, and J. S. Ou, "Adaptive Color Image Enhancement Using Particle Swarm Optimization", Journal of Informatics &; Electronics, Vol. 2, pp. 29-38, 2007.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
系統版面圖檔 系統版面圖檔