Algorithmus zur Spaltengenerierung

Question

Ich möchte einen VRP mit einem Spaltengenerierungsalgorithmus lösen. Das Ziel des Problems ist die Minimierung der Makespan. Es ist jedoch sinnvoll, die Ankunftszeit des Fahrzeugs in jedem Knoten zu berechnen. Das Fahrzeug muss mit einem anderen Transportmittel wie einem Zug synchronisiert werden, dessen Route vor dem Lösen des oben genannten VRP vorgegeben ist. Der Zug kann von einigen Knoten fahren, an denen das Fahrzeug vorbeifährt, und in diesen Knoten ist die Ankunftszeit maximal der Ankunftszeit von Zug und Fahrzeug. Ich möchte wissen, wie ich das Preisproblem lösen soll.

Answer 1

Wenn ich Ihr Problem richtig verstanden habe, besteht der einzige Unterschied zur ursprünglichen Version (ohne Zug) darin, dass die Zeitfunktion nicht additiv ist.

Nehmen wir zum Beispiel an, der Zug fährt durch den Knoten $j$ zur (gegebenen) Zeit $t_j$und Sie berechnen einen Pfad $p$ dessen letzter Knoten ist $i$. Die auf diesem Pfad akkumulierte Gesamtzeit wird mit bezeichnet$\tau_p(i)$. $\Delta t_{ij}$ bezeichnet die Zeit, die das Fahrzeug benötigt, um loszufahren $i$ zu $j$. Wenn Sie den Pfad erweitern und einen Knoten hinzufügen möchten$j$, dann die gesamte akkumulierte Zeit für den Pfad $p$, $\tau_p$wird wie folgt erhöht: $$ \tau_p(j) := \max\{ t_j, \tau_p(i) + \Delta t_{ij} \} $$

Wenn der Zug vor dem Fahrzeug ankommt, nimmt die gesamte akkumulierte Zeit Wert $\tau_p(i) + \Delta t_{ij}$Andernfalls nimmt es Wert $t_j$.

Beachten Sie, dass dies wie Zeitfenster auf Ihren Zugknoten mit nur einer Untergrenze ist: Sie können einfach Zeitfenster hinzufügen $[t_j, +\infty[$ auf Knoten $j$ und führen Sie Ihren Algorithmus für den kürzesten Pfad mit Zeitfenstern aus (falls Sie einen zur Hand haben).

Mit anderen Worten, die (Zeit-) Ressourcenerweiterungsfunktion ist nicht additiv. Dies wird zum Beispiel von cspy erledigt , einer großartigen Python-Bibliothek, die kürzeste Pfade mit Ressourcenbeschränkungen berechnet, in die Sie Ihre eigene angepasste Ressourcenerweiterungsregel eingeben können ( lesen Sie die Dokumente, in denen ein solches Beispiel angegeben ist). VRPy , eine VRP-Python-Bibliothek für VRP, verwendet cspy , um die kürzesten Pfade für die Spaltengenerierung zu berechnen. Da VRPy Zeitfenster verwaltet, haben Sie einen guten Ausgangspunkt!