| Abstract: | Two different general approaches to optimizing traveling salesman problem (TSP) tours are investigated. One is a tour construction approach, and the other is a tour improvement approach. The first consists of generalizations of the nearest neighbor heuristic. The nearest neighbor algorithm is generalized in two ways. First, extensions are made in the depth of the neighborhood searched. Second, node selection criteria are broadened. Algorithms are given along with implementations and a small sample of test results. The second type of generalization for the TSP, involves applications of group theory. Any alteration of a tour can be regarded as the operation of a permutation on the tour. Permutations form algebraic structures called groups. The principal idea of this research is to use groups to sample tours of a TSP problem. To make group sampling strategies possible, it is necessary to solve several hurdles. The operation of a permutation on a tour, may not necessarily yield a tour. This can be solved by using the conjugation operation. However, different permutations can conjugate on a tour to yield an identical tour. It is shown precisely how this occurs, and how to avoid it. This research explores data structures and algorithms for carrying out efficient group sampling for a wide range of groups (those groups that are generated by independent permutations). Algorithms are given for manipulating groups and for applying groups to TSP tours (along with their implementations which are given in the appendix). |
|---|