Optimierung kürzester Weg im Warenlager

[kekster]

Hallo allerseits,

ich versuche derzeit für die Kommissionierung in einem Warenlager optimale Routen zwischen einzelnen Positionen zu finden. Dazu habe ich das Lager nachgebaut und die einzelnen Regale des Lagers mit Wegpunkten verbunden. Als Screenshot: l3xqc2fd.jpg - directupload.net
Hier müsste man sich vorstellen, dass das komplette Lager mit Wegpunkten verbunden ist und nicht nur der kleine Ausschnitt oben links im Bild.
Die orangenen Punkte sind Wegpunkte, die blauen Linien sind Verbindungen zwischen den Wegpunkten und die grünen Linien sind Verbindungen zwischen Regalen und Wegpunkten.

Wenn ich nun innerhalb dieses Lagers 20 Wegpunkte zur Kommissionierung anlaufen möchte, dann würde ich zur Wegoptimierung auf den traveling salesman zurück greifen und den Ameisenalgorithmus nutzen. Dabei nehme ich verschiedene Beispiele und Diplomarbeiten zur Hilfe...

Nun aber zu meinem Problem: der traving salesman müsste die kürzeste Route zwischen zwei Wegpunkten kennen. In meinem Beispiel gibt es aber optimierte Routen zwischen den einzelnen Wegpunkten. Um von Wegpunkt A nach B zu kommen, müsste ich zb über C, D und E gehen.

Heißt das nun, dass ich im Vorfeld -jede- nur mögliche Route zwischen -jedem- Wegpunkt optimieren muss (zb Ameisenalgorithmus)?! Nachdem ich dann alle optimierten Wege zwischen allen Wegpunkten habe, kann ich den traveling salesman loslassen.

Sehe ich das richtig?! Dann müsste ich erst zwei Tage rechnen lassen, damit alle Wegpunkte untereinander optimiert wurden... Oder übersehe ich etwas?!

Vielen Dank & beste Grüße!

 

[Lodorvonhal]

Hallo,

ich hoffe ich habe Dein Problem richtig verstanden und Versuche mal einen Ansatz.

Da du in deinem Warenlager die ganzen Wegpunkte hast, müsstest du zur Implementierung ja einen Graphen nutzen. Um den kürzesten Weg zwischen zwei Regalen zu finden, ist im Graph ja definiert, welche Wege erlaubt sind. Zusätzlich müsstest du Kosten für die Nutzung jeder Kante des Graphen haben (Entfernungen o.Ä.).

Wie wäre es mit einem Wegfindungsalgorithmus, welcher abhängig von Graph und den Kosten den optimalen Weg errechnet. Ich denke da z.B. an A-Stern.

Als Ergebnis von A-Stern bekommst du die Gesamtkosten für den optimalen Weg und den Weg als Liste.
Das müsste man eigentlich nur einmal ermitteln, da sich diese Werte nicht noch einmal ändern.


Diese Kosten zwischen deinen Punkten könnte man in die Matrix für das Rundreiseproblem übernehmen.

 

[kekster]

Hallöchen,

jepp - ich denke du hast mich richtig verstanden

Allerdings verstehe ich deinen Ansatz über einen Graphen nicht?! Zielsetzung hast du soweit richtig angesprochen: berechne alle Kosten zwischen 2 Wegpunkten für den traveling salesman.

Du meinst also, dass ich alle Knoten (=Wegpunkte) in einen Graphen aufnehme und die Entfernung zum Nachbarn als Gewichtung der Kante nehme? Da könnte ich dann per A* oder Dijkstra den kürzesten Weg zweier Knoten berechnen.

Nehme ich mal an, dass ich in meinem Lager 20 Wegpunkte zu besuchen habe. Dann müsste ich für jeden dieser 20 Wegpunkte per A* oder Dijkstra o.ä. den kürzesten Weg zu jedem anderen berechnen. Nachdem ich dann die Kosten für jeden Weg berechnet habe, kann ich mir per traveling salesman den kürzesten Weg zwischen alles 20 Knoten berechnen lassen.

Hmmm... habe ich doch so richtig verstanden? Aber wäre der Aufwand zum Berechnen der kürzesten Wege zwischen allen 20 Knoten nicht extrem hoch und damit extrem langsam? Wären das nicht 20! Möglichkeiten?? Zudem hat das gesamte Lager insgesamt ca. 1.000 Knoten so dass der Aufwand für die Suche des kürzesten Weges zwischen 2 Knoten schon recht aufwändig ist. Du hast Recht: man muss die Entfernungen der Knoten untereinander nicht jedes mal neu berechnen - aber wenn diese Daten noch nicht vorliegen, dann müssen sie ja erst einmal berechnet werden.

Aber ein echt guter Ansatz! An einen Algorithmus zu kürzesten Pfaden habe ich bisher nicht gedacht.

Vielen Dank

 

[Lodorvonhal]

Das freut mich das ich helfen konnte.

Mit Graphen meinte ich ein Abbild deiner Karte (Lager). Dazu wendet man gern die Graphentheorie an.
Der Graph wäre deine Karte, wobei jeder Wegpunkt ein Knoten des Graphen wäre und jede Kante der Weg dazwischen.

Grundlegend braucht man für das Rundreiseproblem ja nur die Punkte, welche abgelaufen werden müssen. Du benötigst aber Zusätzlich bei der Wahl der Strecke A zu B - den Weg von A nach B über weitere Wegpunkte x, y und z.
A-Stern würde dir die Kosten für die Matrix geben und den Weg, welcher abgearbeitet werden würde wenn deine Rundreise startet. Diese Werte hast du dann aber irgendwo schon gespeichert.


A-Stern ist im Vergleich zu anderen Algorithmen recht rechenaufwändig, das stimmt. Ist halt die Frage wie groß der Graph ist. Für eine kleine Java Anwendung aber kein Problem. Ich habe selber vor kurzem eine Belegarbeit geschrieben mit einer Implementierung des A-Stern unter Android. Die Berechnung geht sehr fix.
Dazu kann ich dir folgende Seite empfehlen:
A* Pfadfindung für Anfänger

Dieser Artikel bezieht sich jedoch auf eine symmetrische Karte als Raster. Daher sind die Kosten pro Kante dort fix. Ich denke mal in dem Lager wird das nicht so sein. Generell ist das Bsp auf eine Spielkarte bezogen.

Bei Fragen oder Problemen kannst Du Dich gerne melden, momentan stecke ich noch gut im Thema drin.

MFG

 

[kekster]

Ok - wunderbar. Vielen Dank für dein Feedback bis hierhin.

Ich bin mit dem ersten Schritt durch und habe die Entfernungen der abzulaufenden Knoten alle per Dijkstra (kenne ich noch aus Vorlesungen, daher lieber Dijkstra anstatt A*) berechnet. Als Ergebnis habe ich nun einen Graphen mit x Knoten, der alle Knoten mit einer Gewichtung miteinander verbindet. Um nun die schnellste Route zu finden, habe ich Implementationen des Ameisenalgorithmus gefunden.

Mein Problem ist nun folgendes: tsp.jpg - directupload.net

Ich möchte nicht nur die schnellste Route von den 4 Knoten wissen, sondern Vorgabe ist ebenfalls, dass ich beim Punkt Z starte und beim Punkt Y ende. Die kürzeste Route aus dem Graphen wäre zb C - D - B - A. In diesem Fall wäre C zwar nah an Z (= dem Startpunkt) dran, aber A wäre zu weit weg von Y (= Endpunkt).

Ich nutze dazu folgende Implementation: Test Run - Ant Colony Optimization

Aber - wie auch jeder andere Ameisenalgorithmus - bildet die kürzeste Route quasi einen Kreis - wie auch zb hier: http://upload.wikimedia.org/wikiped...Deutschland_3.png/220px-TSP_Deutschland_3.png

Ich finde einfach keine logische Lösung, um einen Start- bzw Endpunkt in den Algorithmus einzubauen. Was müsste ich tun, um VON Knoten Z alle Knoten A, B, C, D zu besuchen und ZU Knoten Y zum Schluß zurück zu kehren. Die Entfernung der Knoten Z und Y zu sämtlichen anderen Knoten sind mir bekannt.

Hast du dazu noch eine Idee?! Mir fällt kein algorithmischer Ansatz ein :/

Viele Grüße & besten Dank

 

[Lodorvonhal]

Du darfst die beiden Algorithmen und ihre Graphen nicht vermischen.

Dein Ameisenalgorithmus berechnet dir die optimale Route. Fall: Du stehst an der der Lagertür L und musst zu Punkt A, B und C (start und ziel wäre ja dein L - irgendwo muss man ja anfangen)
Ziel des Ganzen ist ein Weg zu finden der alle Punkte in einer Rundreise verbindet UND dies mit dem kürzesten Gesamtweg.
Der Algorithmus braucht dazu die Entfernungen zwischen allen Punkten. Er gibt dir dann eine optimale Rundreise (z.b: L - B - A - C)
In deinem Fall sind diese Punkte ja nur deine Lagerplätze und kein Wegpunkt im Lager!

Zusätzlich kommt in deinem Beispiel noch die Wegfindung des optimalen Weges zwischen den Punkten. Dazu nutzt du Dijkstra (A stern wäre zwar besser aber gut ^^) dieser gibt dir den kürzesten Weg zwischen den einzelnen Punkten (z.B. zwischen A und B) die Kosten für diesen Weg braucht dein Ameisenalgorithmus für die Matrix.
Exkurs: den kürzesten Weg ermitteln wir ja, da dieser in den Lager nicht trivial zu ermitteln ist.

Zusätzlich liefert die Dijkstra eine Liste von Wegpunkten welche du zwischen Punkt A und Punkt B für den optimalen Weg benötigst. Dies wären dann alle möglichen Wegpunkte im gesamten Lager!
Dem Ameisenalgorithmus ist es egal wie du von A nach B kommst. Er möchte nur die Entfernung haben.


Die komplette Ausführung ist so, wie ich mir das denke. Bitte berichtigen, falls ich Blödsinn erzähle. opcorn:


Zusatz: Ich hab keine Ahnung warum du sagst, dass du bei (deinem Beispiel) Z startest und bei Y ankommst. Dann hast du ja keine Rundreise. Ist das gewollt? gibt es einen speziellen Anwendungsfall dazu?

(bezogen auf dein Beispiel)
Als Ansatz würde ich zuerst dein Ameisenalgorithmus auf deine Knoten A,B,C,D anwenden. (folgend als Menge K genannt) Dieser gibt dir den optimalen Weg zwischen diesen 4 Knoten. Dann würde ich schauen wie die Entfernung zwischen Z und allen Knoten und Y und allen Knoten. Bedingung wäre, dass die Verbindung von Z zu K und Y zu K nur so erlaubt ist, als das diese Verbindung "benachbart" wäre. (Für das Beispiel wäre A-B-C-D schon die optimale Route)

https://dl.dropboxusercontent.com/u/34845727/list.JPG

Dies wäre wichtig, da der optimale Weg von K sonst gesprengt würde. Davon müsste man die Kombination wählen, wo die Summe von Z zu K + Y zu K die minimalste ist.

Nur mal als Vermutung gedacht. Keine Ahnung ob das auch besser gehen würde.

 

[kekster]

Deine ersten Anmerkungen bzgl. der Unterschiede vom TSP und Dijkstra sind absolut richtig - und von mir verstanden. Das Thema ist allerdings bereits erledigt, da ich Dijkstra nur genutzt habe, um die Entfernungen der Wegpunkte für das TSP zu berechnen.

Nun zum TSP - und hier hast du mein Problem korrekt erkannt: ich möchte -keine- Rundreise. Unsere Mitarbeiter im Lager sollen lediglich 1 mal die Wegpunkte ablaufen - dabei starten sie an einem fest definierten Wegpunkt (zb Eingang ins Lager) und enden an einem anderen Wegpunkt (zb die Packstraße).

Das heißt: ich möchte keinen "Kreis" bilden und zu meinem ersten Wegpunkt zurück kehren, sondern lediglich alle Wegpunkte 1 mal besuchen mit der Sonderbedingung: "starte bei Z, ende bei Y". Dazu war mein oben genannter Screenshot gedacht. Die Punkte A bis D stellen dabei meine abzulaufenden Wegpunkte im Lager dar. Die Punkte Z und Y (evtl eine blöde Benennung...) stellen dabei den Start- bzw. den Endpunkt fest.

Zielsetzung: suche die kürzeste Route von Z -> [A,B,C,D] -> Y
Dabei sind mir die Entfernungen von Z und Y zu allen Wegpunkten A, B, C, D bekannt.

Ich denke wir haben ein wenig aneinander vorbei geredet - ich hoffe ich konnte das Problem verständlich genug erläutern?

Viele Grüße

 

[Lodorvonhal]

Ok, ich war leicht verwirrt und habe das wohl falsch Verstanden.

Alternativ hatte ich auch schon überlegt die Rundreise komplett wegzulassen. Dann könnte man bei Z starten und per Dijkstra schauen was von der Menge (A B C D) an kürzesten wäre. und somit alle ablaufen und danach zu Y.
Im schlimmsten Fall könnte zwar die Wegfindung optimal sein, nur der Schlussweg zu Y nicht. (ich meine damit das bezogen auf den Zielpunkt Y sicherlich eine andere Route als die reine Wegfindung optimal wäre)


Was ist dem dem Ansatz bezogen auf dein Beispiel aus meinem letzten Post? würde das passen?
Ich denke das würde annähernd ein gutes Ergebnis liefern.

(bezogen auf dein Beispiel)
Als Ansatz würde ich zuerst dein Ameisenalgorithmus auf deine Knoten A,B,C,D anwenden. (folgend als Menge K genannt) Dieser gibt dir den optimalen Weg zwischen diesen 4 Knoten. Dann würde ich schauen wie die Entfernung zwischen Z und allen Knoten und Y und allen Knoten. Bedingung wäre, dass die Verbindung von Z zu K und Y zu K nur so erlaubt ist, als das diese Verbindung "benachbart" wäre. (Für das Beispiel wäre A-B-C-D schon die optimale Route)

https://dl.dropboxusercontent.com/u/34845727/list.JPG

Dies wäre wichtig, da der optimale Weg von K sonst gesprengt würde. Davon müsste man die Kombination wählen, wo die Summe von Z zu K + Y zu K die minimalste ist.

Nur mal als Vermutung gedacht. Keine Ahnung ob das auch besser gehen würde.

 

[Alex Unkreativ]

Hallo kekster,dass es sich nicht um eine Rundreise handelt, macht das Problem leider nicht besser. Jetzt hast du ein Steiner Path Problem, wo ich auch erstmal von der NP-schwere ausgehen würde, weshalb du dir eine Heuristik überlegen solltest. Das Problem liegt darin, dass du die Reihenfolge der Wegpunkte ABCD ja nicht kennst, sonst wäre es simpel zu lösen. Wenn du nur vier hast, dann kannst du auch mit Dijkstra alle durchprobieren, aber bei 20 ist das schon keine Option mehr.

Ich würde es so lösen:
1) Berechne einmalig eine Distanzmatrix, d. h. die kürzesten Wege für je zwei Paare -> All-pairs shortest path problem
2) Jetzt gibt es einen konkreten Auftrag für einen Kommissionierer: Er startet in A und muss in Z abliefern und Waren von I,J,K und L holen.

Schritt 1: Suche in der Distanzmatrix die kürzeste Distanz zwischen je zwei zu erreichenden Knoten, also
(A,I)
(A,J)
...
(J,K)
(J,L)
(K,L)
...
(K,Z)
(L,Z)
Das ist sind quadratisch viele, was bei 20 Stationen kein Problem ist.

Schritt 2: Nun haben wir beispielsweise (I,L) als das Knotenpaar mit kürzester Entfernung gefunden. Die identifizieren wir jetzt als einen Knoten und passen die Distanzen zwischen allen anderen Knoten und dem neuen Knoten "IL". Die neue Distanz für K ist beispielsweise einfach MIN((K,I),(K,L)).

Schritt 3: Das iterieren wir jetzt. Suchen also die nächst kürzeste Distanz. Aufpassen müssen wir, wenn wir drei Knoten vereinen. Da wir einen Pfad und keinen Baum suchen, ist der Mittelknoten nicht mehr erreichbar, sondern nur noch die Außenknoten, weshalb wir alle Distanzen, die bisher auf den Mittelknoten als kürzesten zeigten, nun zu einem Außenknoten "verlängern müssen".
Damit hast du schnell einen recht effizienten Algorithmus zusammengebaut, der zwar keine Optimallösung berechnet, die aber aufgrund der wahrscheinlichen NP-schwere auch nicht zu erwarten ist.

Ich würde auch noch versuchen, daraus eine randomisierte Version zu basteln, die nicht umbedingt die kürzesten Knoten konkateniert, sondern die zwei Knoten randomisiert auswählt. Wenn du einen solchen randomisierten Algorithmus einige Male laufen lässt, bekommst du wahrscheinlich für eine kleine Menge wie 20 fast immer eine Optimallösung.