An Improved Ant Colony Optimization for the Vehicle Routing Problem in Logistics Distribution

Abstract:

The routing of a fleet of vehicles to service a set of customers is important in logistic distribution systems. The main objective of Vehicle routing problem (VRP) is to minimize the total required fleet size for serving all customers. Secondary objectives are to minimize the total distance traveled or to minimize the total route duration of all vehicles. In this paper, we present a hybrid ant colony System, named PACS, coupled with a pareto local search (PLS) algorithm and apply to the VRP and its variant, the VRP with Time Windows (VRPTW). The algorithm only chooses partial customers randomly to compute the transition probability and PLS can help to escape local optimum. Experiments on various aspects of the algorithm and computational results for some benchmark problems are reported. We compare our approach with some classic, powerful meta-heuristics and show that the proposed approach can obtain the better quality of the solutions.

• Periodical: Advanced Materials Research (Volumes 121-122)
• Pages: 1006-1011
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.121-122.1006
• Online since: June 2010
• Authors: Cheng Ming Qi
• Keywords: Ant Colony System, Pareto Local Search, Vehicle Routing Problem (VRP)

References

[1] A. Colorni, M. Dorigo and V. Mariiezzo. Distributed Optimization by Ant Colonies, in: Proc. Eearop. Conf. Artificial Life, ed. F. Varela and P. Bourgine, (Elsevier, Amsterdam, 1991).

[2] M. Dorigo and L.M. Gambardella. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1(1): 53-66, (1997).

DOI: 10.1109/4235.585892

[3] T. Stützle and H.H. Hoos. The MAX-MIN Ant System and Local Search for the Traveling Salesman Problem. In T. Saeck, Z. Michalewicz, and N. Yao, editors, Proceedings of the IEEE International Conference on Evolution anj Computation (ICEC'97'), pages 309-314, (1997).

DOI: 10.1109/icec.1997.592327

[4] L.M. Gambardella, M. Dorigo. Solving Symmetric and Asymmetric TSPs by Ant Colonies, Proceedings of the IEEE Conference on Evolutionary Computation, ICEC96, IEEE Press, 1996, 622-627.

DOI: 10.1109/icec.1996.542672

[5] A. C. Zecchin, H. R. Maier, A. R. Simpson, M. Leonard, & J. B. Nixon. Ant colony optimization applied to water distribution system design: comparative study of five algorithms. Journal of Water Resources Planning and Management, 133(1), 87-92, (2007).

DOI: 10.1061/(asce)0733-9496(2007)133:1(87)

[6] Y. Li, & A. B. Chan Hilton. Optimal groundwater monitoring design using an ant colony optimization paradigm. Environmental Modelling and Software, 22(1), 110-116, (2007).

DOI: 10.1016/j.envsoft.2006.05.023

[7] Y. Aksoy, & A. Derbez. Software survey: supply chain management. OR/MS Today, 30(3), 1-13, (2003).

[8] B. Bullnheimer, R. F. Hartl, & C. Strauss. Applying the Ant System to the vehicle routing problem. In S. Voss., S. Martello, I. H. Osman, & C. Roucairol (Eds. ), Meta-heuristics: Advances and trends in local search paradigms for optimization (pp. 109C120), 1998. Boston: Kluwer.

DOI: 10.1007/978-1-4615-5775-3_20

[9] L.M. 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. D. Corne et al. editors. Pages 63-76, (1999).

[10] A.E. Rizzoli, R. Montemanni, E. Lucibello, & L.M. Gambardella. Ant colony optimization for real-world vehicle routing problems. From theory to applications. Swarm Intelligence, 1(2): 135-151, (2007).

DOI: 10.1007/s11721-007-0005-x

[11] D. Angus, & C. Woodward. Multiple objective ant colony optimization. Swarm Intelligence 3(1) 69-85, (2009).

DOI: 10.1007/s11721-008-0022-4

[12] R. Montemanni, L. Gambardella, A. Rizzoli, and A. Donati. A new algorithm for a dynamic vehicle routing problem based on ant colony system. In Second International Workshop on Freight Transportation and Logistics, (2003).

DOI: 10.1007/s10878-005-4922-6

[13] X. Hu, J. Zhang & Y. Li. Flexible protein folding by ant colony optimization. In: Computational Intelligence in Biomedicine and Bioinformatics: Current Trends and Applications. Springer-Verlag, New York, pp.317-336, (2008).

DOI: 10.1007/978-3-540-70778-3_13

[14] M. Dorigo, V. Maniezzo and A. Colorni. Ant System: Optimization by a Colony of Cooperating Agents, IEEE Trans. Sys., Man, Cybernetics 26(1996)29.

DOI: 10.1109/3477.484436

[15] L. Paquete and T. Stützle. A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices (2004).

DOI: 10.1016/j.ejor.2004.08.024

[16] B. Bullnheimer, R. F. Hartl, & C. Strauss. An improved Ant System algorithm for the vehicle routing problem. (Tech. Rep. POM-10/97). Vienna, Austria: University of Vienna, Institute of Management Science, (1997).

[17] Gendreau, M., Hertz, A. and Laporte, G.: A tabu search heuristic for the vehicle routing problem. Management Science 40: 1276-1290, (1994).

DOI: 10.1287/mnsc.40.10.1276

[18] L.M. 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. D. Corne et al. editors. Pages 63-76, (1999).

[19] N. Christofides, A. Mingozzi and P. Toth: The vehicle routing problem. Combinatorial Optimization. Wiley, Chicester, (1979).