サイズ

ルーティング ソルバーは、ディメンションと呼ばれるオブジェクトを使用して、車両のルートに沿って累積された量を追跡します。たとえば、移動時間や、車両が集荷や配達を行っている場合は、車両の総重量を追跡します。制約の問題や目的関数において、こういった問題が数量の問題に関係している場合は、ディメンションを指定して定義する必要があります。

このセクションでは、ディメンションを定義して使用する方法について説明します。

ディメンションの例

前のセクションのディメンションの例を次に示します。

  • VRPTW の例は、各車両の累積移動時間を追跡するディメンションを作成します。ソルバーは、このディメンションを使用して、車両が位置の時間範囲内にしか移動できないという制約を適用します。

  • CVRP の例では、需要（例: ピックアップする重量や数量）のディメンションが作成されます。これにより、車両が経路に沿って積み重ねている累積負荷が追跡されます。ソルバーは、このディメンションを使用して、車両の負荷が容量を超えないようにする制約を適用します。

下記の例では、AddDimension メソッドを使用して VRPTW のディメンションを定義します。

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)

AddDimension メソッドには次の入力があります。

  • callback_index: 数量を返すコールバックのインデックス。コールバックは、コールバックのソルバー内部参照である RegisterTransitCallback や RegisterUnitaryTransitCallback などのメソッドによって作成されます。
  • slack_max: slack の最大値。その場所の待ち時間を表す変数です。詳しくは、以下の slack 変数をご覧ください。問題が待機時間を含まない場合は、通常 slack_max を 0 に設定します。
  • capacity: 各ルートで蓄積される合計量の最大値。capacity を使用して、CVRP のような制約を作成します。問題にこのような制約がない場合は、コールバックの制限に使用されるマトリックスまたは配列のすべてのエントリの合計など、ルートに制限を課すのに十分な値に capacity を設定できます。
  • fix_start_cumulative_to_zero: ブール値。true の場合、数量の累積値は 0 から始まります。ほとんどの場合、これは True に設定する必要があります。ただし、VRPTW やリソースの制約に関する問題の場合、時間枠の制約により、一部の車両は 0 以降に開始しなければならない場合があります。このような問題では、fix_start_cumulative_to_zero を False に設定する必要があります。
  • dimension_name: ディメンションの名前の文字列（例: 'Distance'）。プログラムの他の場所で変数にアクセスするために使用できます。

CVRP プログラムは、AddDimensionWithVehicleCapacity メソッドを使用して、わずかに異なるタイプのディメンションを作成します。このメソッドは、各車両に対応するエントリを 1 つ持つ、さまざまな配列の配列を取得します。 （対照的に、AddDimension は capacity に対して単一の値を受け取るため、すべての車両が同じ容量であると想定されます）。

ディメンションを作成するその他の方法については、RoutingModel のリファレンス ページをご覧ください。

ソリューションの時間枠をリストまたは配列に保存するセクションには、リストまたは配列のディメンションに累積データを保存する関数が記載されています。

Slack 変数

以下に、移動時間に関連する問題の slack 変数を示す例を示します。ルートの 1 ステップで車両がロケーション i からロケーション j に移動したとします。

  • i での車両の累積走行時間は 100 分です。
  • 車両の j での累積移動時間は 200 分です。
  • i から j までの移動時間は 75 分です。

到着時に車両が現在地 i を出発できません。位置情報 j の累積時間は 175 になります。その場合、車両は出発前に位置情報 i で 25 分待機する必要があります。つまり、位置情報 i のたるみは 25 分です。

VRPTW では、時間枠の制約のため、車両が場所を訪れるまで待機しなければならない場合があるため、たるみを許容する必要があります。このような問題が生じた場合は、slack_max に、車両がある場所まで待機してから次の場所に移動できるようにする最大時間を設定します。待機時間に関係なく、slack_max を非常に大きな値に設定します。

一方、CVRP では、累積負荷の i から j への変化は常に i の需要と等しいため、たるみはありません。このような場合は、slack_max を 0 に設定します。

次に、Slack の正式な定義を紹介します。内部的に、ディメンションには経路に沿って蓄積される数量に関連する 2 種類の変数が格納されます。

  • 交通機関の変数: ルートの各ステップでの数量の増減。i -> j がルート内の 1 ステップである場合、交通機関変数は、交通機関マトリックスの i または j エントリ（交通機関のコールバックの場合）、または場所 i のコールバック値のいずれかになります（コールバックが 1 つの場所のみに依存している場合）。
  • 累積変数: 各地域の累積数量。累積変数にはロケーション i の dimension_name.CumulVar(i) でアクセスできます。例については、VRPTW の例の期間の制約をご覧ください。

あるステップで車両が場所 i から場所 j に移動した場合、スラックは次のように変数に関連付けられます。 

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

ディメンションの詳細については、リファレンス セクションの RoutingDimension をご覧ください。