Sensitive Ants in Solving the Generalized Vehicle Routing Problem

  • Camelia-M. Pintea G. Cosbuc N.College Romania, A. Iancu, 400083, Cluj-Napoca
  • Camelia Chira “Babes-Bolyai” University Romania, M. Kogalniceanu, 400084, Cluj-Napoca
  • Dan Dumitrescu “Babes-Bolyai” University Romania, M. Kogalniceanu, 400084, Cluj-Napoca

Abstract

The idea of sensitivity in ant colony systems has been exploited in hybrid ant-based models with promising results for many combinatorial optimization problems. Heterogeneity is induced in the ant population by endowing individual ants with a certain level of sensitivity to the pheromone trail. The variable pheromone sensitivity within the same population of ants can potentially intensify the search while in the same time inducing diversity for the exploration of the environment. The performance of sensitive ant models is investigated for solving the generalized vehicle routing problem. Numerical results and comparisons are discussed and analysed with a focus on emphasizing any particular aspects and potential benefits related to hybrid ant-based models.

References

[1] R. Baldacci, E. Bartolini and G. Laporte, Some applications of the Generalized Vehicle Routing Problem, Le Cahiers du GERAD, G-2008-82, 2008.

[2] M. Dorigo, C. Blum, Ant Colony Optimization Theory: A Survey, Theoretical Computer Science, 344, 2-3, pp. 243-278, 2005.

[3] M. Dorigo, L. M. Gambardella. Ant Colony System: A cooperative learning approach to the Traveling Salesman Problem. IEEE Trans. Evol. Comp., 1, pp.53-66, 1997.
http://dx.doi.org/10.1109/4235.585892

[4] D. Feillet, P. Dejax and M. Gendreau, Traveling salesman problems with profits, Transportation Science, Vol. 39, pp. 188-205, 2005.
http://dx.doi.org/10.1287/trsc.1030.0079

[5] M. Fischetti, J.J. Salazar, P. Toth. A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research, 45:378-394, 1997.
http://dx.doi.org/10.1287/opre.45.3.378

[6] G. Ghiani, G. Improta. An efficient transformation of the generalized vehicle routing problem. European Journal of Operational Research 122, 11-17, 2000.
http://dx.doi.org/10.1016/S0377-2217(99)00073-9

[7] G. Laporte, S. Chapleau, P.E. Landry and H. Mercure, An algorithm for the design of mail box collection routes in urban areas, Transportation Research B, Vol. 23, pp. 271-280, 1989.
http://dx.doi.org/10.1016/0191-2615(89)90029-5

[8] G. Laporte, A. Asef-Vaziri and C. Sriskandarajah, Some applications of the generalized traveling salesman problem, Journal of Operational Research Society, Vol. 47, pp. 1461- 1467, 1996.
http://dx.doi.org/10.1057/jors.1996.190

[9] C.M. Pintea, D. Dumitrescu and P.C. Pop,Combining heuristics and modifying local information to guide ant-based search, Carpathian Journal of Mathematics, Vol. 24, No. 1, pp. 94-103, 2008.

[10] C-M. Pintea, C. Chira, D.Dumitrescu, Sensitive Ants: Inducing Diversity in the Colony, Nature Inspired Cooperative Strategies for Optimization NICSO 2008, Studies in Computational Intelligence, 236 (Krasnogor, N.; Meli�n-Batista, B.; Moreno-P�rez, J.A.; Moreno-Vega, J.M.; Pelta, D.; Eds.), Springer-Verlag, 15-24, 2009.

[11] P.C.Pop, C.M.Pintea, I.Zelina, D.Dumitrescu. Solving the Generalized Vehicle Routing Problem with an ACS-based Algorithm, American Institute of Physics (AIP) Springer, Conference Proceedings: BICS 2008, Vol.1117, No.1, 157–162, 2009.
http://dx.doi.org/10.1063/1.3130618

[12] P.C. Pop, Efficient Transformations of the Generalized Combinatorial Optimization Problems into Classical Variants, Proceedings of the 9-th Balkan Conference on Operational Research, Constanta, Romania, 2-6 September 2009.

[13] P.C. Pop, A survey of different integer programming formulations of the generalized minimum spanning tree problem, Carpathian Journal of Mathematics, Vol. 25, No. 1, pp. 104-118, 2009.

[14] http://www.iwr.uni-heidelberg.de/groups/comopt/software/ TSPLIB95/vrp/
Published
2011-12-01
How to Cite
PINTEA, Camelia-M.; CHIRA, Camelia; DUMITRESCU, Dan. Sensitive Ants in Solving the Generalized Vehicle Routing Problem. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 6, n. 4, p. 731-738, dec. 2011. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/2098>. Date accessed: 10 aug. 2020. doi: https://doi.org/10.15837/ijccc.2011.4.2098.

Keywords

ant-based models, optimization, sensitivity, complex problems