運具排程問題(VRP)在這經濟社會中扮演一個重要的角色，它主要的目的在於求最小的成本，在顧客需求已知的情況下，滿足所有顧客的需求，運具排程問題是一種NP-hard問題，其包含了背包問題與旅行銷售員問題，且有車輛載重限制與最大旅行距離限制，我們的研究中，採用單一場站模式，車輛由場站出發，最後必回到場站。螞蟻群組最佳化(ACO)是一種新的啟發式演算法，目前已經成功的被應用在解最佳化組合問題上，螞蟻群組最佳化主要是以動態參數費洛蒙與靜態參數距離去尋優，不過，他仍然有停滯行為與過早收斂的缺點，當問題的複雜度增加時更為明顯。在這篇論文中，我們以vrpnc1-vrpnc10為我們的研究範例，提出了低費洛蒙限制、速度參數與隨機機制的方法去有效的改善這些缺點並比較這些結果，且配合傳統啟發式，使得螞蟻有更好的搜尋能力。

Vehicle routing problems (VRP) plays an important role in business. Its goal is mainly to search for the minimum cost and to satisfy the demands of the customers when the demands are known. VRP which contains backpack problem and travel salesman problem is a NP-hard problem, and it has the restriction of vehicle’s capacity and the largest distance. In our research, we adopt the type of single-depot, and the vehicles set out from the depot and then get back. Ant colony optimization (ACO) is a new heuristic algorithm which has been successfully applied to solve combinatorial optimization problems. ACO mainly depends on a dynamic (pheromone) parameter and a static (distance) parameter to search for optimal. However, it still has some deficits such as stagnation behavior and premature convergence. The deficits will be more evident when the complexity of VRP increases. In the thesis, vrpnc1 ~ vrpnc10 are used as our research instances. We proposed the methods of lower pheromone bound and speed parameter and random mechanism to effectively overcome these deficits and then cooperated with classical heuristic to improve the search capability of ACO.

[1] N. Christofides, A. Mingozzi, and P. Toth, ”The vehicle routing problem,” Combinatorial Optimization, Wiley, Chichester, pp. 313-338, 1979.
[2] L. D. Bodin, B. L. Golden, A. A. Assad, and M. O. Ball, “Routing and scheduling of vehicles and crews,” Computers and Operations Research, vol. 10, no. 2, pp. 63-211, 1983.
[3] G. Reinelt, “The traveling salesman: Computational solutions for TSP applications,” Lecture Note in Computer Science, vol. 840, Springer-Verlag, Berlin, 1994.
[4] 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.
[5] R. A. Russell and D. Gribbin, “A multiphase approach to the period routing problem,” Networks, vol. 21, pp. 747-765, 1991.
[6] M. Bellmore and S. Hong, “Transformation of Multi-Salemen Problem to the Srandard Traveling Salesman Problem,” Journal of ACM, vol. 21, pp. 500-504, 1974.
[7] http://neo.lcc.uma.es/radi-aeb/WebVRP/
[8] M. Grotschel, “Graphic programming using odd and even points,” Chinese Mathematics, vol. 1, pp. 273-277, 1962.
[9] 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.
[10] G. Laporte, M. Gendreau, J. Y. Potvin, and F. Semet, “Classical and modern heuristics for the vehicle routing problem,” International Transactions in Operational Research, vol. 7, pp. 285-286, 2000.
[11] B. L. Gloden, 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, pp. 33-56, 1998.
[12] G. Clarke and J. W. Wright, “Scheduling of vehicles from a central depot to a number of deliver points,” Operations Research, vol. 12, pp. 568-581, 1964.
[13] N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and Edward Teller, “The metropolis algorithm,” Nicholas Constantine, Phys., vol. 21, 1953.
[14] S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi, “Optimization simulated annealing,” Science, vol. 220, pp.671-680, 1983.
[15] F. Robust, C. F. Daganzo, and R. Souleyrette II, “Implementing Vehicle Routing Models,” Transportation Research, vol. 24B, pp. 263-286, 1990.
[16] 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.
[17] J. H. Holland, Adaptation in natural and artificial system, The University of Michigan Press, 1975.
[18] M. Dorigo. and L. M. Gambardella, “Ant colony system: A cooperative learning
approach to the travelling salesman problem.” IEEE Transactions on Evolutionary Computation, pp. 53-66, 1997.
[19] M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on System, Man, and Cybernetics, Part B, vol. 26, pp. 29-41, 1996.
[20] T. Stutzle and M. Dorigo, Ant colony optimization, MIT Press, 2004.
[21] B. Bullnheimer, R. F. Hartl, and Strauss, “Applying the ant system to the vehicle routing problem,” In Voss, S., Martello, S., Osman, I. H. and Roucairol, C. (Eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Kluwer, Boston, 1999.
[22] M. Dorigo, “Optimization, learning and natural algorithms,” Ph.D. Thesis, Politecnico di Milano, Italy, 1992.
[23] M. Dorigo and G. D. Caro, “Ant colony optimization: A new meta-heuristic,” Proceedings of the 1999 Congress on Evolutionary Computation, vol. 2, pp. 1470-1477, 1999.
[24] M. Gendreau, A. Hertz, and G. Laporte, “New insertion and post optimization procedures for the traveling salesman problem,” Operations Research 40, pp. 1086-1094, 1992.
[25] http://sales-training-2.info/Insertion+Mold+Christofides
[26] J. F. Cordeau, M. Gendreau, G. Laporte, and J. Y. Potvin, “A guide to vehicle routing heuristics,” J. Operational Research Soc., vol. 53, no. 5, pp. 512-522, 2002.
[27] H. R. Lourenco, O. Martin, and T. Stutzle, Iterated local search, Handbook of Meta-heuristics, F. Glover and G. Kochenberger (Eds.), Springer-Verlag, pp. 321-353, 2003.
[28] C. Blum and A. Roli, “Meta-heuristics in combinatorial optimization: Overview and conceptual comparison,” ACM Computing Surveys, vol. 35, no.3, pp. 268-308, 2003.
[29] D. H. Ackeley, G. E. Hinton, and T. J. Sejnowski, “A learning algorithm for Boltzmann machines,” Cognitive Science , pp. 145-170, 1985.
[30] McCarthy, J. Minsky, N. Rochoster, and C. E. Shannon, “A proposal for the Dartmouth summer search project on artificial intelligence,“ John McCathy, 1955.
[31] Marvin, L. Minsky, “Future of AI technology,” Toshiba Review 47, no. 7, 1992.
[32] E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm intelligence from natural to artifical systems, Oxford University Press, 1999.
[33] B. Bullnheimer, F. Richard and C. Strauss, “Apply the ant system to the vehicle routing problem,“ 2nd International Conference on Metaheuristics, Sophia- Antipolis, pp. 2-5, 1997.
[34] K. Doerner, M. Gronalt, R. F. Hartl, Marc R. C. Strauss and M. Stummer, “Savings Ant for the Vehicle Routing Problem,” Insistute of Management Science, pp. 12-15, 2002.
[35] B. Gillett and L. Miller, “A Heuristic Algorithm for the Vehicle Dispatch Problem,” Operations Research, vol. 22, pp. 340-349, 1974.
[36] P. Toth and D. Vigo, The Vehicl Routing Problem, Siam, pp.121-125, 2001.
[37] 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.
[38] B. Gillett and L. Miller, “A heuristic algorithm for the vehicle dispatch problem,” Operations Research, vol. 22, pp. 340-349, 1974.
[39] Barrie M. Baker and M. A. Ayechew, “A genetic algorithm for the vehicle routing problem,” Computers & Operations Research, vol. 30, pp. 787-800, 2003.
[40] B. Bullnheimer, R. F. Hartl, and C. Strauss, An improved ant system to the vehicle problem, In S. Vo , S. Martello, I. H. Osman and C. Roucairol (Eds.), Meta-Heuristic: Advances and Trends in Local Search Paradigms for Optimization, Kluwer, Boston, pp. 109-120, 1998.
[41] T. Stutzle, MAX-MIN Ant system for quadratic assignment problems, Technical report AIDA-94-4, FG Intellektik, FB Informatik, TU Darmstadt, Germany, 1997.
[42] H. Paessen, “The savings algorithm for the vehicle routing problem,” European Journal of Operational research, vol. 34, pp. 336-344, 1988.