Excerpt from Branch and Bound Methods for Combinatorial Problems

The difficulty of the problem is entirely computational since the number of tours (i.e. Feasible solutions) is finite. Enumeration of all tours, however, would be a discouraging process for a problem of any appreciable size. There are (n-l)! Tours. Doubling the size of a problem from 5 to 10 cities multiples the number of tours by about 15 thousand; doubling from 10 to 20 cities, by about 250 billion. To put the branch and bound algorithm in perspective, we report briefly on other approaches to the traveling salesman problem. Several methods have been developed for finding a good but not necessarily optimal tour. One of these is random search. Since any permutation of the first n integers can be interpreted as a tour, it is an easy matter to generate a tour by a random process, evaluate its cost, and compare it to the best of any previously developed solutions. Since these steps can be performed quickly, a large number of tours can be generated, and the best one will usually be a good solution. Further more, the statistics generated make it possible to say something about the probability of finding a better solution. This type of approach has been investigated by Heller [8] for a somewhat different problem and in much more detail with more sophisticated random search procedures by Reiter[l6,17]for the traveling salesman problem. On a somewhat similar tack Karg and Thompson[10] have developed a heuristic program. However, their program is designed primarily for the symmetric case.
Such approximate methods are important, especially for large* problems.

About the Publisher

Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com

This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.