In dieser Arbeit wird das Travelling Politician Problem eingeführt. Das Travelling Politician Problem basiert auf dem Travelling Salesman Problem, welches die Aufgabe beschreibt, die kürzeste Rundtour eines Vertreters zu finden, wenn eine Liste mit allen Städten und deren Abständen zueinander gegeben ist. Das Travelling Politician Problem behandelt die Tour eines Politikers im Wahlkampf. Im Gegensatz zum Travelling Salesman Problem muss nicht jede Stadt besucht werden, da Wähler von naheliegenden Städten anreisen können, um eine Wahlkampfveranstaltung zu besuchen.
Weiterhin wird ein Annäherungsalgorithmus entwickelt und in Java implementiert, seine Güte für unterschiedliche Szenarien bewiesen und dann empirisch mit einem exakten Algorithmus verglichen, welcher mithilfe eines ILP-Solver entwickelt wird. In einem separaten Test werden die Grenzen des Approximationsalgorithmus mit zunehmender Inputgröße überprüft. Die Tests werden mit zufällig generierten Daten durchgeführt. |
