Very Near Optimal Algorithm for the Traveling Salesman Problem

Abstract

The Traveling Salesman Problem (TSP) is a P versus NP key problem that can be generalized to some instances of other problems. Using the commercial state-of-the-art branch-and-bound mixed integer linear programming solver (LINGO) solves the TSP problem in an amount of time that is proportional to a quadratic multiplied by an exponential of base two as a function of the number of cities or destinations. My algorithm solves the problem in a quadratic amount of time as a function of the number of cities or destinations. My algorithm basically solves the problem by sorting the cells in the cost or distance matrix from lower to higher values, while checking for cycles. My algorithm performs on average 43.67% better than LINGO for 100 cities or destinations. In the interconnected world of the present and future, fast and reasonably good solutions are better than reaching (if ever) the global optimal solution.