Cost Reduction of Traveling Salesman Problem with an Enhanced Genetic Algorithm

International Journal of Research and Scientific Innovation (IJRSI) | Volume VII, Issue I, January 2020 | ISSN 2321–2705

Cost Reduction of Traveling Salesman Problem with an Enhanced Genetic Algorithm

K. B. Ishola^1*, O. E. James^2
1,2Department of Computer Science, Federal University of Lafia, P.M.B 146 Lafia, Nigeria
*Corresponding Author

Abstract: – Traveling Salesman Problem is a variation of NP hard problem and that has made it an interesting and challenging problem in the field of computer science, even though many techniques have been proposed to improve the performance of TSP.
Genetic Algorithm is a technique used in computing to search the optimal solution from a various possible solution to a computational problem in order that maximizes or minimizes a particular function and Travelling Salesman Problem (TSP) is computational optimization problem. The time to solve TSP grows exponentially as the number of cities increases; if it is to be solved within a reasonable amount of time then it requires optimal solution. This research work examines the solution to improve the performance of TSP by coding it into a genetic form.
The aim of this research work is to use the modified elements of Genetic Algorithm such as chromosomes, selection, crossover, mutation and fitness function to solve the Travelling Salesman Problem where one has to find the shortest or efficient route among the cities from the origin.

Keywords- TSP, NP-Complete Problem, Genetic Algorithm, GA operator

I. INTRODUCTION

Traveling salesman problem (TSP) is NP Complete Problem, where a salesman needs to travel, given a number of cities and the distances (costs) of traveling from any city to any other city, the goal is to find optimal or shortest route from the starting point and visits each city exactly once and then returns back to the starting city[1].
TSP as NP-Hard problem combinatorial optimization problems means the solution techniques have not been improved in polynomial time. If an efficient algorithm is found for the TSP problem, then efficient algorithms could be found for all other problems in the NP complete class. However, it has been known to required heuristic algorithms such as the genetic algorithm (GA) that could obtain possible optimal solutions within reasonable time[2].

Read More