Open Access Open Access  Restricted Access Subscription or Fee Access

EAS-DTSP: An Improved Ant System Model for Dynamic Traveling Salesman (DTSP) Problem

Nitesh M. Sureja, Dr. Ved Vyas Dwivedi, Dr. Sanjeev Kumar

Abstract


Ant Colony Optimization (ACO) is a novel and competitive optimization method for numerous combinatorial optimization problems. It is already applied to various optimization problems. Normally it proved best in terms of solution quality, accuracy and other parameters. This paper presents an Elitist Ant System (EAS) which uses tuning in pheromone update process to improve the performance of the basic Ant System (AS) approach. Dynamic Traveling Salesman Problem is solved in this research with the various pheromone update strategy for finding the improvements in the results. The results obtained are empirically compared with the results obtained with the basic pheromone update strategy of Ant System.

Keywords


Ant Colony Optimization, ElitistAnt System, Dynamic Traveling Salesman Problem (DTSP), Optimization.

Full Text:

PDF

References


M. Hao, Z. Sun, “Comparative Reaserch on Modern optimization Algorithms in solving the Traveling Salesman Problem using Scilab”.

M. M. Flood, “The Traveling Salesman Problem,” Operations Research, 1956.

Gerard Reinelt, “The Traveling Salesman: Computational Solutions for TSP Applications”.

David E. Goldberg,” Genetic Algorithms in Search, Optimization and Machine Learning”.

Emile Aarts, Jan Korst, and Wil Michiels,” Simulated Annealing”, chapter 7. Springer, 2005. Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques.

X. S. Yang, “Firefly algorithm for multimodal optimization”, in proceedings of the stochastic Algorithms. Foundations and Applications (SAGA 109) vol.5792 of Lecture notes in Computer Sciences Springer, Oct.2009.

X. S. Yang, (2010). “Firefly Algorithm Stochastic Test Functions and Design Optimization”, Int. J. Bio-Inspired Computation, vol.2, No. 2, pp.78-84, 2010.

J. Kennedy and R.C. Eberhart, “ Particle swarm optimization”, In IEEE International Conference on Neural Networks, Perth, Australia, 1995.

D. Karaboga, B. Basturk, “A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm”, Journal of Global Optimization 39 (2007) 459–471.

M. Dorigo, T. Stutzle, “Ant Colony optimization”, A Bradford book, MIT Press Cambridge, Massachucetts london, England (2004) .

D.Asmar ,A. Elshamli, S. Areibi, “A Comparative Assessment of ACO Algorithms Within a TSP Environment”, In DCDIS: 4th International Conference on Engineering Applications and Computational Algorithms, Guelph, Ontario, Canada, July 2005.

M. Dorigo, L. Gambardella, “Ant colony System: A Cooperstive learning Approach to the Traveling salesman problem”, IEEE Trans. Evol.Comp. 1 (1997): 53-66.

M. Dorigo, L. Gambardella, “Antcolonies for the Traveling salesman problem”, Biosystems 43 (1997): (73-81).

Y. Li, S. Gong, “Dynamic ant colony optimizationfor TSP”, Int J Adv ManufTechnol, Vol. 22, July 2003.

M. Dorigo, “Optimization, Learning and Natural Algorithms (in Italian)”, PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1992. 140 pages.

M. Dorigo, G Caro, “The ant colony optimization Metaheuristics-new ideas in optimization”, McGraw -Hill, London UK, pp. 11-32,1999.

A. Zhou, L. Kang, Z. Yan, “Solving Dynamic TSP with Evolutionary Approach in Real Time, in: Proceedings of the congress on Evolutionary computation”, Canberra, Australia, 8 – 12, December 2003, IEEE Press, 951 – 957,2003.

N. Sureja, B. Chawda, “Random Travelling Salesman Problem using SA”, International Journal of Emerging Technology and Advanced Engineering, Volume 2, Issue 4, April 2012.

Nitesh M Sureja, Bharat V Chawda, “Random Travelling Salesman Problem using Genetic Algorithms”, IFRSA’s International Journal Of Computing, Volume 2, Issue 2, April 2012.

Merz, P., 2000, “Memetic Algorithms for Combinatorial Optimization Problems: Fitness Landscapes and Effective Search Strategies”, PhD Thesis, University of Siegen,Germany.

Nitesh M. Sureja, Dr. Ved Vyas Dwivedi, Dr. Sanjeev Kumar, “MASA-DTSP: An Improved Model for Dynamic Traveling Salesman (DTSP) Problem”, CiiT International Journal of Artificial Intelligent Systems and Machine Learning, Vol 7, No 8 (2015).


Refbacks

  • There are currently no refbacks.