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

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


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.


Download data is not yet available.


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:

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:

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:

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:

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:

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:

How to Cite
Hossain, M. S., Choudhury, S. S., Hayat, S. M. A. I., Tanim, A. S., 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.