Sensitive Ants in Solving the Generalized Vehicle Routing Problem
Keywords:
ant-based models, optimization, sensitivity, complex problemsAbstract
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
R. Baldacci, E. Bartolini and G. Laporte, Some applications of the Generalized Vehicle Routing Problem, Le Cahiers du GERAD, G-2008-82, 2008.
M. Dorigo, C. Blum, Ant Colony Optimization Theory: A Survey, Theoretical Computer Science, 344, 2-3, pp. 243-278, 2005.
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
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
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
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
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
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
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.
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.
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
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.
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.
http://www.iwr.uni-heidelberg.de/groups/comopt/software/ TSPLIB95/vrp/
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
