An Exact Ranked Linear Assignments Solution to the Symmetric Traveling Salesman Problem

In this paper, we show how Murty’s ranked linear assignment algorithm can be applied to exactly solve the symmetric Traveling Salesman Problem (TSP). To increase the Murty algorithm’s computational efficiency in solving the TSP, we develop a simple algorithm that determines whether a node that is generated in Murty’s sequential node partitioning process contains a sub-cycle of length less than n, where n is the number of cities to be visited. Each such node cannot generate a genuine solution, which must be a full n-cycle, and can thus be eliminated from further partitioning. In exactly, solving the TSP Murty’s ranking process continues, discarding all such nodes, terminating in a finite number of rankings when the first such ranked solution is encountered that is a full n-cycle. This first ranked n-cycle is the exact solution to the given TSP problem.