An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator

  • Md. Sabir Hossain Chittagong University Engineering and Technology
  • Ahsan Sadee Tanim The International University of Scholars
  • Sadman Sakib Choudhury Chittagong University Engineering and Technology
  • S. M. Afif Ibne Hayat Chittagong University Engineering and Technology
  • Muhammad Nomani Kabir Universiti Malaysia Pahang
  • Mohammad Mainul Islam Extend View Inc.
Keywords: Traveling Salesman Problem, Crossover Operator, Minimal Weight Variable, Genetic Algorithm,

Abstract

The traveling salesman problem (TSP) is a famous NP-hard problem in the area of combinatorial optimization. It is utilized to locate the shortest possible route that visits every city precisely once and comes back to the beginning point from a given set of cities and distance. This paper proposes an efficient and effective solution for solving such a query. A modified crossover method using Minimal Weight Variable, Order Selection Crossover operator, a modified mutation using local optimization and a modified selection method using KMST is proposed. The crossover operator (MWVOSX) chooses a particular order from multiple orders which have the minimum cost and takes the remaining from the other parent in backward and forward order. Then it creates two new offspring. Further, it selects the least weight new offspring from those two offspring. The efficiency of the proposed algorithm is compared to the classical genetic algorithm. Comparisons show that our proposed algorithm provides much efficient results than the existing classical genetic algorithm.

Downloads

Download data is not yet available.

References

Ezugwu, A. E. S., & Adewumi, A. O. Discrete symbiotic organisms search algorithm for travelling salesman problem. Expert Systems With Applications, 87, 70-78. 2017 DOI: https://doi.org/10.1016/j.eswa.2017.06.007

Chudasama, C., Shah, S. M., & Panchal, M. Comparison of parents selection methods of genetic algorithm for TSP. In International Conference on Computer Communication and Networks CSI-COMNET, Proceedings (pp. 85-87). 2011.

Xu, S., Wang, Y., & Huang, A. Application of imperialist competitive algorithm on solving the traveling salesman problem. Algorithms, 7(2), 229-242. 2014 DOI: https://doi.org/10.3390/a7020229

Srinivasan, K., Satyajit, S., Behera, B. K., & Panigrahi, P. K. Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience. arXiv preprint arXiv:1805.10928. 2018

Hatamlou, A. Solving travelling salesman problem using black hole algorithm. Soft Computing, 22(24), 8167-8175. 2018. DOI: https://doi.org/10.1007/s00500-017-2760-y

Abdoun, O., & Abouchabaka, J. A comparative study of adaptive crossover operators for genetic algorithms to resolve the traveling salesman problem. arXiv preprint arXiv:1203.3097. 2012

Hussain, A., Muhammad, Y. S., Nauman Sajid, M., Hussain, I., Mohamd Shoukry, A., & Gani, S. Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator. Computational intelligence and neuroscience, 2017. DOI: https://doi.org/10.1155/2017/7430125

Dwivedi, V., Chauhan, T., Saxena, S., & Agrawal, P. Travelling salesman problem using genetic algorithm. IJCA Proceedings on Development of Reliable Information Systems, Techniques and Related Issues (DRISTI 2012), 1, 25. 2012.

Islam, M. L., Pandhare, D., Makhthedar, A., & Shaikh, N. A Heuristic Approach for Optimizing Travel Planning Using Genetics Algorithm. International Journal of Research in Engineering and Technology eISSN, 2319-1163. 2014.

Karaboga, D., & Gorkemli, B. Solving Traveling Salesman Problem by Using Combinatorial Artificial Bee Colony Algorithms. International Journal on Artificial Intelligence Tools, 28(01), 1950004. 2019 DOI: https://doi.org/10.1142/S0218213019500040

Dorigo, M., & Gambardella, L. M. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on evolutionary computation, 1(1), 53-66. 1997 DOI: https://doi.org/10.1109/4235.585892

Published
2019-12-01
How to Cite
Hossain, M. S., Tanim, A. S., Choudhury, S. S., Hayat, S. M. A. I., Kabir, M. N., & Islam, M. M. (2019). An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator. EMITTER International Journal of Engineering Technology, 7(2), 480-493. https://doi.org/10.24003/emitter.v7i2.380
Section
Articles