NOVEL HEURISTIC - BASED APPROACH USING TOUR CONSTRUCTION ALGORITHMS TO SOLVING THE TRAVELLING SALESMAN PROBLEM (TSP)

The Travelling Salesman Problem (TSP) is a classical optimization problem which has gained wide attention of computer scientists. This is so because it is widely used as a fundamental approach to solving many combinatorial problems. It is easy to formulate but difficult to solve. It is an NP - hard problem because it is impracticable to solve using exact algorithms. Therefore, recurse is usually made to heuristics in solving not only the TSP but also the combinatorial problems. The goal of this study was to consider five existing heuristics, implement them, compare their complexities and then hybridize two or more to get a new and superior heuristic for solving the TSP in particular and other combinatorial problems in general. Five heuristics were implemented and their complexities were compared. Varying graph sizes including four nodes, ten nodes and so on up to fifty nodes were implemented. The length of their edges in general were generated using random number generating algorithm. A new heuristic called Hybridized Full Edge Search (Hybrid - FES) was derived. It time complexity was computed and compared with those of the five already existing heuristics. It was observed that the Hybrid - FES performed better, in fact, the larger the graph size, the better its performance when compared with the performance of the existing heuristics. The result of the complexity comparisons were shown as tables, histograms and curves. This study therefore shows that the hybrid - FES outperforms all of the existing heuristics for solving the TSP and in general the combinatorial problems. In case of future study, the number of the existing heuristics to be considered may be increased. Also more measures could be considered. In general the research contributed to complexity study of combinatorial optimization structures by proposing a new and more efficient heuristic.