Der selbstorganisierte Handlungsreisende - TSP using SOM

am

Ein Logistiker wird häufig mit Problemen dieser Art konfrontiert:

  • Ein Handelsreisender möchte eine Reihe von Kunden an verschiedenen Orten besuchen. Nach Abschluss der Besuche möchte er zu seinem Ausgangsort zurückkehren.
  • Für die Entsorgung muss eine Sammeltour zusammengestellt werden, die an allen Containern vorbeiführt, die einem Entsorgungsfahrzeug zugeordnet sind. Das Fahrzeug startet am Betriebshof und muss am Ende wieder dorthin zurückkehren.
  • Ein Transportunternehmen muss in einer Tour verschiedene Kunden anfahren. Start und Ziel der Tour muss der Betriebshof der Spedition sein.
  • Werden verschiedene Teile aus einem Lager benötigt, muss der Lagermitarbeiter vom Übergabeplatz aus alle Kommissionierplätze anfahren, von denen Teile benötigt werden, und am Ende die entnommenen Teile wieder am Übergabeplatz abliefern.

Welcher Weg soll gewählt werden - in welcher Reihenfolge soll der Lagerarbeiter die Kunden aufsuchen bzw. in welcher Reihenfolge soll das Regalbediengerät (RBG) die Regale anfahren - damit die insgesamt zurückgelegte Wegstrecke möglichst gering ist? 

Dieses Problem wird allgemein als Problem des Handlungsreisenden oder auch Travelling Salesman Problem (TSP) bezeichnet. Es wurde bereits 1831 von Voigt (1831) behandelt. Da es sich um ein grundlegendes und weit verbreitetes Problem handelt, wird es schon seit langem untersucht. 

Eine einfache Google-Suche liefert Millionen von Treffern. Auch ich habe mich während meiner Zeit am FLW in Dortmund damit beschäftigt. Einen kurzen und kompakten Überblick gibt die Arbeit von Matai et al. 2010 [8] und natürlich Lawlar et al. 1987 als Klassiker [9].

von Neuronale Netze und der Traveling Salesman

Neuronale Netze sind (wieder einmal) in Mode und die Ergebnisse sind beeindruckend. Oft kann man nicht unterscheiden, ob ein Netz oder ein Mensch etwas erzeugt hat, so dass man von künstlicher Intelligenz spricht. Um es klar zu sagen, alles nur mathematische Näherungen, wenn auch unglaublich kompliziert auf moderner Hardware super schnell. Leider ohne Erklärungskomponente, was für uns einfache Menschen dann magisch erscheint. 
Auch wenn es nur Technik oder Numerik ist, werde ich in diesem Artikel über Neuronen, deren Anpassung, Leben und Sterben sprechen. Neurobabbel ist gerade en vogue.

Alle Autoren erklären die Selbstorganisierende Merkmalskarten auch Kohonen-Karten genannt, so auch ich in ⧉ meiner Dissertation [1]. Das lasse ich sein, warum langweilige Wiederholungen? 

Selbstorganisierende Merkmalskarten (SOM) sind Basis einer guten Heuristik für TSP. Das Verfahren wurde von Angéniol et. al. 1988 [2] beschrieben und Kollege Schäfer promovierte damit an der FLW 1991 [3]. 

In den letzten 30 Jahren gibt es immer wieder Veröffentlichungen zu diesem Thema, die die recht guten Ergebnisse dieser Heuristik vergleichen und sich über die schnelle Berechnung freuen. Das habe ich natürlich auch getan [4, 5]. In den 90er Jahren habe ich 10.000 Zeilen in Borland-Pascal geschrieben, was leider völlig in die Hose gegangen ist. 

Zeit für einen neuen Versuch.

SOM zur Lösung des TSP mit Excel/VBA

Ich höre den Aufschrei bis in mein Homeoffice: "VBA, das ist doch total ineffizient! Da muss man [aktuelle Lieblingssprache einsetzen] nehmen". Nun, mit Excel und VBA geht wirklich alles, das hat jeder auf seinem Rechner und die Arbeitgeber finden es auch gut, wenn man das beherrscht. Außerdem komme ich damit sehr schnell zum ersten Prototypen und bin 100% bürokompatibel.

Für die Analyse eines Algorithmus und seiner Laufzeitkomplexität ist es aber egal, auf welcher Hardware mit welcher Sprache etwas implementiert ist. Das ist natürlich vereinfacht, weil durch Parallelisierung und Vektorisierung erhebliche Geschwindigkeitssteigerungen möglich sind, wie z.B. Tensorflow zeigt. Darüber wird noch zu sprechen sein.

Den Trainingsablauf zeige ich in ▷ diesem Video, andere Animationen im Netz unterscheiden sich darin, dass ein Vielfaches an Neuronen genommen wird, als Städte besucht werden sollen. In meiner Lösung gibt es einen starken Selektionsdruck. Neue Neuronen werden immer dort erzeugt, wo sie gebraucht werden. Neuronen, die keine Stadt "repräsentieren", bekommen 2 Lernzyklen lang eine Chance. Haben sie bis dahin keine Stadt gefunden, sind sie nutzlos und müssen sterben.

Statt also den Ring mit viel zu vielen Neuronen langsam zu verformen, werden in den "interessanten" Ecken mehr Neuronen gebildet und dort, wo wenig los ist, Neuronen abgebaut [2]. Also wieder nach biologischem Vorbild. Die Adaption während des Trainings, die Nachbarschaftsfunktion der Neuronen und die sogenannte Relaxation habe ich stark vereinfacht. Es gibt einfach keine Relaxation, die Nachbarschaft wird einfach periodisch abgebaut und die Adaption ist eine Dreiecksfunktion. Das beschleunigt die vorige Variante noch einmal erheblich.

Die erste hier veröffentlichte ▦ Version 1.9 erzeugt etwa 8% schlechtere Touren als das Optimum. Die Probleme entnehme ich der  ↪ TSPLIB [6]. Meine früheren Versionen sind nur unwesentlich schlechter. Wenn ein neues Neuron erzeugt wird, muss es in den Ring eingefügt werden. Dabei kann es passieren, dass eine Kreuzung entsteht, die ich dann am Ende durch einfaches Vertauschen zweier Nachbarn beseitige. 

Alle Daten der Läufe werden ebenfalls in der Excel-Tabelle gespeichert. Für weitere Auswertungen der Läufe werden Daten in verschiedenen Sheets gespeichert, die dank Excel leicht beliebig erweitert werden können. Beim ersten Start müssen die Makros aktiviert werden.

Statt also den Ring mit viel zu vielen Neuronen langsam zu verformen, werden in "interessanten" Ecken mehr Neuronen erzeugt und da, wo wenig los ist, werden die Neuronen abgebaut [2]. Eben wieder am biologischen Vorbild orientiert. Die Adaption während des Trainings, die Nachbarschaftsfunktion der Neuronen und die sog. Relaxation habe ich stark vereinfacht. Es gibt einfach keine Relaxation, die Nachbarschaft wird simpel periodisch reduziert und die Adaption ist eine Dreiecksfunktion. Das beschleunigt die vorige Variante noch mal erheblich.

Die erste hier veröffentlichte ▦ Version 1.9 erzeugt etwas schlechtere Touren ~9% als das Optimum. Die Probleme entnehme ich der ↪ TSPLIB [6]. Meine früheren Versionen sind nur marginal schlechter. Inzwischen ist ▦ Version 2.6 veröffentlicht knapp unter 3% (1.5-1.9 ~9% → 2.0-2.5 ~4.3% → 2.6 ~2,9%)  Wenn ein neues Neuron erzeugt wird, dann muss es in dem Ring eingefügt werden. Dabei kann es passieren, dass eine Kreuzung erzeugt wird, die ich dann durch einfaches Vertauschen zweier Nachbarn zum Schluss beseitige. 

Alle Daten der Läufe sind auch in dem Excel Sheet gespeichert. In verschiedenen Sheets werden Daten für weitere Auswertungen der Läufe gespeichert, was sich dank Excel leicht beliebig erweitern läßt. Bei ersten Start müssen die Makros aktiviert werden.

Weitere Schritte

  1. Die Bedienbarkeit des Programms lässt zu wünschen übrig, ich kann's 😉 
  2. Der VBA-Code kann sicher verbessert werden.
  3. Der Algorithmus ist noch nicht ausgereizt, gerade bei großen Problemen.
  4. Die Parameter sind in keiner Weise optimiert eingestellt.
  5. Es fehlt ein Review des Standes für TSP mit SOM → △ Review TSP-SOM
  6. Es können nur euklidische Probleme behandelt werden.
  7. Geokoordinaten müssen in euklidische umgerechnet werden.  
  8. Probleme mit systematischen  Positionen (Platinen) werden schlecht gelöst.
  9. Bei Problemen mit unbekanntem Optimum sollte ein Abschätzung gemacht werden.
  10. Eine Systematische KI gestützte Suche aus Publikationen und Experimenten 
  11. Warum Excel - ein pragmatischer Ansatz alle. nicht nur für IT-Experte.
  12. Eine Portierung des Kernalgorithmus wäre effizient (Python, Keras)
An den Punkten 2,3,4 habe ich nach der Erstveröffentlichung gearbeitet, wenn auch das Ende der Fahnenstange noch nicht erreicht ist. Das Review 5 ist geschrieben △ Review TSP-SOM daraus isst Ar4betipunkt 10 entstanden.

Da sind natürlich auch einige Abschlussarbeiten drin. 

Update 2.1.23

Punkt 3 ist im Prinzip erledigt, noch mal deutlich schneller, bei großem Problemen. Bei kleinen Problemen eher etwas langsamer, was egal ist, da sowieso schnell. Ein wenig Luft ist noch drin, wenn der Algorithmus mit weniger Neuronen startet, aber da muss dann noch die Ergebnisqualität angesehen werden. Hier Version 2.0 zum Download.

Update 16.1.23

Es ist ja offensichtlich, dass beim Training Kreuzungen in der Tour entstehen. Damit wird die Topologieerhaltung der selbstorganisierenden Merkmalskarte verletzt. Topologiedefekte erkennen und vermeiden ist ein grundlegendes Problem der SOM, eigentlich von jedem unsupervised learning Verfahren. Das hat Rätzer untersucht [7]. 

Ich habe daher nach dem Training ein 6-opt für nebeneinanderliegende Tourpositionen zur Nachbearbeitung eingebaut. Der Algorithmus ist rekursiv und kann natürlich auch mehr Tourpositionen einbeziehen, dauert dann eben länger.

Mit einigen Versuchen habe ich die Zykluszahl auf 4 und die Lebenszeit auf 2 gesetzt. 

Noch mal deutlich den VBA-Code geändert, Für jeden Zyklus wird die Adaption und die Nachbarschaftsfunktion aus einer Tabelle in ein Varant-Array eingelesen. Damit kann dann jede beliebige Funktion eingesetzt werden. Der Rechenaufwand dafür ist aus dem Training ausgelagert. 

Hier Version 2.3 zum Download.

Update 19.01.2023

Die Übersichtswerke von Matai et.al. aus 2010 [8] und Lawlar et.al. aus 1987 [9] ergänzt. Weitere Schritte mit dem △ Review TSP-SOM upgedatet. Neu Punkt 10

Update 29.01.2023

Aktuelles Version meiner "Jedermann-SOM" ist 2.6 hier zum Download. In der Problemliste stehen 16 Probleme. Nur die euklidischen sind vergleichbar. Die Laufzeitprognose ist jetzt aktiv und basiert auf allen Problemen und ~random-Problemen. Die Berechnung ist dynamisch und wird mit neuen Rechnungen aktualisiert.

2.6 ist erheblich schneller und das n-Opt zur Nachbearbeitung nutzt jetzt Heap-Permutation [10]. Ich habe das c++ Programm von geeksforgeeks auf VBA umgeschrieben und verwende statt eines geschlossenen Rings eine Route wobei Anfang und Ende fest sind. 8 benachbarte Punkte können locker auf meinem Surface Book mit allen Permutationen gerechnet werden. 

Text mit DeepL Write Beta überarbeitet.


Mal sehen, wann ich wieder etwas Zeit habe.

Quellen

  1. Wölker M (2000), "Analyse Logistischer Systeme mit Selbstorganisierenden Merkmalskarten". Thesis at: Universität Dortmund. Dortmund, Juni, 2000. Verlag Praxiswissen. [BibTeX] [URL]
  2. B. Angéniol, G. de la, C. Vaubois, J-Y L. Texier, Self-organizing feature maps and the travelling salesman problem, Neural Netw. 1 (1988) 289–293.
  3. G. Schäfer, Beitrag zur Optimierung von Kommissionierfahrten in Hochregallagergassen mittels neuronaler Netze,  Universität Dortmund, MB - FLW, 1991
  4. Jünemann R and Wölker M (1991), "Selbstlernende Systeme in der Kommissioniertechnik, Einsatz von Neuronalen Netzen", In Trends in Materialsflußsystemen, Tagungsband 9. Dortmunder Gespräche, pp. 251 - 259. TüV Rheinland. [BibTeX] [URL]
  5. Wölker M (1996), "Dem Denken abgeschaut, Neuronale Netze im praktischen Einsatz" Braunschweig, Wiesbaden , pp. 84 - 95. Vieweg, Facetten. [BibTeX] [URL]
  6. Gerhard Reinelt, TSPLIB 95, Universität Heidelberg, Institut für Angewandte Mathematik, 2016, http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
  7. Udo Rätzer, UNtersuchung zu effizienten Beurteilungskriterien für das Training Selbstorganissierender Merkmalskarten, Universität Dortmund, Informatik Systemanalyse, Diplomarbeit, 5, 1996
  8. Matai, Rajesh, Surya Singh, and Murari Lal. 2010. “Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches.” Traveling Salesman Problem, Theory and Applications, November. InTech. doi:10.5772/12909.
  9. E.L. Lawlar, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys. The Travelling Salesman Problem. John Wiley and Sons, Chichester, 1987.
  10. Seite „Heap-Algorithmus“. In: Wikipedia – Die freie Enzyklopädie. Bearbeitungsstand: 28. Mai 2021, 15:50 UTC. (Abgerufen: 29. Januar 2023, 15:26 UTC)

, Licence CC BY-NC-SA

Kommentare

Kommentar veröffentlichen