The classical Traveling Salesman Problem aims to find the optimal route (shortest distance) based on a set of n points. A slightly modified version of this problem tries to figure out how a given road network has to be traversed in order to cover all road segments in the shortest possible way. For example, all highlighted road segments in the picture below should be traversed, the required distance however should be minimal.
In the course of this project a smartphone application should by developed, which is capable of calculating the optimal route based on a given road network. Additionally, a navigation along the calculated route should by provided.
Das klassische Traveling Salesman Problem behandelt die Frage, wie die optimale Route (kürzester Gesamtweg) aussieht, um n Punkte zu erreichen, beispielsweise mit einem Auto. Eine leicht modifizierte Fragestellung interessiert sich dafür, wie man ein vorgegebenes Straßennetz abfahren muss, um ALLE Straßenzüge bei minimalem Gesamtweg zu befahren. Beispielsweise will man die roten Straßenzüge in der Abbildung derart abfahren, dass man den minimalen Gesamtweg benötigt.
In dieser Arbeit soll eine Smartphone-App entwickelt werden, die bei vorgegebenem Straßennetz eine optimale Route vorschlägt und eine Navigation entlang dieser Route anbietet.