Die Optimierung von Wegrouten von einem Startpunkt über mehrere sogenannte Wegpunkte zurück zum Startpunkt wird in der Informatik als Travelling Salesman Problem (TSP) – das Problem des Handlungsreisenden – bezeichnet. Besonders schwierig: Beim TSP nimmt der Aufwand für die exakte Berechnung der Lösung für eine steigende Anzahl Wegpunkte mehr als exponentiell zu. «Mittels geeigneter Architekturen und Näherungsalgorithmen wird versucht, das Problem für den jeweiligen Anwendungsfall effizient zu lösen», erklärt IT-Dozent Alain Lafon, der die Bachelorarbeit betreut hat. Untersucht hat Roman Lickel einerseits, welche Architekturen auf das Webumfeld anwendbar sind, und anderseits, welcher Algorithmus sich am besten eignet. Schliesslich erstellte er mehrere Konzepte, um die Architekturvarianten vergleichen zu können.

Die Wahl der Algorithmen stellte sich als wichtigster Einflussfaktor auf die Berechnungsgeschwindigkeit heraus. «Weil Webtechnologien nicht für rechenintensive Aufgaben entworfen wurden, können sie nur durch einen besseren Algorithmus die nötige Effizienz erreichen», so Roman Lickel. Um die bestmögliche Lösung des Problems in der vorgegeben Zeit zu erhalten, hat er eine Aufteilung in Teilprobleme nach der Anzahl Wegpunkte vorgenommen. Aufgrund dieser wird entschieden, welcher Algorithmus für die Berechnung verwendet wird. «Für wenige Wegpunkte erfolgt die Berechnung direkt innerhalb der Web-Applikation», so Roman Lickel. «Bei vier oder mehr Wegpunkten würde der Browser zu lange blockiert und abstürzen, weshalb die Berechnung in einen separaten Berechnungsthread ausgelagert wird.» Laut Roman Lickel stösst der Algorithmus zur exakten Berechnung der Lösung im Webbrowser ab 20 Wegpunkten an seine Grenzen und es kann in nützlicher Zeit nur noch eine Annäherung der Lösung gefunden werden. Der Prototyp, der aufgrund des Konzepts erstellt wurde, zeigt jedoch, dass die Optimierung des TSP mit den gewünschten Anforderungen als Webapplikation umgesetzt werden kann.