An Efficient Solution for the VRP by Using a Hybrid Elite Ant System

Authors

  • Majid Yousefikhoshbakht
  • Farzad Didehvar
  • Farhad Rahmati

Abstract

The vehicle routing problem (VRP) is a well-known NP-Hard problem
in operation research which has drawn enormous interest from many researchers during
the last decades because of its vital role in planning of distribution systems and
logistics. This article presents a modified version of the elite ant system (EAS) algorithm
called HEAS for solving the VRP. The new version mixed with insert and swap
algorithms utilizes an effective criterion for escaping from the local optimum points.
In contrast to the classical EAS, the proposed algorithm uses only a global updating
which will increase pheromone on the edges of the best (i.e. the shortest) route and
will at the same time decrease the amount of pheromone on the edges of the worst
(i.e. the longest) route. The proposed algorithm was tested using fourteen instances
available from the literature and their results were compared with other well-known
meta-heuristic algorithms. Results show that the suggested approach is quite effective
as it provides solutions which are competitive with the best known algorithms in the
literature.

References

Yousefikhoshbakhtm, M. and Khorram, E. (2012). Solving the Vehicle Routing Problem by a Hybrid Meta-Heuristic Algorithm, Journal of Industrial Engineering International, 8(12):1-9.

Yousefikhoshbakht, M., Didehvar, F. and Rahmati, F. (2014). A Combination of Modified Tabu Search and Elite Ant System to Solve the Vehicle Routing Problem with Simultaneous Pickup and Delivery, Journal of Industrial and Production Engineering, 31(2): 65-75. http://dx.doi.org/10.1080/21681015.2014.893928

Hong, L. (2012). An improved LNS algorithm for real-time vehicle routing problem with time windows, Computers and Operations Research, 39(2):151-163. http://dx.doi.org/10.1016/j.cor.2011.03.006

Yousefikhoshbakht, M., F. Didehvar, and F. Rahmati, (2013). Solving the heterogeneous fixed fleet open vehicle routing problem by a combined metaheuristic algorithm, International Journal of Production Research http://dx.doi.org/10.1080/00207543.2013.855337

Toth, P. and Vigo, D. (1997). An exact algorithm for the vehicle routing problem with backhauls, Transportation Science, 31:372-385. http://dx.doi.org/10.1287/trsc.31.4.372

Pop P.C., Sitar C.P., Zelina I., Lupse V. and Chira C. (2011)., Heuristic Algorithms for Solving the Generalized Vehicle Routing Problem, International Journal of Computers Communications & Control, ISSN 1841-9836, 6(1): 158-165.

Valle, C. A., Martinez, L. C. and Cunha, A. S., Mateus, G. R. (2011). Heuristic and exact algorithms for a min-max selective vehicle routing problem, Computers and Operations Research, 38(7):1054-1065. http://dx.doi.org/10.1016/j.cor.2010.10.010

Brad, J., Kontoravdis, G. and Yu, G. (2002). A Branch-and-Cut Procedure for the Vehicle Routing Problem with Time Windows. Transportation Science, 36(2):250-269. http://dx.doi.org/10.1287/trsc.36.2.250.565

Clarke, G. and Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12: 568-581. http://dx.doi.org/10.1287/opre.12.4.568

Gillett, B. E. and Miller, L. R. (1974). A heuristic algorithm for the vehicle dispatch problem. Operations Research, 22: 340-349. http://dx.doi.org/10.1287/opre.22.2.340

Osman, I. (1993). Metastrategy simulated annealing and Tabu search algorithms for the vehicle routing problem, Operations Research, 41: 421-451.

Baker, B., and Ayechew, M. (2003). A genetic algorithm for the vehicle routing problem, Computers and Operations Research, 30: 787-800. http://dx.doi.org/10.1016/S0305-0548(02)00051-5

Hirota, K., Dong, F. and Chen, K. (2006), A Computational Intelligence Approach to VRSDP (Vehicle Routing, Scheduling, and Dispatching Problems), International Journal of Computers Communications & Control, ISSN 1841-9836, Suppl. issue, 1(S): 53-60,

Zhang, X. and Tang, L. (2009). A new hybrid ant colony optimization algorithm for the vehicle routing problem, Pattern Recognition Letters, 30(152): 848-855. http://dx.doi.org/10.1016/j.patrec.2008.06.001

Negulescu S.C., Kifor C.V. and Oprean C. (2008). Ant Colony Solving Multiple Constraints Problem: Vehicle Route Allocation, International Journal of Computers Communications & Control, ISSN 1841-9836, 3(4):366-373.

Ai, J., Kachitvichyanukul, V. (2009). Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem, Computers and Industrial Engineering, 56:380-387. http://dx.doi.org/10.1016/j.cie.2008.06.012

Pintea C.-M., Chira C., Dumitrescu D. and Pop P.C. (2011). Sensitive Ants in Solving the Generalized Vehicle Routing Problem, International Journal of Computers Communications & Control, ISSN 1841-9836, 6(4):734-741.

Yousefikhoshbakht, M., Didehvar, F. and Rahmati, F. (2013). Modification of the Ant Colony Optimization for Solving the Multiple Traveling Salesman Problem, Romanian Journal of Information Science and Technology, 16(1):65-80.

Yousefikhoshbakht, M. and 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.

Marinakis, Y. and Marinaki, M. (2010). A hybrid genetic-particle swarm optimization algorithm for the vehicle routing problem, Expert Systems with Applications, 37(33):1146-1455.

Published

2014-04-04

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.