A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem

We present an algorithm for the approximate solution of the nonsymmetric n-city traveling-salesman problem. An instance of this problem is specified by a n × n distance matrix D = (dᵢⱼ ). The algorithm first solves the assignment problem for the matrix D, and then patches the cycles of the optimum assignment together to form a tour. The execution time of the algorithm is comparable to the time required to solve an n × n assignment problem. If the distances dᵢⱼ are drawn independently from a uniform distribution then, with probability tending to 1, the ratio of the cost of the tour produced by the algorithm to the cost of an optimum tour is < 1 + ε (n), where ε (n) goes to zero as n → ∞. Hence the method tends to give nearly optimal solutions when the number of cities is extremely large.