Group Theoretic Tabu Search Approach to the Traveling Salesman Problem

The traveling salesman problem (TSP) is a combinatorial optimization problem that is mathematically modeled as a binary integer program. The TSP is a very important problem for the operations research academician and practitioner. This research demonstrates a Group Theoretic Tabu Search (GTTS) Java algorithm for the TSP. The tabu search metaheuristic continuously finds near-optimal solutions to the TSP under various different implementations. Algebraic group theory offers a more formal mathematical setting to study the TSP providing a theoretical foundation for describing tabu search. Specifically, this thesis uses the Symmetric Group on n letters, Sn, which is the set of all n! permutations on n letters whose binary operation is permutation multiplication, to describe the TSP solution space. Thus, the TSP is studied as a permutation problem rather than an integer program by applying the principles of group theory to define the tabu search move and neighborhood structure. The group theoretic concept of conjugation (an operation involving two group elements) simplifies the move definition as well as the intensification and diversification strategies. Conjugation in GTTS diversifies the search by allowing large rearrangement moves within a tour in a single move operation. Empirical results are presented along with the theoretical motivations for the research.