跳到主要內容

臺灣博碩士論文加值系統

(18.97.9.169) 您好!臺灣時間:2025/02/18 01:38
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:許富雄
研究生(外文):Fu-Hsung Hsi
論文名稱:以模擬退火法結合區域搜索法應用於載重限制車輛途程問題
論文名稱(外文):Applying Simulated Annealing Approach for Capacitated Vehicle Routing Problems
指導教授:林 詩 偉
指導教授(外文):Shih-Wei Lin
學位類別:碩士
校院名稱:華梵大學
系所名稱:資訊管理學系碩士班
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:58
中文關鍵詞:模擬退火法車輛途程問題區域搜索法組合問題
外文關鍵詞:Simulated AnnealingVehicle Routing ProblemLocal SearchCombinatorial Problem
相關次數:
  • 被引用被引用:19
  • 點閱點閱:459
  • 評分評分:
  • 下載下載:142
  • 收藏至我的研究室書目清單書目收藏:0
載重車輛途程問題(Capacitated Vehicle Routing Problem, VRP)是一個在供應鍊管理中相當重要的問題。CVRP問題目的是以最小的成本,且在顧客的需求已知的狀態下分送貨物到每位客戶手中,車輛最終必須回到出發的場站。
CVRP是一個困難的組合問題,它包含了背包問題和旅行員銷售問題,除了考慮路線的建構外,還需考慮不同的限制條件,如車輛最大載重限制和最大旅行距離限制等。本研究應用了模擬退火法結合區域搜索法來求解不同的顧客分佈型態和顧客數的CVRP問題。
為了驗證所發展之演算法,本研究以Christofides等學者的14個小型例題和Golden等學者的8個大型例題作為測試,小型例題的顧客數範圍為50到199,大型例題的顧客數範圍為240到440。
在小型例題中,本研究方法在合理的時間內求得6個已知最佳解。對小型及大型例題而言,研究結果和相關文獻相比,本研究獲得較小的演算平均誤差百分比,顯示本研究所發展之方法可有效應用於不同類型的CVRP問題。
The capacitated vehicle routing problem (CVRP) is one of the elemental problems in supply chain management. The objective of CVRP is to deliver a set of customers with known demands on minimum-cost vehicle routes originating and terminating at a delivery depot.
CVRP is a difficult combinatorial problem, since it contains both the bin packing problem and the traveling salesperson problem as special cases. Besides considering the construction of the path, one also needs to consider different limitations such as the loading capacity of the vehicle and maximum allow traveling distance. A simulated annealing (SA) combining local search approach is developed in this research to solve the capacitated vehicle routing problems with different distribution and number of customers.
In order to verify the proposed SA approach, Christofides’ 14 small problems and Golden’s 8 large problems are used. The small problems have the number of customers range from 50 to 199 while the large problems have the number of customers range from 240 to 440. In the small problems, the proposed approach obtained six solutions which equal to the best solution found so far using the reasonable computational time. For both small and large problem sets, the solutions obtained have the smaller average relative deviation percentage (RDP) when compared with the best solution found so far in the literature. Therefore, the developed approach can perform well in different problem settings.
致謝......................... . I
摘要.......................... . Ⅱ
英文摘要........................ . Ⅲ
目錄........................... Ⅳ
表錄........................... VI
圖錄............................ VII
一、緒論..........................1
1.1 研究背景與動機.....................1
1.2 研究目的........................2
1.3 研究範圍........................3
1.4 研究流程........................3
二、文獻探討.................... ... 5
2.1 車輛途程問題的種類.................5
2.2 CVRP問題之求解方法分類............. 8
2.3 傳統啟發式演算法..................9
2.4 萬用啟發式演算法..................13
三、問題定義和研究方法.................. 19
3.1 CVRP問題定義與假設................19
3.2 所發展的演算法...................21
3.2.1 參數設定...................21
3.2.2 建構初始解..................22
3.2.3 區域搜索法..................24
3.2.4 模擬退火法執行步驟..............27
四.例題測試與實驗設計...................29
41 實驗測試例題與目前最佳解.............. 29
4.2 SA-CVRP參數測試分析............... 31
4.2.1 初始溫度...................32
4.2.2 停止溫度...................33
4.2.3 冷卻率....................33
4.2.4 迭代次數...................34
4.3 結果分析與比較...................35
4.3.1小型例題結果分析與比較............ 35
4.3.2大型例題結果分析與比較............ 39
五、結論與後續研究.................... 41
5.1結論........................41
5.2未來研究方向....................42
參考文獻......................... 41
附錄........................... 43
[1] 陳勝男,「禁忌搜尋法應用於車輛路線問題之研究」,大葉大學工業工程研究所碩士論文,民國85年。
[2] 林明俊 ,「隨機環境下多車種車派車問題之研究」,中原大學工業工程研究所碩士論文,民國85年。
[3] 羅中育,「田口品質工程應用於模擬退火法參數組合─以旅行推銷員問題(TSP)為例」, 國立雲林科技大學工業工程與管理研究所碩士論文,民國90年。
[4] 莊志諒,配送網路之設計研究,國立交通大學,碩士論文,民國77年。
[5] 黃麗芬,物流中心貨品配送途程規畫之研究,私立逢甲大學,碩士論文,民國86年。
[6] Garey, M. R. and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP Completeness, W. H. Freeman & Co., New York, 1979.
[7] Christofides, N., A. Mingozzi, and P. Toth, The Vehicle Routing Problem, In N. Christofides, A. Mingozzi, P. Toth, and C. Sandi, editors, Combinatorial Optimization, 1979, pp. 325-338, Wiley, Chichester.
[ 8] Golden, B. L., E.A. Wasil, J.P. Kelly, and I.-M. Chao. Metaheuristics in Vehicle Routing, In T. G.Crainic and G. Laporte, eds, Fleet Management and Logistics. Boston: Kluwer, 1998,pp. 33-56.
[9] Bodin, L., Golden, B., Assad and A., Ball, M., “Routing and Scheduling of Vehicles and Crews: the state of the art,” Computer & Operations Research, Vol. 10, No. 2, 1983,pp. 63-67.
[10] Golden, A., A. A. Assad, and L. Levy, and F. Gheysens, “The Fleet Size and Mix Vehicle Routing Problem,” Management Science & Statistics Working Paper No. 82-020, University of Maryland at College Park, 1982.
[11] Newton, R., and W. Thomas, “Design of School Bus Route by Computer , ”Socio-Economic Planning Sciences, vol. 3,1969,pp. 75-85..
[12]Bodin, L. and S. Kursh, “A Computer-Assisted System for the Routing and Scheduling of Street Sweepers,” Operations Research, vol. 26, no. 4, 1978,pp. 525-537.
[13]Bodin, L. and S. Kursh, “A detailed Description of a Street Sweeper Routing andScheduling System,” Computers and Operations Research, vol. 6, 1979,pp. 191-198,.
[14] Clarke, G. and J. W. Wright, “Scheduling of vehicles from a central depot to a number of delivery points,” Operations Research, vol. 12, 1964, pp. 568-581
[15]Norback,j.p. and Love,R. F.,”Heuristic for the Hamiltonian path problem in Euclidean two space,” Journal of Operations Research Society , Vol.30,1979,pp.363-368.
[16] Anily, S and A. Federgruen, “Ergodicity in parameter nonstationarymarkov chains: an application to simulated annealing methods,” Operations Search, Vol. 35,1987,pp. 867-874.
[17] Rosenkrantz, D. J., Stearns, R. E. and Lewis, P. N., “An analysis of Several Heuristics for the Traveling Salesman Problem,” SLAM Journal on Computing, vol. 6, 1977,pp. 563-581.
[18]Gillett, B. and J. Johnson, “Multi-Terminal Vehicle-Dispatch Algorithm,” Omega, vol. 4,1976,pp. 711-718.
[19] Chapleau, L., J. Ferland, and J. M. Rousseau, “Clustering for Routing in Dense Area,”University of Montreal Transportation Research Center Publication, no. 206,1981.
[20]Karp, R. “Probabilistic Analysis of Partitioning Algorithms for the Traveling Salesman Problem in the Plan,” Mathematics of Operations Research, vol. 2, 1977,pp. 209-224.
[21] Glover, F. “Heuristics for Integer Programming Using Surrogate Constraints,” Decision Sciences, vol. 8, no. 1,1977, pp.156-166.
[22] Willard, J. A. G. “Vehicle Routing Using γ-Optimal Tabu Search, M.Sc. Dissertation,” The Management School, Imperial College, London, 1989.
[23] Lin, S., “Computer solutions of the traveling salesman problem,” The Bell System Technical Journal, Vol. 44, 1965,pp. 2245-2269.
[24] Or. I., “Traveling salesman-type Combinatorial Problems and TheirRealation on the Logistics of regional Blood Banking”, Ph. D.Dissertation, Northwestern University, 1976.
[25] Osman, H. “Metastrategy Simulated Annealing and Tabu Search Algorithms for t he Vehicle Routing Problem,” Annals of Operations Research, vol. 41, 1993, pp. 421-451.
[26] Gendreau, M. P., A. Hertz and G. Laporte, “A tabu search heuristic for the vehicle routing problem,” Management Science, vol. 40, 1994, pp. 1276-1290.
[27] Kirkpatrik, S., C. D. Gelatt, and J. M. P. Vecchi, “Optimization by Simulated Annealing,” Science, vol. 220, 1983, pp. 671-680.
[28]Robuste, F., C. F. Daganzo, and R. Souleyrette II, “Implementing Vehicle Routing Models,” Transportation Research, vol. 24B,1990,pp. 263-286.
[29]Chiang, W., and Russell, R., “Simulated annealing Meta-heuristics for the Vehicle Routing Problem with Time Windows,” Annals of Operations Research, Vol. 63, 1996, pp. 3-27.
[30]Dorigo, M., “Optimization, Learning and Natural Algorithms,” Ph.D. Thesis, Politecnico di Milano, Italy, 1992.
[31]Kawamura, H., M. Yamamoto, T. Mitamura, K. Suzuki, and A. Ohuchi, “Cooperative Search on Pheromone Communication for Vehicle Routing Problems,” IEEE Transactions on Fundamentals, 1998, pp. 1089-1096.
[32]Bullnheimer, B., R. F. Hartl, and C. Strauss, “An Improved Ant System for the Vehicle Routing Problem,” In S. Vo s, S. Martello, I. H. Osman, and C. Roucairol, editors,Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, 1998,pp. 109-120, Kluwer, Boston.
[33]Bullnheimer, B. R. F. Hartl, and C. Strauss, “An improved Ant System algorithm for the Vehicle Routing Problem,” Annals of Operations Research, vol. 89,1999 pp. 319-328.
[34] Holland, J. H. , “Adaptation in Natural and Artificial System,” The University of Michigan Press, 1975.
[35]Van Breedam, A. ,“An Analysis of the Effect of Local Improvement Operators in
Genetic Algorithms and Simulated Annealing for the Vehicle Routing Problem,” RUCA Working Paper 96/14, University of Antwerp, Belgium, 1996.
[ 36] Schmitt,L. J. ,“An Empirical Computational Study of Genetic Algorithms to Solve Order Based Problems: An Emphasis on TSP and VRPTC,” Ph.D. Dissertation, Fogelman College of Business and Economics, University of Memphis, 1994.
[37] Schmitt, L. J. “An Evaluation of a Genetic Algorithmic Approach to the Vehicle Routing Problem,” Working Paper, Department of Information Technology Management,Christian Brothers University, Memphis, 1995.
[38]Charon, I. & O. Hudry , “The Noising Method: a New Method for Combinatorial Optimization,” Operations Research Letters, Vol. 14, 1993, pp.133-137.
[39]Dueck, G., and T. Scheuer “Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing,” Journal of Computational Physics, Vol. 90,1990 pp.161-175.
[40] Schumann, M. and R. Retzko, “Self-Organizing Maps for Vehicle Routing Problems –Minimizing an Explicit Cost Function,” Proceedings of the International Conference on Artificial Neural Networks, 1995,pp. II-401-406, Paris.
[41] Xu , J. and J.P.Kelly, “A network flow-based tabu search heuristic for the vehicle routing problem," Transportation Science, vol. 30, 1996, pp.379-393.
[42]Taillard, E. D. “Parallel Iterative Search Methods for Vehicle Routing Problem,”Networks, vol. 23,1993, pp. 661-673.
[43]Rochat ,Y. and E. D. Taillard, “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing,” Journal of Heuristics, vol. 1,1995, pp. 147-167.
[44]Mester, D. and O. Br¨aysy. . “Active Guided Evolution Strategies for the Large-Scale Vehicle Routing Problems with Time Windows.” Computers & Operations Research 32, 2005, pp.1593–1614.
[ 45]Prins, C. “A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem.” Computers& Operations Research 31(12), 2004, pp.1985–2002.
[ 46]Toth ,P. and D. Vigo, “The granular tabu search and its application to the vehicle-Routing Problem,” Journal on Computing , vol. 15, 2003, pp. 333-346
[ 47]Gendreau ,M., G. Laporte, and J.-Y. Potvin. Metaheuristics for the VRP. In The Vehicle Routing Problem, P. Toth and D. Vigo (eds), SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002, pp129-154.
[ 48]Doerner, K., M. Gronalt, R. F. Hartl, M. Reimann, C. Strauss, and M. Stummer,“SavingsAnts for the Vehicle Routing Problem,” POM Working Paper 2002,Department of Production and Operations Management, University of Vienna,2002.
[49]Barrie M. Baker, M.A. Ayechew” A genetic Algorithm for the Vehicle Routing Problem”, Computers & Operations Research 30 , 2003, pp787–800
[50]Golden, B. L., E.A. Wasil, J.P. Kelly, and I.-M. Chao. Metaheuristics in Vehicle Routing, In T. G. Crainic and G. Laporte, eds, Fleet Management and Logistics. Boston: Kluwer, 1998, pp. 33-56.
[51] Ergun, O¨., J.B. Orlin, and A. Steele-Feldman. “Creating very Large Scale Neighborhoods out of Smaller ones by Compounding Moves: A Study on the Vehicle Routing Problem.” Technical report, Massachusetts Institute of Technology, 2003.
[52] Ho.Sin C. ,Michel Gendreau,” Path relinking for the vehicle routing problem” J Heuristics vol. 12, 2006, pp 55–72
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top