# RouPSy ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ## Was ist RouPSy? RouPSy ist ein Lernprogramm für Lösungsverfahren des Traveling Salesman Problems, das im Rahmen der Projektarbeit Fakultät Informatik der Hochschule Kemptens entwickelt wurde. Es ist eine Java-basierte Desktopanwendung. Mit RouPSy können anhand zufällig generierter Beispiele vier verschiedene Heuristiken erlernt und geübt werden: - Nearest Neighbour - Nearest Insertion - Farthest Insertion - Cheapest Insertion Außerdem bietet das Programm eine detailierte Erklärung des exakten Lösungsverfahren "Branch and Bound", das anhand eines statischen Beispiels Schritt für Schritt erläutert wird. Das Programm soll als Lerntool für die Lehre eingesetzt werden. ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ## Installation und Ausführung ### Installation In diesem Ordner befindet sich neben dieser Datei auch eine .jar Datei. Falls die Datei nicht als .jar sondern als .zip runtergeladen wurde, die Datei von `[Dateiname].jar.zip` zu `[Dateiname].jar` umbenennen und bei Hinweisen durch das System, dass sich dadurch der Dateityp ändert, diese bestätigen. ### Java Version Für die Ausführung von RouPSy wird mindestens Java Version 11 benötigt. Mit dem Befehl `java -version` kann per Kommandozeile die aktuell installierte/aktive Java Version des Geräts kontrolliert werden. Falls es sich um eine Java Version kleiner als 11 handelt, muss eine aktuellere Version installiert werden. Hier kann eine aktuelle Java Version heruntergeladen werden: https://www.oracle.com/java/technologies/downloads/ Nach der Installation der neuen Java Version, die Version nochmal durch den obigen Befehl kontrollieren (davor muss das Terminal Fenster erneut geöffnet werden). Falls anschließend immernoch die falsche Version bei java -version angezeigt wird, muss eventuell auch die PATH Umgebungvariable angepasst werden, indem der Pfad zur Installation der neuen Java Version dort als ersten Eintrag eingetragen wird. (z.B. unter Windows: "C:\User\Program Files\Java\jdk-18\bin\") Hier findet sich eine Anleitung zum setzen der PATH Variable: https://www.java.com/en/download/help/path.html ### Ausführen der Datei Es gibt zwei Möglichkeiten zum Ausführen der Anwendung: - Durch Doppelklick im Explorer auf die JAR Datei (die Anwendung sollte direkt starten, falls nicht, die Ausführung über Kommandozeile versuchen, dort werden auch evetuelle Fehler angezeigt) - Über Kommandozeile ausführen: `java -jar [Dateiname].jar` ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ## Wie benutze ich RouPSy? Nach dem Ausführen des Programms, landet man auf der Startseite. Hier gibt das Programm eine Einführung zum Traveling Salesman Problem und zu Heuristiken. Unter dem Punkt "Einführung" kann über ein Tutorial die Bedienung des Programms anhand der Nearest Neighbour Heuristik erlernt werden. Hier kann zwischen Beispielen mit 6 oder 12 Städten gewählt werden die dann jeweils zufällig neu generiert werden. Als erstes muss eine Start-Stadt gewählt werden, und dann der ausgewählten Heuristik entsprechend, die Route vervollständigt werden. Hierbei kann über "Erklärung anzeigen" noch die Erklärung des ausgewählten Algorithmus nachgelesen werden. Es kann vor, während oder nach der Durchführung eines Beispiels auch zu anderen Heuristiken gewechselt werden, die mit der gleichen Karte gestartet werden können, die Heuristik, die davor gewählt war wird dabei aber zurückgesetzt. Über den Menüpunkt "Branch and Bound" kann eine ausführliche Erklärung dieses exakten Lösungsverfahrens Schritt für Schritt nachvollzogen werden. Das Beispiel ist hierbei statisch. ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ## Probleme bei der Darstellung Nach dem Ausführen der JAR sieht das Programm verschoben aus, oder die Grafikelemente sind ist nicht gut bedienbar? Momentan gibt es bei der Anwendung noch einen Grafikbug, der die Skalierung der Anwendung beeinflusst. Lösungen: a) Unter den Anzeigeeinstellungen des Primärbildschirms die Skalierung verringern (z.B. wird bei Laptops oft 125%, 150% oder 200% Skalierung vom System empfohlen) und die Anwendung erneut starten. Falls Darstellung immernoch verschoben, andere Skalierung wählen und Anwendung erneut starten (bis die richtige Skalierug gefunden wurde) b) Unter den Anzeigeeinstellungen des Primärbildschirms die Auflösung verringern (z.B. von 3000x2000 auf 1920x1080) und die Anwendung erneut starten. Eventuell muss hier ebenfalls die Skalierung angepasst werden. ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ## Credits Projektteam: Alptug Aslivar, Ramona Erlebach, Lukas Linder, Svenja Orlitta, Maximilian Sontheim und Dominik Wößner Betreuer: Prof. Dr. Peter Klutke ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ## Quellen Für die Entwicklung der Anwendung wurden verschiedene Quellen zur Recherche und Implementierung genutzt. | Thema | Quelle | Notizen | |-------|--------|---------| | Branch-and-Bound Durchführung Video-Beispiel | | Ab Minute 22:55 bis Minute 56:00, aber gesamtes Video ist sehr gut, aber halt Theorie. Nicht von Titel des Videos irritieren lassen. In diesem Teil geht es noch um Branch-and-Bound | | Allgemeine Erklärung von Branch-and-Bound | https://www.youtube.com/watch?v=Zz7hmnpOXEI | In diesem Video wird der Branch-and-Bound Algorithmus anhand des Rucksackproblems erklärt. Hilft zum Verständnis für den Umgang mit dem Entscheidungsbaum | | "TSP-Spiel" (TUM) Anwendung | https://www-m9.ma.tum.de/games/tsp-game/index_de.html | Recherche/Inspiration für Lernumgebung | | "TSP-Spiel" (TUM) Bachelorarbeit | https://mediatum.ub.tum.de/doc/1225159/1225159.pdf | Recherche/Inspiration für Lernumgebung | | Demo TSP TU Chemnitz | https://www.tu-chemnitz.de/mathematik/discrete/demos/tsp/ | Recherche/Inspiration für Lernumgebung | | Rundreise Applet Fernuni Hagen | https://www.fernuni-hagen.de/bwlquam/studium/orlabor/rundreise_applet.shtml | Recherche/Inspiration Lernumgebung | | Rundreise JS App Fernuni Hagen | https://www.fernuni-hagen.de/bwlquam/studium/orlabor/rundreise_javascript.shtml | Recherche/Inspiration Lernumgebung | | Implementierungsbeispiel TSP Google Devs | https://developers.google.com/optimization/routing/tsp#java_9 | Implementierungsbeispiel mit Koordinaten-Matrix | | Sammlung von Erklärungen zu Heuristiken | https://stemlounge.com/animated-algorithms-for-the-traveling-salesman-problem/ | Unterscheidung zwischen Nearest Insertion und Cheapest Insertion mit Animation | | Mathematische Erklärung Nearest Insertion | https://www-m9.ma.tum.de/downloads/felix-klein/19B/nearest-insert.pdf | Unterscheidung zwischen Nearest Insertion und Cheapest Insertion mit Animation | | Mathematische Erklärung Cheapest Insertion | https://www-m9.ma.tum.de/downloads/felix-klein/19B/cheapest-insert.pdf | Unterscheidung zwischen Nearest Insertion und Cheapest Insertion mit Animation |