The Travelling Salesman and Chinese Postman Problems

A problem which has attracted much attention, and continues to do so, is the travelling salesman problem (TSP) in which a salesman starting from town T₁ visits n —1 other towns T₂, T₃,..., T_n, each once only, finally returning to T₁. If the distance d_ij from town T_i to T_j is given for each pair (i, j) find a route for the salesman which minimises the total distance travelled. Much of the interest in the problem arises from the challenge presented by the fact that the problem is easy to state and understand but computationally very difficult to solve. Indeed TSP is ‘at least as difficult to solve’ as any NP-complete problem (see appendix).