Asymmetries in the Travelling Salesman Problem

Master Project - Summer 2019

Supervisors: Prof. Dr. Tobias Friedrich, Dr. Katrin Casel, Gregor Lagodzinski

Motivation

The Traveling Salesman Problem, TSP for short, asks for a fastest round-trip through a given set of cities. It has many obvious applications in logistics but also in other areas such as manufacturing of microchips. Solving TSP is a challenging task, as its corresponding decision problem is NP-hard, which lead to extensive research on how to efficiently compute good solutions. Some even say TSP is "one of the most celebrated and intensively studied problems in combinatorial optimization'' [1].

One way to solve TSP is the simple but elegant Christofides algorithm [2], which combines a minimum spanning tree with a perfect matching to compute a 3/2-approximate solution. This famous result, like many other solutions to TSP, requires that the distances are symmetric (travelling from city \(A\) to city \(B\) takes as much time as travelling from \(B\) to \(A\)) and satisfy the triangle inequality (travelling from \(A\) to \(C\) directly does not require more time than taking a detour through \(B\)). This may not seem like an actual restriction at first, but in reality blocked roads, one way streets or simply traffic may cause violations of symmetry.

For a clear distinction between TSP with and without symmetric distances, these two variants are often referred to as STSP (symmetric) and ATSP (asymmetric), respectively.
Although so far not proven by lower bounds, loss of symmetry seems to have a huge effect. While there are numerous efficient and good approximation algorithms for STSP, no such result is known for ATSP. The recent improvements on the long standing \(O(\log n)\)-approximation for ATSP only yield ratios \(O(\log(n) / \log \log n)\) [1], and 5500 [3] with running-times far from practical.

Purpose of the Project

Many solutions for ATSP transform a given instance into a symmetric one and then use algorithms for STSP. This approach has the drawback that it causes increase in size of the instance, and also significantly worsens the approximation guarantee. We want to take the different approach of designing algorithmic strategies to address asymmetry locally, without extensive increase of running-time or solution quality. With a realistic solution in mind, we want to empirically determine the types of asymmetries that occur in real-world instances. We will then carefully study the effects of non-symmetric distances by analysing how they affect the difficulty to compute good solutions, starting with: Which kinds of non-symmetries are problematic? Can we efficiently compute a good solution if there is only one problematic non-symmetry? What about two, three or any constant number?

What we expect from you. You should bring the curiosity and willingness to delve into an interesting research topic within Theoretical Computer Science. Our main goal is a mathematical understanding of the difficulties non-symmetric distances add to the travelling salesman problem and we expect you to contribute theoretical results.

What you can expect from us. We will gently introduce you to the field and accompany you all along this interesting journey. This will be a team effort, and we aim at publishing our results at a renowned international conference.

[1]	Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, and Amin Saberi: An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem. Operations Research 65(4): 1043-1061, 2017
[2]	Nicos Christofides: Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem. TR 388, Graduate School of Industrial Administration, Carnegie Mellon University, 1976
[3]	Ola Svensson, Jakub Tarnawski, László A. Végh: A constant-factor approximation algorithm for the asymmetric traveling salesman problem. STOC 2018: 204-213, 2018