Efficient Heuristical Algorithms for the Traveling Salesman Problem Based on Set Tolerances

Combinatorial optimization is a field in mathematics that has grown tremendously in importance within the last years.

We will here investigate the probably most famous problem, the Traveling Salesman Problem (TSP), which is defined as follows.

Given a set of cities, find the shortest possible tour that visits each city exactly once and returns to the origin city.

We will also investigate the asymmetric variant of the TSP,  where the distance between two cities may differ in both directions.

Our algorithms are based on sensitivity analysis, more concretely, on cost changes of elements which keep them inside or outside an optimal solution, so-called single tolerances.In this project, first we plan to extend these methods to multiple elements, so-called set tolerances, and determine how they can be computed efficiently.

Second, we will make use of this theory of set tolerances in TSP, and ATSP algorithms. As a more ambitious aim, we intend to find record tours for the two most famous large-scale TSP instances.

We expect that the project results could be applied to different classes of combinatorial optimization problems and to have a strong impact on real world routing problems from operations research.

One example is the Shortest Path Problem, which is the problem of finding the shortest path between two locations in a network.

This problem has important applications in navigation systems or Google Map and we believe that the project can signficantly contribute in this area.