Traveling Salesman Problem (TSP)

Problem

• Ein Handlungsreisender will n Städte in einer kürzesten Tour besuchen. Es gibt viele ähnliche Anwendungen.

• Modellierung durch einen Graphen mit n Punkten (Ecken/Vertices) und Verbindungen (Kanten/Edges) zwischen allen Punkten.

• Jede Verbindungen zwischen zwei Ecken hat bestimmte (Fahrt-)Kosten.

• Eine Tour ist ein Pfad im Graphen, der alle Punkte umfasst und zum Ausgangspunkt zurückkehrt.

• Problem: finde eine Tour mit den niedrigsten (Fahrt-)Kosten.

• Das Finden einer Lösung ist NP-vollständig.

• Exakte Lösung: durch Aufzählen aller möglichen Touren und heraussuchen der Tour mit den niedrigsten Kosten. Aufwand O(n!) ~ O((n/e)^n+1/2).

• Näherungslösungen: ausgehend von einem Spanningtree ausprobieren von kostengünstigeren Touren. Genetische Algorithmen, Simulated Anneahling. Aufwand für erste Näherung O(n²).

• Exakte Algorithmen: Branch and Bound/Cut. Wenn der Anfang einer Tour schon höhere Kosten hat als die beste bekannte Tour, wird der weiter Suchzweig abgeschnitten.

• Parallele exakte Algorithmen: Verwendung von zentralen und lokalen Arbeitsstapel (Workpiles).

Implementierung mit ArrayList

---

Optimierungen

• Verwendung von byte[] anstelle von ArrayList

• Vermeidung von new byte[.] bei tiefer Rekursion / langen Pfaden

• Parallelisierung mit Threads: Aufteilung der zu untersuchenden Pfade auf mehrere CPUs / Threads

• Verwendung von globalen und lokalen Arbeitsstapeln

• Verwendung der richtigen java (1.4.2) Optionen: -Xms200M -Xmx400M -XX:+AggressiveHeap -XX:+UseParallelGC

• Verteilung auf mehrere Rechner mit Sockets: Aufteilung der zu untersuchenden Pfade auf mehrere Prozesse

---

Implementierung mit byte[]

• da die behandelbaren Probleme weniger als 20 Städte haben braucht man keine dynamische Liste von Integern

• Speicherung der Punkte im Pfad: byte benötigt nur 1 Byte anstelle von mindestens 2 x 4 Byte bei Integer-ArrayList

• Verringerung von new byte[.] durch Wiederverwenden des used-Arrays in den innersten Schleifen / tiefsten Rekursionen

• Lastverteilung durch globale synchronisierte Deque mit FIFO Nutzung

• Lokaler unsynchronisierter Stack (LIFO Nutzung) zur Verwaltung der TeilPfade.

• weitere Optimierung: new byte[.] nur in einer clone() Methode bevor der Pfad in die globale Deque getan wird.

---

Verteilte Implementierung

• Master sendet Pfade zu Servern/Clients. Verteilte Server/Clients suchen besten Pfad und melden diesen zurück.

• Kommunikation mit SocketChannel. Path implementiert Serializable.

• Lastbalancierung durch Rücksenden von Teilpfaden.

• Alternativen: Standalone Server/Client oder Programmcode versenden.

• Verteilte Server empfangen Programmcode und führen diesen aus.

• Verwaltung der Server über ein Maschine-File:

  master:port  # first is master
  host1:port   # first server
  host2:port   # second server
  ...
  

• weitere Optimierung: Verwendung von Threads in den verteilten Programmen

• Verringerung von new byte[.] durch explizites clone() bei Bedarf (bei send() wird automatisch gecloned).

---

Graphical User Interface

• Grundaufbau nach MVC Pattern.

• Modell: behandelt die Verbindung zu den TSP Algorithmen

• View: GUI mit Swing, zeigt Zustand des Modells an

• Controler: verschiedene Event Handler, verändern das Modell

• README und TODO

• TSPgui.jar und TSPdaemon.jar