CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

New Approach for Solving Dynamic Traveling Salesman Problem with Hybrid Genetic Algorithms and Ant Colony Optimization

by Farhad Soleimanian Gharehchopogh, Isa Maleki, Masoum Farahmandian
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 53 - Number 1
Year of Publication: 2012
Authors: Farhad Soleimanian Gharehchopogh, Isa Maleki, Masoum Farahmandian
10.5120/8388-1997

Farhad Soleimanian Gharehchopogh, Isa Maleki, Masoum Farahmandian . New Approach for Solving Dynamic Traveling Salesman Problem with Hybrid Genetic Algorithms and Ant Colony Optimization. International Journal of Computer Applications. 53, 1 ( September 2012), 39-44. DOI=10.5120/8388-1997

@article{ 10.5120/8388-1997,
author = { Farhad Soleimanian Gharehchopogh, Isa Maleki, Masoum Farahmandian },
title = { New Approach for Solving Dynamic Traveling Salesman Problem with Hybrid Genetic Algorithms and Ant Colony Optimization },
journal = { International Journal of Computer Applications },
issue_date = { September 2012 },
volume = { 53 },
number = { 1 },
month = { September },
year = { 2012 },
issn = { 0975-8887 },
pages = { 39-44 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume53/number1/8388-1997/ },
doi = { 10.5120/8388-1997 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:53:02.296572+05:30
%A Farhad Soleimanian Gharehchopogh
%A Isa Maleki
%A Masoum Farahmandian
%T New Approach for Solving Dynamic Traveling Salesman Problem with Hybrid Genetic Algorithms and Ant Colony Optimization
%J International Journal of Computer Applications
%@ 0975-8887
%V 53
%N 1
%P 39-44
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Dynamic travelling salesman problem (DTSP) is one of the optimization issues which it is not solvable with classical methods. To solve this problem, various solutions in the literature can be seen that each has advantages and disadvantages. Genetic Algorithm (GA) and Ant Colony Optimization (ACO) have been good to solve the DTSP. In this paper, we highlight a new algorithm by combining genetic and ACO which gives us a better solution for DTSP. In hybrid algorithm, suitability of algorithm and travelled distance for DTSP has been considered. Obtained results suggest that Hybrid algorithm does not establish easily in the local optimum and possesses a good speed in convergence for comprehensive answer.

References
  1. Lo, C. C. , & Hus, C. C, "Annealing framework with learning memory", IEEE Transactions on System, Man, Cybernetics - Part A, vol. 28, no. 5, pp. 1–13, 1998.
  2. Dorigo, M. , & Gambardella, L. M, "Ant colony system: a cooperative learning approach to the traveling salesman problem", IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53–66, 1997.
  3. Tsai, H. K. , Yang, J. M. , Tsai, Y. F. , & Kao, C. Y, "Heterogeneous selection genetic algorithms for traveling salesman problems", Engineering Optimization, vol. 35, no. 3, pp. 297–311, 2003.
  4. Albayrak, M. , & Allahverdi, N, "Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic Algorithms", Expert Systems with Applications, vol. 38, no. 3, pp. 1313–1320, 2011.
  5. Leung, K. S. , Jin, H. D. , &Xu, Z. B, "An expanding self-organizing neural network for the traveling salesman problem", Neuro computing, vol. 62, pp. 267–292, 2004.
  6. Masutti, T. A. S. , & de Castro, L. N, "A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem", Information Sciences, vol. 179, no. 10, pp. 1454–1468, 2009.
  7. M. Dorigo, V. Maniezzo, A. Colorni, "Ant system: optimization by a colony of cooperating agents", IEEE Trans. on Systems, Man and Cybernetics, Part B, Vol. 26, No. 1, pp. 29-41, 1996.
  8. M. Dorigo, L. M. Gambardella,"Ant colony system: a cooperative learning approach to the traveling salesman problem", IEEE Trans on Evolutionary Computation, Vol. 1, No. 1, pp. 53-66, 1997.
  9. Goldberg, D. E, Genetic Algorithms in Search, Optimization and Machine Learning, Reading, MA: Addison-Wesley, 1989.
  10. Guntsch, M. , Middendorf, M,"A population based approach for ACO". In: Cagnoni, S. , Gottlieb, J. , Hart, E. , Middendorf, M. , Raidl, G. R. (eds. ) EvoWorkshops 2002. LNCS, vol. 2279, pp. 72–81. Springer, Heidelberg (2002).
  11. Huang, Z. , Hu, X. , Chen, S,"Dynamic traveling salesman problem based on evolutionaycompution". In: Proc. of the 2001 IEEE Congr. onEvol. Comput. , pp. 1283–1288 (2001).
  12. M. b, Fogel. , "The genetic algorithm for TSP", IEEE Transaction on systems, 16:1-13, 1986.
  13. Whitely D. , ''A Genetic Algorithm Tutorial'', Journal of Statistics and Computing Vol. 4,1994, pp. 65-85.
  14. Chatterjee, S. , Carrera, C. , & Lynch, L. A, "Genetic algorithms and traveling salesman problems", European Journal of Operational Research, vol. 93, no. 3, pp. 490-510, 1996.
  15. Vorac J. , Vondrak I. , Vlcek K. , ''School Timetabling Using Genetic Algorithm'', Technical Report, VSB-Technical University of Ostrava, Czech Republic, 2002.
  16. M. Dorigo, G. Di Caro, and L. M. Gambardella. " Ant algorithms for discrete optimization. "Artificial Life, 5(2):137–172, 1999.
  17. Dorigo, M. , Birattari, M. , &Stutzle, T,"Ant colony optimization: artificial ants as a computational intelligence technique", IEEE Computational Intelligence Magazine, vol. 1, no. 4, pp. 28–39, 2006.
  18. R. Schoonderwoerd, O. Holland, and J. Bruten, "Ant-like agent for load balancing in telecommunications network", in Proc. of the 1stInt. Conf. on Autonomous Agents, pp. 209-216, 1997.
  19. G. D. Caro and M. Dorigo, "Mobile agent for adaptive routing," in Proc. 31st Hawaii Int. Conf. on System Science, 1998.
  20. G. D. Caro and M. Dorigo, "AntNet: distributed stigmergetic control for communications networks," J. of Artificial Intelligence Research,vol. 9, pp. 317-365, 1998.
  21. Psaraftis, H. N,"Dynamic vehicle routing problems". In: Golden, B. L. , Assad, A. A. (eds. ) Vehicle Routing: Methods and Studies, pp. 223–248. Elsevier, Amsterdam (1988).
  22. Li, C. , Yang, M. , Kang, L. : "A New Approach to Solving Dynamic Traveling Salesman Problems". In: Wang, T. -D. , Li, X. , Chen, S. -H. , Wang, X. , Abbass, H. , Iba, H. , Chen, G. , Yao, X. (eds. ) SEAL 2006. LNCS, vol. 4247, pp. 236–243. Springer, Heidelberg (2006)
  23. Michael Guntsch, Martin Middendorf, and HartmutSchmeck. "An ant colony optimization approach to dynamic TSP. In Lee Spector et al. , editor, Proceedings of the Genetic and Evolutionary Computation", Conference (GECCO-2001), pages 860–867, San Francisco, California, USA, 7-11 July 2001. Morgan Kaufmann.
  24. Ray, S. S. , Pal, S. K. , Bandyopadhyay, S. , "Genetic Operators For Combinatorial Optimization In TSP And Microarray Gene Ordering" , Springer, 2007
  25. S. N. Sze, "Study on Genetic Algorithms and Heuristic Method for Solving Traveling Salesman Problem," M. S. dissertation, Faculty of Science, UniversitiTeknologi Malaysia, Johor, Malaysia, 2004.
  26. Goldberg, D. E. , and R. Lingle. "Alleles, Loci, and the Traveling Salesman Problem. " Proceedings of the First International Conference on Genetic Algorithms and Their Application, edited by Grefenstette J. , Lawrence Erlbaum Associates, illsdale, NJ,1985, pp. 154-159.
  27. M. Bonyadi, M. Azghadi and H. Shah-Hosseini, "Population based optimization algorithms for solving the Travelling Salesman Problem", ITECH publications, ISBN 978-953-7619-10-7, pp: 1-34, 2008.
Index Terms

Computer Science
Information Sciences

Keywords

DTSP Optimization GA ACO Hybrid algorithm

Powered by PhDFocusTM