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

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Towards Solving Travelling Salesperson Problem using Hybrid of Genetic Algorithm and Lin-Kernighan Algorithm: A Comparative Evaluation with Neural Network Model

by Samuel A. Oluwadare, Bosede A. Ogunsanmi, John C. Nwaiwu
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 179 - Number 7
Year of Publication: 2017
Authors: Samuel A. Oluwadare, Bosede A. Ogunsanmi, John C. Nwaiwu
10.5120/ijca2017915953

Samuel A. Oluwadare, Bosede A. Ogunsanmi, John C. Nwaiwu . Towards Solving Travelling Salesperson Problem using Hybrid of Genetic Algorithm and Lin-Kernighan Algorithm: A Comparative Evaluation with Neural Network Model. International Journal of Computer Applications. 179, 7 ( Dec 2017), 11-19. DOI=10.5120/ijca2017915953

@article{ 10.5120/ijca2017915953,
author = { Samuel A. Oluwadare, Bosede A. Ogunsanmi, John C. Nwaiwu },
title = { Towards Solving Travelling Salesperson Problem using Hybrid of Genetic Algorithm and Lin-Kernighan Algorithm: A Comparative Evaluation with Neural Network Model },
journal = { International Journal of Computer Applications },
issue_date = { Dec 2017 },
volume = { 179 },
number = { 7 },
month = { Dec },
year = { 2017 },
issn = { 0975-8887 },
pages = { 11-19 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume179/number7/28747-2017915953/ },
doi = { 10.5120/ijca2017915953 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T00:54:41.913652+05:30
%A Samuel A. Oluwadare
%A Bosede A. Ogunsanmi
%A John C. Nwaiwu
%T Towards Solving Travelling Salesperson Problem using Hybrid of Genetic Algorithm and Lin-Kernighan Algorithm: A Comparative Evaluation with Neural Network Model
%J International Journal of Computer Applications
%@ 0975-8887
%V 179
%N 7
%P 11-19
%D 2017
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Travelling salesperson problem involves the sales person who intends to find the minimum or shortest round trip that passes through a finite set of cities, exactly once at minimum cost. This problem belongs to the class of optimization problems which is described as non-deterministic polynomial hard, that is, it cannot be solved in exact polynomial time. Several approaches have been employed in solving the problem, but empirical results has shown that these approaches needs more optimization in terms of run time and quality of getting the optimum solution. Genetic algorithm combined with another local search algorithm shows more efficient result could be obtained. In this paper, hybridization of genetic algorithm with a local search algorithm called Lin-Kernighan algorithm is employed to provide efficient solution. A case study of finding the optimal solution for a tour of state capitals in Southern Nigeria is carried out. The model is implemented on Intel Celeron 2GHz, 1GB RAM machine with JAVA programming language and Wamp sever. The performance of the proposed hybrid genetic algorithm-based model is compared with Artificial Neural Network. The results showed that the proposed model performs better than neural network in terms of run-time and minimal tour distance.

References
  1. Corwin, B. D. and Esogbue, A. O., 1974. Two Machine flow shop scheduling problems with sequence dependent setup times: a dynamic programming approach, J. Naval Research Logistics.  Vol. 21, pp. 515-524.
  2. Psaraftis, H. N., 1998. Dynamic vehicle routing problems, In: B. L. Golden, A. A. Assad, (eds.) Vehicle Routing: Methods and Studies, Elsevier, Amsterdam, pp. 223–248.
  3. Li, C. Yang, M. and Kang, L. 2006. A New Approach to Solving Dynamic Traveling Salesperson Problems. In: T.-D. Wang, X. Li, S.-H. Chen, X. Wang, H. Abbass, H. Iba, G. Chen, X. Yao, (eds.) SEAL 2006. LNCS, Springer, Heidelberg, vol. 4247, pp. 236–243.
  4. Guntsch, M. Middendorf, M. and Schmeck, H. 2001. An ant colony optimization approach to dynamic TSP. In: Lee Spector et al., editor, Proceedings of the Genetic and Evolutionary Computation, Conference (GECCO-2001), San Francisco, California, USA, 7-11 July 2001. Morgan Kaufmann, pp. 860–867.
  5. Tabatabaee, H. 2015. Solving the traveling salesperson problem using genetic algorithms with the new evaluation function, Bulletin of Environment, Pharmacology and Life Sciences, Vol. 4, No. 11, pp. 124-131.
  6. Zukhri, Z. and Paputungan, I. V. 2013. A Hybrid Optimization Algorithm based on Genetic Algorithm and Ant Colony Optimization, International Journal of Artificial Intelligence & Applications (IJAIA), Vol. 4, No. 5, pp. 63 - 75, DOI : 10.5121/ijaia.2013.4505
  7. Jingui, L. Ning, F. Dinghong, S. and Congyan, L. 2007. An Improved Immune-Genetic Algorithm for the TSP In Proc. IEEE Int. Conf. Natural Computation.
  8. Wang, S. and Zhao, A. 2009. An Improved Hybrid Genetic Algorithm for Traveling Salesperson Problem, In IEEE Proc. Int. Conf. Computational Intelligence and Software Engineering.
  9. Rodriguez, M. A. V. Gutierrez-Gil, R. Avila-Roman, J. M. Sanchez-Perez, J. M. and Gomez-Pulido, J. A. 2005. Genetic Algorithms Using Paralelism and FPGAs: The TSP as Case Study, in IEEE Proc. Int. Conf. Parallel Processing Workshops.
  10. Gharehchopogh, F. S. Maleki, I. and Farahmandian, M. 2012. New Approach for Solving Dynamic Travelling Salesman Problem with Hybrid Genetic Algorithms and Ant Colony Optimization, International Journal of Computer Applications, Vol. 53, No. 1, pp. 0975 – 8887.
  11. Li-Ying, W. Jie, Z. and Hua, L. 2007. An Improved Genetic Algorithm for TSP, In IEEE Proc. Int. Conf. Machine Learning and Cybernetics.
  12. Sze, S. N. 2004. Study on Genetic Algorithms and Heuristic Method for Solving Traveling Salesman Problem, M.S. dissertation, Faculty of Science, Universiti Teknologi Malaysia, Johor, Malaysia.
  13. Wang, S. and Zhao, A. 2009. An Improved Hybrid Genetic Algorithm for Traveling Salesperson Problem, In IEEE Proc. Int. Conf. Computational Intelligence and Software Engineering.
  14. Yingzi, W. Yulan, H. and Kanfeng, G. 2007. Parallel Search Strategies for TSP’s using a Greedy Genetic Algorithm, in IEEE Proc. Int. Conf. Natural Computation.
  15. Zhenchao, W. Haibin, D. and Xiangyin, Z. 2009. An Improved Greedy Genetic Algorithm for Solving TSP, in IEEE Proc. Int. Conf. Natural Computation.
  16. Yan, X. Zhang, C. Luo, W. Li, W. Chen, W. and Liu, H. 2012. Solve Traveling Salesman Problem Using Particle Swarm Optimization Algorithm, IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 6, No. 2, pp. 264-271.
  17. Zhang, C. Sun, J. Wang, Y. and Yang, Q. 2007. An Improved Discrete Particle Swarm Optimization Algorithm for TSP, Proceedings of Web Intelligence/IAT Workshops, pp. 35-38.
  18. Rajasekaran, S. and VijayalakshmiPai, G. A. 2010. Neural Networks, Fuzzy Logic and Genetic algorithms Synthesis and applications, PHI Learning private Limited, New Delhi.
  19. Alireza, A. A. Naserasadi, A. and Zeinab, A. A. 2011. A New Hybrid Algorithm for Traveler Salesman Problem based on Genetic Algorithms and Artificial Neural Networks, International Journal of Computer Applications, Volume 24, No.5, pp. 0975 – 8887.
  20. Potvin, J-Y. 1996. Genetic algorithms for the traveling salesman problem, Annals of Operations Research, Vol. 63, pp. 339-370.
  21. Katayama, K. and Sakamoto, H. 2000. The Efficiency of Hybrid Mutation Genetic Algorithm for the Travelling Salesman Problem, Mathematical and Computer Modeling, Vol. 31, pp. 197-203.
  22. Liu, S. 2014. A Powerful Genetic Algorithm for Traveling Salesman Problem, Proceedings of the course Principles of Artificial Intelligence, Sun Yat-sen University, Guangzhou, China, pp. 1 – 5.
  23. El-Mihoub, T. A. Hopgood, A. A. Nolle, L. and Battersby, A. 2006. Hybrid Genetic Algorithms: A Review, Engineering Letters, 13:2, EL_13_2_11 (Advance online publication).
  24. Donald, D. 2010. Travelling Salesman Problem, Theory and Applications, InTech,Janeza Trdine 9, 51000 Rijeka, Croatia.
  25. Zakir, H. A. 2011. Genetic algorithm for the travelling salesman problem using sequential constructive crossover operator, International Journal of Biometrics and Bioinformatics (IJBB), Vol.3, Issue.6, pp. 96-105.
  26. Oluwadare, S. A. 2009. A Scheduling Algorithm for enhancing operating system support for high-speed multimedia systems, Ph.D. Thesis, Dept. Comp. Sci., Federal University of Technology, Akure, Nigeria.
  27. Raza, Z. and Vidyarthi, D. P. 2009. A computational grid scheduling model to minimize turnaround using modified GA, International Journal of Artificial Intelligence, Vol. 3, No. A9, pp. 86-106.
  28. Johnson, D. S. and McGeoch, L. A. 1995. The Traveling Salesman Problem: A Case Study in Local Optimization, Department of Mathematics and Computer Science, Amherst College, Amherst, MA 01002.
  29. Graupe D. and Gandhi, R. 2001. Traveling Salesman’s Problem Solution using Hopfield Neural Network, Final year Project Report, ECE 559.
  30. Laarhoven, P. V. and Aarts, E. H. L. 1987. Simulated Annealing: Theory and Applications, KluwerAcademic.
  31. Zhao, F. G. Sun, J. S. Li, S. J. and Liu, M. W. 2009. A Hybrid Genetic Algorithm for the Travelling Salesman Problem with Pickup and Delivery, International Journal of Automation and Computing, Vol. 6, No.1, pp. 97-102, DOI: 10.1007/s11633-009-0097-4.
  32. Tsai, C-W. Tseng, S-P. Chiang, M-C. Yang, C-S. and Hong, T-P. 2014. A High-Performance Genetic Algorithm: Using Traveling Salesman Problem as a Case, Hindawi Publishing Corporation, The Scientific World Journal, Vol. 2014, Article ID 178621, pp. 1-14, http://dx.doi.org/10.1155/2014/178621.
  33. Ogunsanmi, B. A. 2015. Hybrid Genetic Algorithm-Based Model for Solving Travelling Salesperson Problem, M.Tech Thesis, Dept. Comp. Sci., Federal University of Technology, Akure, Nigeria, unpublished.
  34. El-Mihoub, T. A. Hopgood, A. A. Nolle, L. and Battersby, A. 2006. Hybrid Genetic Algorithms: A Review, Engineering Letters, 13:2, EL_13_2_11 (Advance online publication)
  35. Helsgaun, K. 1998. An Effective Implementation of Lin- Kernighan Traveling Salesman Heuristic, A Report, Dept. of Comp. Sci., Roskilde Uni., Roskilde, Denmark,http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.4908&rep=rep1&type=pdf.
  36. Saranya, M. and Dhinakaran, S. 2013. Implementation of Traveling Salesman’s Problem Using Neural Network, International Journal of Computer & Organization Trends, Vol. 3, Issue 4, pp. 161-164, ISSN: 2249-2593.
  37. Karapetyan, D. 2010. Design, Evaluation and Analysis of Combinatorial Optimization Heuristic Algorithms, Ph.D Thesis, Dept. Comp. Sci., Royal Holloway College University of London.
Index Terms

Computer Science
Information Sciences

Keywords

Travelling salesperson problem Genetic algorithm Lin-Kernighan algorithm Neural network Optimal solution

Powered by PhDFocusTM