Compatible tours for the asymmetric traveling salesman problem

Abstract

In this thesis, we consider this question through the study of a problem called the Compatible Tour Problem (CTP). Given an optimal ASEP solution x*, a compatible tour for x* is a directed Hamiltonian cycle that has exactly one edge coming in and one edge going out of the node set (henceforth called a tight set) of every tight cut of value 2 of x*. The compatible tour problem is the problem of finding a minimum cost compatible tour for x*, where x* is the optimal solution of the ASEP. Note that it is suspected that CTP is an NP-hard problem. We consider the problem of finding a minimum cost "almost" compatible tour for a given solution x* for ASEP. The "almost" compatible tour satisfies important tight sets in x* which are nested with respect to each other. We then develop a heuristic to find this tour as a heuristic solution to the ATSP which is based on the well-known cheapest insertion heuristic for the symmetric travelling salesman problem. Finally, we test this heuristic and give the results. (Abstract shortened by UMI.)