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

  • Majid Yousefikhoshbakht
  • Farzad Didehvar
  • Farhad Rahmati

Abstract

The vehicle routing problem (VRP) is a well-known NP-Hard problemin operation research which has drawn enormous interest from many researchers duringthe last decades because of its vital role in planning of distribution systems andlogistics. This article presents a modified version of the elite ant system (EAS) algorithmcalled HEAS for solving the VRP. The new version mixed with insert and swapalgorithms utilizes an effective criterion for escaping from the local optimum points.In contrast to the classical EAS, the proposed algorithm uses only a global updatingwhich will increase pheromone on the edges of the best (i.e. the shortest) route andwill 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 instancesavailable from the literature and their results were compared with other well-knownmeta-heuristic algorithms. Results show that the suggested approach is quite effectiveas it provides solutions which are competitive with the best known algorithms in theliterature.

References

[1] 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.

[2] 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


[3] 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



[4] 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


[5] 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


[6] 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.

[7] 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


[8] 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


[9] 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


[10] 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


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

[12] 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


[13] 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,

[14] 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


[15] 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.

[16] 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


[17] 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.

[18] 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.

[19] 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.

[20] 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
How to Cite
YOUSEFIKHOSHBAKHT, Majid; DIDEHVAR, Farzad; RAHMATI, Farhad. An Efficient Solution for the VRP by Using a Hybrid Elite Ant System. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 9, n. 3, p. 340-347, apr. 2014. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/161>. Date accessed: 16 july 2020. doi: https://doi.org/10.15837/ijccc.2014.3.161.