Abmessungen

Die Routenlösung verwendet ein Objekt, das als Dimension bezeichnet wird, um Werte zu erfassen, die sich entlang der Route eines Fahrzeugs ansammeln, z. B. die Fahrtzeit oder – wenn das Fahrzeug Abholungen oder Lieferungen durchführt – das Gesamtgewicht. Wenn ein Routingproblem eine solche Menge umfasst, müssen Sie entweder in den Einschränkungen oder in der Zielfunktion eine Dimension definieren, um sie anzugeben.

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

Beispiele für Dimensionen

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

  • Im VRPTW-Beispiel wird eine Dimension erstellt, mit der die kumulative Fahrtzeit jedes Fahrzeugs erfasst wird. Der Resolver verwendet die Dimension, um die Einschränkung zu erzwingen, dass ein Fahrzeug einen Standort nur innerhalb des Zeitfensters besuchen kann.

  • Im CVRP-Beispiel wird eine Dimension für die Anforderungen (z.B. Gewichte oder Volumen von Paketen, die abgeholt werden müssen) erstellt, die die kumulative Last erfassen, die das Fahrzeug entlang seiner Route transportiert. Der Resolver verwendet die Dimension, um die Einschränkung zu erzwingen, dass die Last eines Fahrzeugs seine Kapazität nicht überschreiten darf.

In den folgenden Beispielen wird eine Dimension für den VRPTW mit der Methode AddDimension definiert.

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. Der Index, der die interne Referenz des Resolvers auf den Callback ist, wird durch Methoden wie RegisterTransitCallback oder RegisterUnitaryTransitCallback erstellt.
  • slack_max: Maximum für slack, eine Variable, die die Wartezeit an den Standorten darstellt. Weitere Informationen finden Sie unten im Abschnitt Slack-Variablen. Wenn das Problem keine Wartezeit umfasst, können Sie slack_max normalerweise auf 0 festlegen.
  • capacity: Maximum für die Gesamtmenge der Routen. Verwenden Sie capacity, um Einschränkungen wie in der CVRP zu erstellen. Wenn Ihr Problem keine solche Einschränkung hat, können Sie capacity auf einen Wert setzen, der ausreichend groß ist, um keine Einschränkungen für die Routen festzulegen, z. B. die Summe aller Einträge der Matrix oder des Arrays, die zum Definieren des Callbacks verwendet werden.
  • fix_start_cumulative_to_zero: Boolescher Wert. Wenn wahr, beginnt der kumulative Wert der Menge bei 0. In den meisten Fällen sollte sie auf True gesetzt sein. Bei VRPTW oder Problemen mit Ressourcenbeschränkungen müssen einige Fahrzeuge jedoch möglicherweise aufgrund von Zeitfensterbeschränkungen nach 0 starten. Legen Sie daher für diese Probleme fix_start_cumulative_to_zero auf False fest.
  • 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.

Im CVRP-Programm wird mit der Methode AddDimensionWithVehicleCapacity eine etwas andere Art von Dimension erstellt. Diese Methode verwendet ein Array von Kapazitäten mit einem Eintrag pro Fahrzeug. Im Gegensatz dazu nimmt AddDimension für capacity einen einzelnen Wert an, sodass angenommen wird, dass alle Fahrzeuge die gleiche Kapazität haben.

Auf der Referenzseite zu RoutingModel finden Sie weitere Methoden zum Erstellen von Dimensionen.

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

Slack-Variablen

Das folgende Beispiel veranschaulicht Slack-Variablen für ein Problem mit der Reisezeit. Angenommen, ein Fahrzeug fährt in einem Schritt seiner Route von Standort i zu Standort j. Es gilt Folgendes:

  • Die kumulative Fahrtzeit des Fahrzeugs in i beträgt 100 Minuten.
  • Die kumulative Fahrtzeit des Fahrzeugs bei j beträgt 200 Minuten.
  • Die Fahrtzeit von i bis j beträgt 75 Minuten.

Das Fahrzeug kann den Standort i nicht sofort bei Ankunft verlassen, sonst wäre die kumulative Zeit am Standort j 175. Stattdessen muss das Fahrzeug 25 Minuten am Standort i warten, bevor es losfährt. Das heißt, der Slack-Standort bei Standort i beträgt 25 Minuten.

Sie müssen Slack in einem VRPTW zulassen, da Fahrzeuge aufgrund von Zeitfensterbeschränkungen möglicherweise warten müssen, bevor sie einen Ort besuchen. Legen Sie in einem solchen Problem slack_max auf die maximale Zeit fest, die Fahrzeuge an einem Ort warten dürfen, bevor sie zum nächsten Standort wechseln. Wenn es nicht wichtig ist, wie lange sie warten, legen Sie für slack_max einfach eine sehr große Zahl fest.

Bei CVRP hingegen entspricht die Änderung der akkumulierten Last von i zu j immer der Nachfrage bei i, sodass es kein Slack gibt. Für Probleme wie dieses können Sie slack_max auf 0 festlegen.

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

  • Transitvariablen: Die Erhöhung oder Verringerung der Menge bei jedem Schritt einer Route. Wenn i -> j ein Schritt in einer Route ist, ist die Variable für öffentliche Verkehrsmittel entweder der i- oder j-Eintrag der Transitmatrix (für einen Callback für öffentliche Verkehrsmittel) oder einfach der Callback-Wert am Standort i (wenn der Callback nur von einem Standort abhängt).
  • Kumulative Variablen: Die Gesamtmenge an jedem Standort. Sie können über dimension_name.CumulVar(i) auf die kumulative Variable an Standort i zugreifen. Ein Beispiel finden Sie unter Zeitbeschränkungen im Beispiel VRPTW.

Wenn ein Fahrzeug in einem Schritt vom Standort i zum Standort j wechselt, hängt das Slack so mit diesen Variablen zusammen: 

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

Weitere Informationen zu Dimensionen finden Sie unter RoutingDimension im Referenzabschnitt.