Solving the open vehicle routing problem by a hybrid ant colony optimization
Keywords:
Ant colony optimization, candidate list, local search techniques, np-hard Problems, open vehicle routing problemAbstract
The open vehicle routing problem (OVRP) is a variant of vehicle routing problem (VRP) in which the vehicles are not required to return to the depot after completing a service. Since this problem belongs to NP-hard Problems, many metaheuristic approaches like ant colony optimization (ACO) have been used to solve it in recent years. The ACO has some shortcomings like its slow computing speed and local-convergence. Therefore, in this paper a hybrid ant colony optimization called HACO is proposed in which a new state transition rule, an efficient candidate list, several effective local search techniques and a new pheromone updating rule are used in order to achieve better solutions. Experimentation shows that the algorithm is successful in finding solutions within almost 3% of known optimal solutions on classical thirty one benchmark instances. Additionally, it shows that the proposed algorithm HACO finds twenty one best solutions of classical instances and is competitive with eight existing algorithms for solving OVRP. Furthermore, the size of the candidate lists used within the algorithm is a major factor in finding improved solutions and the computational times for the algorithm compare satisfactorily with other solution methods.
References
Back, T., Hammel, U. Schwefel, H. P. 1997. Evolutionary computation: comments on the history and current state. IEEE Trans Evolution Computation, 1(1): 3-17.
Bodin, L., Golden, B., Assad, A. Ball, M. 1983. Routing and scheduling of vehicles and crews: The state of the art. Computers and Operations Research, 10 (2): 63-211.
Brandقo, J. 2004. A tabu search algorithm for the open vehicle routing problem. European Journal of Operational Research, 157(3): 552-564.
Bullnheimer, B., Hartl, R. F. Strauss, C. 1997. A new rank based version of the ant system - A computational study. Central European Journal for Operations Research and Economics, 7(1), 25-38.
Bullnheimer. B., Hartl, R. F. Strauss, C. 1998. Applying the ant system to the vehicle routing problem. In: Voss S, Martello S, Osman IH, Roucairol C, editors. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Boston: Kluwer.
Bullnheimer. B., Hartl, R. F. Strauss, C. 1999. An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research, 89: 319-328.
Christofides, N., Mingozzi, A. Toth, P. 1979. The vehicle routing problem. In: Christofides N, Mingozzi A, Toth P, Sandi L, editors. Combinatorial optimization. Chichester: Wiley; 315-338.
Dorigo, M. 1992. Optimization, Learning and Natural Algorithms (in Italian). PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 140.
Fisher, M. L. Jaikumar, R. 1978. A decomposition algorithm for large-scale vehicle routing, Working Paper 78-11-05, Department of Decision Sciences, University of Pennsylvania.
Fleszar, K., Osman, I. H. Hindi, K. S. 2009. A variable neighbourhood search algorithm for the open vehicle routing problem. European Journal of Operational Research, 195: 803-809.
Fu, Z., Eglese, R. Li, L.Y. O. 2005. A new tabu search heuristic for the open vehicle routing problem. Journal of the Operational Research Society, 56: 267-274.
Fu, Z., Eglese, R. Li, L. Y. O. 2006. Corrigendum: A new tabu search heuristic for the open vehicle routing problem. Journal of the Operational Research Society, 57: 1018.
Letchford, A. N., Lysgaard, J. Eglese, R. W. 2007. A Branch-and-cut Algorithm for the Capacitated Open Vehicle Routing Problem. Journal of the Operational Research Society, 58: 1642-1651.
Levy, L. 2005. Private communication. RouteSmart Technologies, Inc.
Li, F., Golden, B. Wasil, E. 2007. The open vehicle routing problem: Algorithms, large-scale test problems, and computational results. Computers and Operations Research 34: 2918-2930.
MirHassani, S. A. Abolghasemi, N. 2011. A Particle Swarm Optimization Algorithm for Open Vehicle Routing Problem. Expert Systems with Applications, 38(9): 11547-11551.
Pisinger, D. Ropke, S. A. 2007. General heuristic for vehicle routing problems. Computers and Operations Research, 34: 2403- 2435.
Repoussis, P. P., Tarantilis, C. D., Brقysy, O. Ioannou, G. 2010. A Hybrid Evolution Strategy for the Open Vehicle Routing Problem. Computers Operations Research, 37 (3): 443-455.
Saadati Eskandari, Z. Yousefikhoshbakht, M. 2012. Solving the Vehicle Routing Problem by using an Effective Reactive Bone Route Algorithm. Transportation Research Journal, 1: 51-67
Salari, M., Toth, P. Tramontani, A. 2010. An ILP improvement procedure for the open vehicle routing problem. Computers and Operations Research, 12 (2): 2106-2102.
Sariklis, D. Powell, S. 2000. A heuristic method for the open vehicle routing problem. Journal of the Operational Research Society, 51: 564-573.
Syslo, M., Deo, N. Kowaklik, J. 1983. Discrete Optimization Algorithms with Pascal Programs. Prentice Hall, Inc.
Schrage, L. 1981. Formulation and structure of more complex/realistic routing and scheduling problems. Networks, 11: 229-232.
Tarantilis, C. D., Zachariadis, E. Kiranoudis, C. 2008. A guided Tabu search for the heterogeneous vehicle routing problem. Journal of the Operational Research Society, 59, 1659-1673.
Tarantilis, C. D., Ioannou, G., Kiranoudis, C. T. Prastacos, G. P. 2005. Solving the open vehicle routing problem via a single parameter metaheuristic algorithm. Journal of the Operational Research Society, 56: 588-596.
Tarantilis, C. D., Diakoulaki, D. Kiranoudis, C. T. 2004a. Combination of geographical information system and efficient routing algorithms for real life distribution operations. European Journal of the Operational Research, 52: 437-53.
Tarantilis, C. D., Ioannou, G., Kiranoudis, C. T. Prastacos, G. P. 2004b. A threshold accepting approach to the open vehicle routing problem. RAIRO Operations Research, 38: 345-360.
Yousefikhoshbakht, M. Khorram, E. 2012. Solving the Vehicle Routing Problem by a Hybrid Meta-Heuristic Algorithm. Journal of Industrial Engineering International, 8(11): 1-9.
Yousefikhoshbakht, M. Sedighpour, M. 2012. A Combination of Sweep Algorithm and Elite Ant Colony Optimization for Solving the Multiple Traveling Salesman Problem. Proceedings of the Romanian Academy A, 13(4): 295-302.
Zachariadis, E. E. Kiranoudis, C. T. 2010. An Open Vehicle Routing Problem Metaheuristic for Examining Wide Solution Neighborhoods. Computers Operations Research, 37(4): 712-723.
