Email this article 
Open Access
Subscription or Fee Access
MASA-DTSP: An Improved Model for Dynamic Traveling Salesman (DTSP) Problem
Abstract
The Memetic algorithms (MA) are computational models inspired by the Cultural Revolution. Robustness, scalability and simplicity are the advantages of Memetic algorithms. By looking at this strength of MA, they are very much suitable for solving some combinatorial optimization problems which falls in the category of NP-hard problems. In this paper, we propose MA based optimization model for Dynamic Traveling Salesman Problem (DTSP), to achieve overall higher system performance and better throughput.
During implementation, results are obtained with number of randomly generated Traveling Salesman Problem instances, measured in terms of required time, quality and path length. It has been observed that the proposed model works well in terms of quality and path length. As it uses Simulated Annealing, it is found little bit less effective in terms of time.
Keywords
References
M. Hao, Z. Sun, “Comparative Reaserch on Modern optimization Algorithms in solving the Traveling Salesman Problem using Scilab”.
David E. Goldberg, “ Genetic Algorithms in Search, Optimization and Machine Learning”.
N Sureja, B Chawda, “Random Travelling Salesman Problem using Genetic Algorithms”, IFRSA’s International Journal Of Computing, Volume 2, Issue 2, April 2012.
M. Boyandi, M. Azghadi, “Population-Based Optimization Algorithms for Solving the Traveling Salesman Problem”.
M. Dorigo, G Caro, The antcolony optimization Metaheuristics, new ideas in optimization, McGraw Hill, 1999.
J. Kennedy and R.C. Eberhart, “ Particle swarm optimization”, In IEEE International Conference on Neural Networks, Perth, Australia, 1995.
J. Kennedy and R. Eberhart. “A discrete binary version of the particle swarm algorithm”. In Proceedings of the Conference on Systems, Man and Cybernetics, Piscataway, New Jersey, pages 4104–4109. 1997.
Emile Aarts, Jan Korst, and Wil Michiels. “Simulated Annealing”, chapter 7, Springer, 2005. Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques.
Ma ´ndziuk J, Macukow B, (1992) A Neural Network Designed to Solve The N-Queens Problem. Biol. Cybern. 66, 375-379.
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.
Gerard Reinelt. “The Traveling Salesman: Computational Solutions for TSP Applications”.
M. M. Flood, “The Traveling Salesman Problem,” Operations Research, 1956.
E. Elbeltagi, T. Hegazy, D. Grierson, “ Comparison among five evolutionary-based optimization algorithms”.
P. Moscato, “ Memetic algorithms: A short introduction. In D. Corne, M. Dorigo, and F. Glover, editors,New Ideas in Optimization, pages 219{234. McGraw-Hill, Maidenhead, Berkshire, England, UK, 1999.
P. Moscato and C. Cotta. “ A gentle intro duction to memetic algorithms”. In F. Glover and G. Ko chen- erger, editors, Handbook of Metaheuristics, pages 105{144. Kluwer Academic Publishers, Boston MA, 2003.
Natalio Krasnogor and Jim Smith “A Tutorial for Competent Memetic Algorithms: Model, Taxonomy and Design Issues”, IEEE Transactions on Evolutionary Computation, Vol.9 (5), 2005, 474-488.
S. Sumathi, T. Hamsapriya, P. Surekha, “ Evolutionary Intelligence”.
David Bookstaber, “Simulated Annealing for Traveling Salesman Problem”, Spring, 1997.
N. Sureja, B. Chawda, “Random Travelling Salesman Problem using SA,” International Journal of Emerging Technology and Advanced Engineering, Volume 2, Issue 4, April 2012.
A. Kulkarni, P. Kamble, “Memetic Algorithms – A PowerPoint Presentation ” ,Department of CSE, IIT Bombay, 2008.
Merz, P., “2000, Memetic Algorithms for Combinatorial Optimization Problems: Fitness Landscapes and Effective Search Strategies”, PhD Thesis, University of Siegen,Germany .
Refbacks
- There are currently no refbacks.