Branchen- und Preisalgorithmus

Question

Können Branch und Price ein guter Lösungsansatz für ein Routing-Problem mit Min-Max-Zielfunktion sein? Zum Beispiel Minimieren der maximalen Länge einer Fahrzeugroute in einem VRP.

In der Literatur habe ich noch nie gesehen, dass dieser Lösungsansatz zur Lösung eines solchen Problems verwendet wurde. Soweit ich weiß, wird dieser Ansatz verwendet, um VRPs zu lösen und die Gesamtkosten zu minimieren.

Answer 1

Ein guter oder schlechter Ansatz hängt von mehreren Faktoren ab, zum Beispiel:

• die Größe der Instanzen
• Zeit zur Verfügung, um eine Lösung zu finden (dies ist in der Regel eine wichtige Angelegenheit bei Fahrzeugrouting-Anwendungen)
• Rechenleistung
• Welches Niveau der Lösungsqualität gilt als gut genug

Sehen Sie sich diese Arbeit von Yu, Nagarajan und Shen zum minimalen Makespan-VRP mit Kompatibilitätsbeschränkungen an, da es sich um ein ähnliches Problem handelt, das untersucht wurde, bevor Branch-and-Price als Ansatz zur Lösung einer Makespan-VRP-Variante verwendet wurde. Es hat ganz gut funktioniert. Beachten Sie, dass sie in ihrem Fall einen Approximationsalgorithmus entwickelt haben, um die B & P-Ausführungszeit zu beschleunigen.

Ich schlage folgendes Experiment vor:

Erster Schritt: Folgen Sie der Antwort von @ RobPratt auf Ihre vorherige Frage zur Makespan-Minimierung in VRP :

Lassen $d_i$ die Nachfrage nach Kunden sein $i\in N$, Lassen $V=\{1,\dots,K\}$ sei die Menge der Fahrzeuge und lass $P$ Dies ist die Menge von Spalten, wobei jede Spalte einer möglichen Untertour ausgehend vom Depot mit Bogenvariablen entspricht $x_{i,j}$ und Knotenvariablen $y_i$. Lassen$z$sei die Makespan. Das Master-Problem ist vorbei$z$ und $\lambda$ist wie folgt, mit zwei Variablen in Klammern: \ begin {align} & \ text {minim} & z \\ & \ text {vorbehaltlich} & z - \ sum_ {p \ in P} \ left (\ sum_ {i, j } c_ {i, j} x_ {i, j} ^ p \ right) \ lambda ^ p_v & \ ge 0 && \ text {for$v\in V$} && (\ pi_v \ ge 0) \\ && \ sum_ {v \ in V} \ sum_ {p \ in P} y_i ^ p \ lambda ^ p_v & \ ge 1 && \ text {for $i\in N$} && (\ text {$\alpha_i \ge 0$}) \\ && - \ sum_ {p \ in P} \ lambda ^ p_v & \ ge -1 && \ text {for $v\in V$} && (\ text {$\beta_v \ge 0$}) \\ && \ lambda ^ p_v & \ ge 0 && \ text {for $v\in V$ und $p\in P$} \ end {align}

Das Teilproblem der Spaltengenerierung ist vorbei $x$ und $y$ für jede $v\in V$ ist dann die reduzierten Kosten von zu minimieren $\lambda^p_v$. Das heißt, minimieren$$\pi_v \sum_{i,j} c_{i,j} x_{i,j} - \sum_{i \in N} \alpha_i y_i + \beta_v$$ vorbehaltlich $(x,y)$ Bildung einer möglichen Subtour ausgehend vom Depot mit $\sum_i d_i y_i \le L$, wo $L$ ist die Kapazität jedes Fahrzeugs.

Wie dort angegeben, kann das Teilproblem als kürzester Elementarpfad umformuliert werden: Teilen Sie das Depot in eine Quelle und eine Senke auf und verschieben Sie die Knotengewichte in die Bögen: $\pi_v c_{i,j}−\alpha_i$ für das Gewicht des Lichtbogens $(i,j)$ im elementaren Teilproblem des kürzesten Weges.

Zweitens: Implementieren Sie die obige Methode. Ich empfehle, VRPy zu verwenden, wie von Kuifje hier vorgeschlagen . Auf diese Weise müssen Sie nicht alle Filial- und Preisoperationen von Grund auf neu implementieren. Detaillierte Schritte:

1. Schauen Sie sich die Projektdokumentation an.
2. Schauen Sie sich den Code in GitHub an.
3. Erstellen Sie einen Fork oder laden Sie das Projekt als .zip herunter, damit Sie Änderungen lokal vornehmen können.
4. Ändern Sie den Code bezüglich des Teilproblems so, dass das Depot wie oben erläutert aufgeteilt wird.
5. Führen Sie die Experimente aus. Sie können den Beispielinstanzen aus der Dokumentation wie hier und hier folgen .
6. Lassen Sie uns wissen, wie es funktioniert hat. Denken Sie auch daran, VRPy und seine Entwickler in Ihrer Arbeit anzuerkennen (sei es ein Projektbericht, eine Abschlussarbeit, eine Veröffentlichung usw.) und die Bedingungen in der Lizenz der Bibliothek in Bezug auf Änderungen zu beachten.

Answer 2

VRPy (v0.3.0) unterstützt jetzt diese Option: Alles, was Sie tun müssen, ist die minimize_global_spanOption festzulegen , Truewenn Sie das VehicleRoutingProblemObjekt instanziieren :

prob = VehicleRoutingProblem(G, num_vehicles=2, minimize_global_span=True)
prob.solve()

Natürlich dein Graph $G$ muss in erster Linie gut definiert sein.

Die von @RobPratt vorgeschlagene Formulierung ist implementiert. Wenn Sie mit einigen Spielzeugproblemen herumspielen, werden Sie feststellen, dass die Formulierung im Vergleich zur klassischen (ohne Makespan) schwach ist. Es ist leicht zu erkennen, dass die Einschränkung$$ z - \sum_{p\in P} \left(\sum_{i,j} c_{i,j}x_{i,j}^p\right) \lambda^p_v \ge 0 \quad \text{ for $v \ in V.$} $$ ist dafür verantwortlich.

Sie können auch den folgenden alternativen Ansatz ausprobieren:

1. Lösen Sie das Problem ohne die Option min_max

2. Fragen Sie die größte Spanne ab

3. Lösen Sie erneut ohne min_max, aber beschränken Sie das Problem so, dass jede Route eine kleinere Spanne hat als die größte, die in 2 abgefragt wird.

4. Wenn nicht möglich, stoppen Sie, andernfalls fahren Sie mit Schritt 2 fort.

All dies ist mit dem Ökosystem von VRPy unkompliziert. Habe Spaß.