臺灣博碩士論文加值系統

為了貫徹螞蟻演算法之中心思想，本研究嘗試模擬螞蟻實際覓食方式，提出同時釋放並且同時行進之螞蟻建構路線模式，以節省法(Savings)建構初始路線，蟻群最佳化演算法(Ant Colony Optimization, ACO)求解具車輛容量與車輛路線長度限制之車輛途程問題(The Vehicle Routing Problem under Capacity and Distance Constraints, DCVRP)，以5隻螞蟻建構所有之問題路線，並且以2-opt交換法做鄰近解搜尋，直到無法再進行改善後停止，加入候選人名單(Candidate List)，以減少計算時間同時達到事先淘汰不良路徑的目的。本研究根據Bullnheimer 等學者(1999)之研究文獻中的測試問題，選擇以Christofides 等學者(1979)於1979年所提出之標準測試例題進行測試，並將其結果與其他方法做比較，發現本研究在具路線長度限制之問題中，明顯優於ASold (Bullnheimer 等學者,1999)、AS(Bullnheimer 等學者,1998)與SavingsAnt(Doerner等學者,2002)三種螞蟻方法，與四種傳統啟發式方法表較中ACO-DCVRP表現最好，在萬用啟發式方法中，ACO-DCVRP之結果亦明顯優於另外四種啟發式方法：Taburoute(Gendreau 等學者,1994)、Osman’s Ts(Osman,1993)、GTS(Toth等學者,1998)與SA (Osman ,1993)。

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1研究背景與動機 1
1.2研究目的 2
1.3研究範圍及假設 2
1.4研究流程 3
第二章 文獻回顧 5
2.1 途程問題之分類 5
2.2 車輛途程(VRP)問題之目標分類 6
2.3 車輛途程(VRP)問題之求解方法分類 6
2.4 啟發式(Heuristic)方法應用在車輛途程問題之文獻回顧與介紹 7
2.4.1 傳統啟發式方法(Classical Heuristics) 8
2.4.2 萬用啟發式方法(Metaheuristic) 15
第三章 問題定義與研究方法 21
3.1問題定義 21
3.2 研究方法 23
3.2.1轉換法則 27
3.2.2費洛蒙即時更新(Online Update) 30
3.2.3鄰近解搜尋(Local Search) 30
3.2.4費洛蒙離線更新(Offline Update) 31
第四章 數據分析 32
4.1參數設計 32
4.1.1螞蟻數量 34
4.1.2費洛蒙濃度初始值( ) 35
4.1.3候選人名單(Candidate List)長度 35
4.1.4參數( ) 36
4.1.5參數 38
4.1.6參數 與 39
4.1.7費洛蒙更新規則與鄰近解搜尋機制之影響 41
4.2標準例題測試 42
4.2.1 不同螞蟻方法於標準測試問題之比較 43
4.2.2 ACO-DCVRP與傳統啟發式方法之比較 46
4.2.3 ACO-DCVRP與萬用啟發式方法之比較 48
第五章 結論 51
5.1結論 51
5.2未來研究方向 52
參考文獻 53
附錄一 60

A. S. Alfa, S. S. Heragu, and M. Chen, “A 3-opt Based Simulated Annealing Algorithm for Vehicle Routing Problem,” Computers & Industrial Engineering, vol. 21, pp. 635-639, 1991.
J. E. Beasley, “Route-First Cluster-Second Methods for Vehicle Routing,” Omega, vol. 11, pp. 403-408, 1983.
L. Bodin and L. Berman, “Routing and Scheduling of school buses by computer,” Transportation Science, vol. 13, no. 2, pp. 113-129, 1979.
L. Bodin and S. Kursh, “A detailed Description of a Street Sweeper Routing and Scheduling System,” Computers and Operations Research, vol. 6, pp. 191-198, 1979.
L. Bodin and S. Kursh, “A Computer-Assisted System for the Routing and Scheduling of Street Sweepers,” Operations Research, vol. 26, no. 4, pp. 525-537, 1978.
L. D. Bodin, B. L. Golden, A. A. Assad, and M. O. Ball, “Routing and Scheduling of Vehicles and Crews. The State of the Art,” Computers and Operations Research, vol. 10, no. 2, pp. 63-211, 1983.
B. Bullnheimer, R. F. Hartl, and C. Strauss, “An Improved Ant System for the Vehicle Routing Problem,” In S. Voß, S. Martello, I. H. Osman, and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 109-120, Kluwer, Boston, 1998.
B. Bullnheimer, R. F. Hartl, and C. Strauss, “Applying the Ant System to the Vehicle Routing Problem,” Annals of Operations Research, vol. 89, pp. 319-328, 1999.
L. Chapleau, J. Ferland, and J. M. Rousseau, “Clustering for Routing in Dense Area,” University of Montreal Transportation Research Center Publication, no. 206, 1981.
N. Christofides, A. Mingozzi, and P. Toth, “The Vehicle Routing Problem,” In N. Christofides, A. Mingozzi, P. Toth, and C. Sandi, editors, Combinatorial Optimization, pp. 325-338, Wiley, Chichester, 1979.
N. Christofides, A. Mingozzi, and P. Toth, “ Exact Algorithm for the Vehicle Routing Problem, Based on Spanning Tree and Shortest Path Relaxations,” Mathematical Programming, vol. 20, pp. 255-282, 1981.
G. Clarke and J. W. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, vol. 12, pp. 568-581, 1964.
H. Crowder and M. Padberg, “Solving Large-Scale Symmetric Traveling Salesman Problem to Optimality,” Management Science, vol. 26, no. 5, pp. 495-509, 1980.
K. Doerner, M. Gronalt, R. F. Hartl, M. Reimann, C. Strauss, and M. Stummer, “SavingsAnts for the Vehicle Routing Problem,” POM Working Paper 02/2002, Department of Production and Operations Management, University of Vienna, 2002.
M. Dorigo, Optimization, Learning and Natural Algorithms, Ph.D. Thesis, Politecnico di Milano, Italy, 1992.
M. Dorigo and L. M. Gambardella, “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53-66, 1997.
M. Dorigo and L. M. Gambardella, “A Study of Some Properties of Ant-Q,” Technical Report IRIDIA 1996-4, Université Libre de Bruxelles, Belgium, 1996.
M. L. Fisher and R. Jaikumar, “A Decomposition Algorithm for Large-Scale Vehicle Routing,” Working Paper 78-11-05, Department of Decision Sciences, University of Pennsylvania, 1978.
M. L. Fisher and R. Jaikumar, “A Generalized Assignment Heuristic for Vehicle Routing,” Networks, vol. 11, no. 2, pp. 109-124, 1981.
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP Completeness, W. H. Freeman & Co., New York, 1979.
T. J. Gaskell, “Bases for Vehicle Fleet Scheduling,” Operational Research Quarterly, vol. 18, pp. 281-295, 1967.
M. Gendreau, A. Hertz and G. Laporte, “A Tabu Search Heuristic for the Vehicle Routing Problem,” Management Science, vol. 40, pp. 1276-1290, 1994.
H. Ghaziri, “Solving Routing Problems by a Self-Organizing Map,” In T. Kohonen, K. Makisara, O. Simula, and J. Kangas, editors, Artificial Neural Networks, pp. 829-834, North-Holland, Amsterdam, 1991.
H. Ghaziri, “Supervision in the Self-Organizing Feature Map: Application to the Vehicle Routing Problem,” In I. H. Osman and J. P. Kelly, editors, Meta-Heuristics: Theory and Applications, pp. 651-660, Kluwer, Boston, 1996.
B. Gillett and L. Miller, “A Heuristic Algorithm for the Vehicle Dispatch Problem,” Operations Research, vol. 22, pp. 340-349, 1974.
B. Gillett and J. Johnson, “Multi-Terminal Vehicle-Dispatch Algorithm,” Omega, vol. 4, pp. 711-718, 1976.
F. Glover, “Heuristics for Integer Programming Using Surrogate Constraints,” Decision Sciences, vol. 8, no. 1, pp.156-166, 1977.
A. Golden, 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.
K. Hansen and J. Krarup, ”Improvement of the Held-Karp Algorithm for the Symmetric Traveling Salesman Problem,” Mathematical Programming, vol. 7, pp. 87-96, 1982.
J. H. Holland, Adaptation in Natural and Artificial System, The University of Michigan Press, 1975.
R. Karp, “Probabilistic Analysis of Partitioning Algorithms for the Traveling Salesman Problem in the Plan,” Mathematics of Operations Research, vol. 2, pp. 209-224, 1977.
H. Kawamura, M. Yamamoto, T. Mitamura, K. Suzuki, and A. Ohuchi, “Cooperative Search on Pheromone Communication for Vehicle Routing Problems,” IEEE Transactions on Fundamentals, E81-A, pp. 1089-1096, 1998.
S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi, “Optimization Simulated Annealing,” Science, vol. 220, no. 4598, pp.671-680, 1983.
P. Krolak, W. Felts, and G. Marble, “A Man-Machine Approach Toward Solving the Traveling Salesman Problem,” Communications of the ACM, vol. 14, pp. 327-334, 1971.
P. Krolak, W. Felts, and J. Nelson, “A Man-Machine Approach Toward Solving the Generalized Truck Dispatching Problem,” Transportation Science, vol. 6, pp. 149-170, 1972.
Y. Matsuyama, “Self-Organization via Competition, Cooperation and Categorization Applied to Extended Vehicle Routing Problems,” Proceedings of the International Joint Conference on Neural Networks, pp. I-385-390, Seattle, Washington, 1991.
R. Newton and W. Thomas, “Design of School Bus Route by Computer,” Socio-Economic Planning Sciences, vol. 3, pp. 75-85, 1969.
I. H. Osman and J. P. Kelly, “Meta-Heuristics: An Overview,” In I. H. Osman and J. P. Kelly, editors, Meta-Heuristics: Theory and Applications, pp. 1-21, Kluwer, Boston, 1996.
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.
V. M. Pureza and P. M. França, “Vehicle Routing Problems via Tabu Search Metaheuristic,” Technical Report CRT-347, Centre for Research on Transportation, Montreal, 1991.
M. Reimann, M. Stummer, and K. Doerner, “A Savings Based Ant System for the Vehicle Routing Problem,” POM Working Paper 03/2002, Department of Production and Operations Management, University of Vienna, 2002.
M. Reimann, M. Stummer, and K. Doerner, “A Savings Based Ant System for the Vehicle Routing Problem,” POM Working Paper 03/2002, Department of Production and Operations Management, University of Vienna, 2002.
F. Robusté, C. F. Daganzo, and R. Souleyrette II, “Implementing Vehicle Routing Models,” Transportation Research, vol. 24B, pp. 263-286, 1990.
Y. Rochat and E. D. Taillard, “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing,” Journal of Heuristics, vol. 1, pp. 147-167, 1995.
L. J. Schmitt, 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.
L. J. Schmitt, “An Evaluation of a Genetic Algorithmic Approach to the Vehicle Routing Problem,” Working Paper, Department of Information Technology Management, Christian Brothers University, Memphis, 1995.
M. Schumann and R. Retzko, “Self-Organizing Maps for Vehicle Routing Problems — Minimizing an Explicit Cost Function,” Proceedings of the International Conference on Artificial Neural Networks, pp. II-401-406, Paris, 1995.
H. Stern and M. Dror, “Routing electric Meter Readers,” Computers and Operations Research, vol. 6, pp. 209-223, 1979.
E. D. Taillard, “Parallel Iterative Search Methods for Vehicle Routing Problem,” Networks, vol. 23, pp. 661-673, 1993.
P. Toth and D. Vigo, “The Granular Tabu Search (and Its Application to the Vehicle Routing Problem),” Working Paper, DEIS, University of Bologna, 1998
P. Toth and D. Vigo, The Vehicl Routing Problem, Siam, pp.121-125, 2001.
A. Van Breedam, “Improvement Heuristics for the Vehicle Routing Problem Based on Simulated Annealing,” European Journal of Operational Research, vol.86, pp. 480-490, 1995.
A. Van Breedam, “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.
J. A. G. Willard, Vehicle Routing Using γ-Optimal Tabu Search, M.Sc. Dissertation, The Management School, Imperial College, London, 1989.
A. Wren, Computers in Transport Planning and Operation, Ian Allan, London, 1971.
A. Wren and A. Holiday, “Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points,” Operational Research Quarterly, vol. 23, pp. 333-344, 1972.
P. Yellow, “A Computational Modification to the Savings Method of Vehicle Scheduling,” Operational Research Quarterly, vol. 21, pp. 281-283, 1970.
王文貞，圖書配送車輛排程問題之研究，國立成功大學，碩士論文，1997。
徐明輝，多部車一般車輛途程解算法之研究，私立元智大學，碩士論文，1997。
莊志諒，配送網路之設計研究，國立交通大學，碩士論文，1988。
陳坤賓，模擬退算法應用於車輛途程問題之研究，私立元智大學，碩士論文，1998。
敖君瑋，禁制搜尋法於軟性時窗限制之車輛問題研究，私立元智大學，碩士論文，1999。
黃麗芬，物流中心貨品配送途程規畫之研究，私立逢甲大學，碩士論文，1997。
廖亮富，含時間窗限制多部車車輛途程問題解算之研究，私立元智大學，碩士論文，1998。
韓復華、卓裕仁，門檻接受法、噪音擾動法與搜尋空間平滑法在車輛路線問題之應用研究與比較分析，運輸學刊，第9卷，第三期，113-144，1996。