Exact Minimum Lower Bound Algorithm for Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is defined by a given finite number of (n) cities along with the cost of travel between each pair of them. It is required to find the tour with least cost to visit all of the cities and returning to the starting point. Each city has to be visited once and only once. The TSP has direct applications in many engineering disciplines such as telecommunications, electricity, and a lot of network applications. It has high importance in Geoinformatics as it mathematically model the networks and infrastructures. This research presents the Minimum-Travel-Cost Algorithm for computing an exact lower bound for the general case of the (TSP). Although the TSP does not have yet an exact algorithm to determine its optimal path, this algorithm can help on identifying a minimal threshold that the exact unknown cost will exceed. The minimum-travel-cost algorithm is a dynamic programming algorithm to compute an exact and deterministic lower bound for the general case of the traveling salesman problem (TSP). The algorithm is presented with its mathematical proof and asymptotic analysis. It has a (n²) complexity. A program is developed for the implementation of the algorithm and successfully tested among well known TSP problems and the results were consistent.