Study on heuristic approaches for symmetric traveling salesman problem

Abstract

Traveling Salesman Problem (TSP) is an NP-Hard class of combinatorial optimization problem. Getting an optimal solution for a large-scale TSP instance consumes infeasible time over the computational platform. Exact methods become intractable while solving large-scale TSP instances. Therefore, heuristic approaches are being used, which finds a satisfactory solution instead of an optimal solution in a reasonable time. The heuristic approach prohibits exploring all feasible solutions possible with exact methods; instead, either start with a random solution or construct a feasible solution following the specific criteria. This chapter presents the hybrid of improvement and construction heuristics, which produces a better cost-quality solution in lesser time. In the worst case, it creates a 1.91, 2.86 times better cost-quality compared to the improvement and construction heuristics, respectively. Moreover, it also provides the final cost in the least time, i.e., 16.51, 4.72 times faster than the improvement and construction heuristics, respectively. © 2020 Nova Science Publishers, Inc. All rights reserved.