%0 Journal Article
%T An Exact Ranked Linear Assignments Solution to the Symmetric Traveling Salesman Problem
%A Roy Danchick
%J Open Access Library Journal
%V 7
%N 3
%P 1-8
%@ 2333-9721
%D 2020
%I Open Access Library
%R 10.4236/oalib.1106159
%X 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.
%K Traveling Salesman
%K Applied Probability
%K Assignment
%U http://www.oalib.com/paper/5427180