Dimensions

Der Routing-Löser nutzt ein Objekt, eine sogenannte Dimension, Mengen an, die sich entlang der Route eines Fahrzeugs ansammeln, z. B. Fahrzeit oder bei Abhol- und Lieferungen: das Gesamtgewicht, das es transportiert. . Wenn ein Routing-Problem eine solche Menge beinhaltet, entweder in den der Zielfunktion ist, müssen Sie dafür eine Dimension definieren.

In diesem Abschnitt wird erläutert, wie Dimensionen definiert und verwendet werden.

Beispiele für Dimensionen

Hier sind einige Beispiele für Dimensionen aus den vorherigen Abschnitten.

  • Mit dem Beispiel für VRPTW wird eine Dimension für das Tracking erstellt. kumulierte Fahrtzeit jedes Fahrzeugs ermitteln. Der Matherechner verwendet die Dimension, um die Einschränkung, dass ein Fahrzeug nur einen Standort innerhalb der Zeitfenster.

  • Im Beispiel für CVRP wird eine Dimension für die Anforderungen (z.B. Gewicht oder Menge der abzuholenden Pakete), die die die kumulative Last, die das Fahrzeug auf seiner Route trägt. Der Solver nutzt die Dimension, um die Einschränkung zu erzwingen, dass die Last eines Fahrzeugs ihre Kapazität nicht überschreiten darf.

In den folgenden Beispielen wird eine Dimension für das VRPTW mithilfe der Methode AddDimension .

Python

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

C++

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

Java

routing.addDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

C#

routing.AddDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

Die Methode AddDimension hat folgende Eingaben:

  • callback_index: Der Index für den Callback, der die Menge zurückgibt. Die -Index, also der interne Verweis des Solver zum Callback, wird durch wie RegisterTransitCallback oder RegisterUnitaryTransitCallback.
  • slack_max: Maximum für den Leerlauf (Slack), eine Variable, die für Wartezeiten steht Uhrzeiten an den Orten. Siehe Slack-Variablen unten für Informationen zu Details. Wenn das Problem keine Wartezeit beinhaltet, können Sie in der Regel slack_max festlegen. auf 0 gesetzt.
  • capacity: Maximum für die entlang jeder Route akkumulierte Gesamtmenge. Verwenden Sie capacity, um Einschränkungen wie die im CVRP Wenn Ihr Problem nicht über können Sie für capacity einen Wert festlegen, der groß genug ist, keine Einschränkungen für die Routen auferlegen, z. B. die Summe aller Einträge der Matrix oder des Arrays, die zur Definition des Callbacks verwendet werden.
  • fix_start_cumulative_to_zero: Boolescher Wert. Falls wahr, der kumulierte Wert beginnt bei 0. In den meisten Fällen sollte dieser Wert auf True festgelegt werden. Für die VRPTW oder Probleme mit Ressourceneinschränkungen, einige Fahrzeuge möglicherweise aufgrund von Zeiteinschränkungen nach der Zeit 0 beginnen müssen, daher sollten Sie fix_start_cumulative_to_zero für diese Probleme auf False festlegen.
  • dimension_name: String für den Namen der Dimension, z. B. 'Distance' mit dem Sie an anderer Stelle im Programm auf die Variablen zugreifen können.

Das CVRP-Programm erstellt mithilfe der Funktion AddDimensionWithVehicleCapacity . Diese Methode verwendet ein Array von Kapazitäten mit einem Eintrag für jedes Fahrzeug. (Im Gegensatz dazu verwendet AddDimension einen einzelnen Wert für capacity, sodass alle wird davon ausgegangen, dass die Fahrzeuge die gleiche Kapazität haben.)

Weitere Informationen finden Sie in der RoutingModel. für andere Methoden zum Erstellen von Dimensionen.

Der Abschnitt Zeitfenster für die Lösung in einer Liste oder einem Array speichern stellt Funktionen zum Speichern der kumulativen Daten in einer Dimension in einer Liste oder einem Array dar.

Slack-Variablen

Hier ist ein Beispiel, das Slack-Variablen für ein Problem mit Reisezeit. Angenommen, ein Fahrzeug in einem Schritt seiner Route von Ort i zu Ort J bewegt, und dass

  • Die kumulierte Fahrtzeit des Fahrzeugs bei i beträgt 100 Minuten.
  • Die kumulierte Fahrzeit des Fahrzeugs bei j beträgt 200 Minuten.
  • Die Fahrzeit von i nach j beträgt 75 Minuten.

Das Fahrzeug kann den Ort nicht sofort nach der Ankunft oder nicht sofort verlassen. an Ort j 175. Stattdessen muss das Fahrzeug 25 Minuten Ort i vor der Abreise; mit anderen Worten, das Spiel beträgt an Position i 25.

Sie müssen das Spielraum in einem VRPTW zulassen, da Fahrzeuge möglicherweise warten müssen, bevor aufgrund von begrenzten Zeitfenstern nicht besucht. Stellen Sie bei einem solchen Problem slack_max bis zur maximalen Wartezeit von Fahrzeugen nach einem Standort suchen, bevor Sie mit dem nächsten fortfahren. Wenn es keine Rolle spielt, wie lange warten Sie. Setzen Sie einfach slack_max auf eine sehr hohe Zahl.

Für den CVRP hingegen ist die Änderung der akkumulierten Last von i zu j entspricht immer dem Bedarf um i, also gibt es kein Spiel. Bei Problemen wie setzen Sie slack_max auf 0.

Als Nächstes geben wir die formale Definition von Slack. Intern speichert eine Dimension zwei Typen von Variablen, die sich auf Mengen beziehen, die sich entlang der Routen ansammeln:

  • Variablen für öffentliche Verkehrsmittel: Die Erhöhung oder Verringerung der Menge in jedem Schritt eine Route berechnen. Wenn i -> j ein Schritt in einer Route ist, ist die Variable für öffentliche Verkehrsmittel entweder i, j-Eintrag der Transit-Matrix (für einen Transit-Callback) oder einfach den Callback-Wert an Standort i (wenn der Callback von nur einem Standort abhängt).
  • Kumulative Variablen: Die an jedem Standort akkumulierte Gesamtmenge. Ich auf die kumulative Variable an Position i zugreifen, dimension_name.CumulVar(i) Ein Beispiel finden Sie in der Zeitfenstereinschränkungen im VRPTW-Beispiel an.

Wenn ein Fahrzeug in einem Schritt von Standort i zu Standort j fährt, hängt mit diesen Variablen zusammen: 

slack(i) = cumul(j) - cumul(i) - transit(i, j)

Weitere Informationen zu Dimensionen finden Sie unter RoutingDimension im Referenzabschnitt.