Fahrzeugrouting- / Ressourcenplanungsalgorithmus Design

https://stackoverflow.com/questions/1925439

20-09-2019
|

Frage

Mein erster Beitrag hier - in der Hoffnung, dass Sie mir bei der Gestaltung eines Algorithmus helfen können, den ich schon seit einiger Zeit in Betracht gezogen habe - nicht sicher, welcher Ansatz zu wählen ist (VRPTW- oder Ressourcenplanung oder etwas ganz anderes!

Um es in ein echtes Wortbeispiel zu setzen, haben wir an einer kleinen Anzahl von Orten eine Menge Gartenabfälle (normalerweise weniger als 5). Der Abfall muss alle innerhalb von Zeitrahmen an andere Standorte transportiert werden. Um den Gartenabfall zu bewegen, haben wir Anhänger, die von Autos abgeschleppt werden müssen. Gartenabfälle können nur zu bestimmten Zeiten (Zeitfenster) im Abfalldepot fallen gelassen werden. An einigen Orten können wir den Anhänger abgeben, um dort von Menschen auszufüllen oder zu entleert, aber an anderen Orten muss der Fahrer des Autos es selbst tun und das Auto muss dort bleiben. Alle Zeiten können berechnet werden (dh Lade- / Entladezeiten, Transitzeiten usw.). Autos können sich zwischen Standorten ohne Anhänger bewegen, Anhänger können leer abgeschleppt werden, aber Anhänger können sich nicht zwischen den Orten bewegen.

Unser Ziel ist es, sicherzustellen

Minimierung der Anzahl der im Gebrauch in verwendeten Anhänger und Autos
Treffen Sie alle Zeitfenster, um Abfall abzugeben
„Ausgleich“ die Trailer - dh am Ende des Tages haben wir an jedem Ort so viele Anhänger wie zu Beginn des Tages dort

Ich dachte daran, dies als Ressourcenplanungsalgorithmus zu nähern, aber ich bin mir nicht sicher, wie ich mit dem „Ausgleich“ von Anhängern umgehen soll.

Eine andere Methode, die ich in Betracht hatte, war, die Autos zuerst zu berücksichtigen. Ich konnte dann die früheste Aufgabe auswählen und danach ein Diagramm aller realisierbaren Aufgaben erstellen. Wenn ich dann den längsten Pfad durch die Grafik auswählen würde, die die maximale Anzahl von Anhängerlasten bedienen würde. Ich konnte diese Aufgaben dann aus der Liste der Aufgaben entfernen und wiederholen, bis alle Aufgaben gewartet wurden. Ich müsste dann diese Liste der Anhängerladungen durchführen, um die Anzahl der erforderlichen Anhänger herauszufinden.

Alle Gedanken über die Herangehensweise wären geschätzt!

Lösung

Ich stimme Jiri zu ... Sie möchten einen heuristischen Algorithmus, der schnell mit einer akzeptablen Lösung schließt und sich dann von dort aus verfeinert.

Ich habe zuvor bei Unternehmen gearbeitet, die zur Routing -Software für Lieferungen verfügten, und der Ansatz, den sie gewählt haben, bestand darin, einen genetischen Algorithmus zu verwenden, um sehr ähnlich, wenn auch viel größeres Problem zu lösen. Nimm a Schau hier Wenn Sie mit dem Ansatz nicht vertraut sind. Von dieser Seite:

Start] erzeugen eine zufällige Population von N -Chromosomen (geeignete Lösungen für das Problem)
Fitness] Bewerten Sie die Fitness f (x) jedes Chromosoms X in der Population
Neue Bevölkerung] schaffen eine neue Bevölkerung, indem sie die folgenden Schritte wiederholen, bis die neue Bevölkerung abgeschlossen ist

Selektion] Wählen Sie zwei übergeordnete Chromosomen aus einer Population nach ihrer Fitness (die bessere Fitness, die größere Chance, ausgewählt zu werden)

Crossover] mit einer Crossover -Wahrscheinlichkeit überqueren die Eltern, um einen neuen Nachkommen (Kinder) zu bilden. Wenn kein Crossover durchgeführt wurde, ist Nachkommen eine genaue Kopie der Eltern.

Mutation] mit einer Mutationswahrscheinlichkeit mutieren neue Nachkommen an jedem Ort (Position im Chromosom).

Akzeptieren] Stellen Sie neue Nachkommen in einer neuen Bevölkerung ein
Ersetzen] Verwenden Sie eine neue generierte Bevölkerung für einen weiteren Algorithmus
Test] Wenn die Endbedingung erfüllt ist, stoppen und geben Sie die beste Lösung in der aktuellen Bevölkerung zurück
Schleife] Weiter mit Schritt 2

Der Trick dafür besteht darin, Ihre Einschränkungen in ein "Chromosom" zu kodieren und die "Fitness" -Funktion zu schreiben. Die Fitnessfunktion muss Eingaben der Ergebnisse einer potenziellen Lösung annehmen und eine Punktzahl darüber ausspucken, wie gut eine Lösung ist, die sie ist, oder sie herauswerfen, wenn sie gegen eine der Einschränkungen verstößt.

Wie von Jiri erwähnt, besteht der Vorteil dieser Lösung, dass sie ein praktikables, wenn auch nicht die beste, sehr schnell beantworten und je länger Sie es laufen lassen, desto besser wird die Lösung.

Andere Tipps

Wir sprechen hier mit Sicherheit über einen NP -vollständigen Algorithmus. Über eine Reihe von Autos und Anhängern wird dies nicht eine Aufgabe sein, bei der Sie aus allen möglichen Lösungen eine beste Lösung erhalten und diese dann entsorgen und wieder gehen können, um das zu vermeiden längster Weg, wie Sie vorschlagen. Wenn Sie Ihren Algorithmus auf diese Weise entwerfen, ist es sehr wahrscheinlich, dass Sie eines Tages ein bisschen mehr Autos und Anhänger hinzufügen und die Lösung nie fertigstellen wird.

Sie möchten wahrscheinlich mit Algorithmus gehen, der vernünftigerweise schnell genug Lösung des Problems erzeugen kann. Vergewissern Sie sich Nehmen Sie die erste Lösung, die metrisch innerhalb der Grenzen hat. Dies hat den zusätzlichen Vorteil, ob dieser Algorithmus zu lange dauert, um zu berechnen, und Sie abbrechen.

Ich bin mir jedoch nicht sicher, welcher Ansatz das Problem selbst annimmt. Ich würde empfehlen, nach der Suche ein paar Artikel zu lesen ACM -Portal. Ich würde annehmen, dass UPS und Fedex wahrscheinlich ähnliche Probleme haben. Wenn Sie sie als Schlüsselwörter zu einer Suche in Google hinzufügen, können Sie einige nützliche Ergebnisse erzielen.

Ich stimme Robert zu. Das klingt für mich wie ein wirklich großartiger Kandidat für eine evolutionäre Optimierungstechnik wie die von ihm beschriebene genetische Algorithmus -Implementierung.

Ich habe auch sehr gute Erfolge bei bestimmten Problemen mit der Partikelschwarmoptimierung (PSO) gehabt. Grundsätzlich können Sie sich jedes Genom als Partikel in einem multi -dimensionalen Raum vorstellen. Die Koordinaten des Partikels sind die Parameter für Ihre Berechnung (Fitnessfunktion). Jedes Teilchen wird zufällig mit einer zufälligen Geschwindigkeit begonnen. Für jede Iteration der Simulation aktualisieren Sie die Position jedes Partikels mit seinem aktuellen Reisevektor und fügen dann Komponenten anderer Vektoren wie: Richtung zum besten Teilchen, Richtung, Richtung zum besten Partikel aller Zeiten, Richtung zu einer lokalen Gruppe Beste usw. ...

Es mag zunächst ziemlich entmutigend erscheinen, einen GA oder PSO zu implementieren, aber ich versichere Ihnen, dass es einfach ist, einen kleinen Rahmen zu schreiben, der den Algorithmus (GA/PSO) aus der tatsächlichen Problemdomäne abstrahiert, die Sie optimieren möchten. Sie können immer auf Wikipedia zurückgreifen, um Einzelheiten zu den Algorithmen zu erhalten.

Sobald ich ein Framework habe, beginne ich normalerweise mit einem 2 Parameterproblem (wahrscheinlich einer Vereinfachung Ihres Problems oder X- und Y -Stellen auf einem Bild), damit ich den Algorithmus leicht visualisieren und optimieren kann, damit ich ein gutes Schwarmverhalten bekomme. Dann skalle ich es zu mehr Dimensionen.

Ich mag diesen Ansatz, weil ich es mir ermöglicht, leicht für Probleme zu optimieren, die ziemlich komplexe und komplizierte Teile für die tatsächliche Problemaussage haben (wie die Autos und Anhänger).

Warum die Evolutionstechniken attraktiv sind, liegt daran, dass Sie der Simulation einen festen Teil der Zeit widmen und die bisher beste Antwort aufnehmen können, wenn Sie sich entscheiden, aufzuhören.

Nach meiner Erfahrung neigen Sie dazu, die Parameter an GA oder PSO zu optimieren (sobald Sie eine Implementierung haben), wie Sie eine hart codierte heuristische Lösung schreiben würden, aber der Vorteil ist, dass die Strategie zum Finden der Lösung normalerweise geändert wird Benötigt nur Parameteränderungen oder tauschen Sie sehr gut definierte Algorithmen mit einer anderen Implementierung aus, anstatt eine völlig andere Strategie zur Lösung des Problems heuristisch von Grund auf neu zu kodieren.

Bitte geben Sie mir einen Schrei, wenn Sie Anleitung zum Entwerfen der generischen Frameworks für einen der beiden Algorithmen benötigen. Ich muss darauf hinweisen, dass Sie dort auch mehrere gute kostenlose Drittanbieter -Frameworks erhalten. Ich mag es manchmal, meine eigenen zu codieren, weil ich dann jeden Aspekt des Algorithmus verstehe und ich weiß, wo ich die Strategie anpassen kann.

Allgemeiner Ansatz:

Da das Problem klein ist, würde ich einen Ansatz vorschlagen, bei dem Sie Autos und Anhänger hinzufügen, bis Sie eine realisierbare Lösung erhalten, anstatt zu versuchen, Autos und Anhänger zu minimieren.

Lösung:

Ich hatte weniger Erfolg mit Gas mit Einschränkungen und noch weniger Erfolg mit Gas mit Einschränkungen für ganzzahlige Variablen (z. B. die Anzahl der Anhänger an einem Ort). Es kann sein, dass die Einschränkungsprogrammierung ein besserer Ansatz ist, da Sie nur eine praktikable Lösung für eine bestimmte Anzahl von Autos und Anhängern erzeugen möchten, anstatt zu versuchen, die zurückgelegte Strecke zu minimieren.

Überwachung:

Sie lösen das Problem in einem Netzwerk, in dem die letzten Bewegungen möglicherweise einen leeren Anhänger verlagern.

Viel Glück !

Lokale Suche sind eine Alternative zu genetischen Algorithmen. In dem Internationaler Zeitplanwettbewerb 2007, lokale Suchalgorithmen (wie Tabu -Suche und simuliertes Tempern) schlagen deutlich die genetischen Algorithmuseinträge (1 bis 4. Platz für LS gegenüber dem 5. Platz für GA in Track 1 von etwa 80 IIRC).

Schauen Sie sich auch einige der Bibliotheken da draußen an, wie z. Optaplanner (Tabu -Suche, simuliertes Glühen, Späte Akzeptanz, Open Source, Java), JGAP (Genetische Algorithmen, Open Source, Java), Opents (Tabu Search, ...

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow