Practical Approaches to the Traveling Salesman Problem
Hiroshi Kubo, Norio OKINO · Journal of the Japan Society of Precision Engineering · 1975
There are many engineering problems founded on the traveling salesman problem, e. g. scheduling problem, routing problem and others. In general, this problem is very difficult to solve practically, because it is one of the combinatorial problem. Applying Branch-and-Bound method, an effective progress for the solution was made by Little and others. These algorithms, however, need too long evaluating time as the number of cities is large, and it is required in practical respect to reduce the computing time. In this paper two new algorithms are proposed which shorten the computing time more than 60 per cent for 20 cities problems, and it is expected that this ratio becomes larger when the number of cities increases. Furthermore, one of these algorithms can be used to an approximate solution of a large number cities problem because its approximation ratio (exact cost/approximate cost) reaches 95 per cent or more in one-tenth in evaluating time compared with the existing methods.