メインコンテンツまでスキップ

車両のスラック

輸配送計画問題（VRP）の文脈において、スラック（一般的に待機時間とも呼ばれます）とは、車両とドライバーが訪問先で過ごさなければならない非生産的なアイドルタイムのことです。

この待機時間は、車両が訪問先のサービス時間枠が始まる前に到着したときに発生します。

スラックが発生する場所：具体例​

ある車両が「顧客B」への配送を行うと想像してください。顧客Bの時間枠は午前9:00～午前11:00です。

  • 車両到着： 午前8:40
  • 最も早いサービス開始時間： 午前9:00（時間枠の開始）
  • サービス開始： 午前9:00
  • 結果として生じるスラック： 午前8:40（到着）から午前9:00（サービス開始）までの20分間がスラックです。ドライバーは待機しなければなりません。

目的：スラックが主要な指標である理由​

スラックは、総ソリューションコストの重要な構成要素です。アイドル状態の車両とドライバーは、ビジネスにとって現実世界のコスト（ドライバーの賃金、車両の非稼働）を意味します。

オプティマイザーの目標は、単に移動時間を最小化することだけでなく、総コストを最小化することです。スラックにコストを割り当てることで、オプティマイザーにドライバーの時間を評価させ、ルート効率が良いだけでなく、運用効率も良いソリューションを見つけさせることができます。

オプティマイザーがスラックをどう扱うか：コストのトレードオフ​

オプティマイザーはスラックを「無料」の時間とは見なしません。システムに待機に対する人工的なコスト（例：スラック1分あたり10単位のコスト）を設定します。このコストは、総ソリューションコストに組み込まれます。

総ソリューションコスト = 移動コスト + 車両コスト + ペナルティコスト + スラックコスト

これにより、オプティマイザーは賢明なトレードオフを行います。他のどの代替案よりも安価である場合にのみ、スラックを許容します。

トレードオフの例：

オプティマイザーが訪問先Aと訪問先Bをサービスするための2つの可能なルートを評価しているとします。

  • 選択肢1：スラックを発生させる

    • ルート：訪問先A -> 訪問先B
    • 移動時間：30分
    • 待機時間：訪問先Bで25分のスラック。
    • 総コスト： コスト(30分の移動) + コスト(25分のスラック)

  • 選択肢2：スラックを回避する

    • ルート：訪問先A -> （長く、間接的なルート） -> 訪問先B
    • 移動時間：60分（ドライバーは道路上で「時間をつぶし」、訪問先Bに時間通りに到着する）。
    • 待機時間：0分のスラック。
    • 総コスト： コスト(60分の移動)

結果： コスト(25分のスラック)が選択肢2の追加の30分の移動のコストよりも低い場合、オプティマイザーは選択肢1を選択します。訪問先で待機する方が、長いルートで燃料と時間を無駄にするよりも安価であると正しく判断します。

主要原則：待機コストの設定​

待機コスト（スラックの分/時間あたりのコスト）は、強力なチューニングパラメータです。

  • 高い待機コストを設定する： オプティマイザーに「ドライバー/車両の時間は非常に価値がある。何としても待機を避けよ。スラックを防ぐためなら、車両がより長いルートを取るか、別の車両を使用する方がましだ」と伝えます。
  • 低い（またはゼロの）待機コストを設定する： オプティマイザーに「待機は無料だ。移動距離と使用車両数を最小化する限り、ドライバーがどれだけアイドル状態でも構わない」と伝えます。

このコストのバランスを取ることが、机上で効率的であり、かつ現実世界で実用的なルートを作成する鍵となります。

ヒント

厳格な最大スラック制限を課すと、受け入れられるソリューションの数が減少し、以下の結果につながる可能性があります。

  • ソルバーが制約を満たす初期解を見つけられない。
  • 拒否されるブッキングの増加。

他のコストとのトレードオフとしてのスラックの最適化​

Stateless APIでは、オプティマイザーがスラック時間をコストとして扱うように設定できます。これは、ドライバーの休憩をサポートしつつスラックの最小化を可能にする新しい局所探索実装によって実現されます。これにより、距離が短いだけでなく、ドライバーのアイドルタイムを最小限に抑えることで運用効率も高いルートの作成が促進され、より良い労働時間と実現可能性の高い計画につながります。

スラックの最適化を有効にするには、リクエストペイロードで以下のパラメータを設定する必要があります。

  1. ロジスティクスモードの有効化：model_parameters.path_constraints_modeを"logistics"に設定します。このモードは、スラックのコスト計算機能を有効にします。
  2. 車両ごとのスラック最適化の有効化：スラックを最小化したい各車両に対して、logistics_optimize_slackをtrueに設定します。
  3. スラックコストの設定（任意）：model_parameters.slack_cost_factorを使用して、スラックの「コスト」を調整できます。これは目的関数におけるスラック時間の係数です。値を高くすると、オプティマイザーはスラックを削減するためにより一層努力し、その結果として移動距離が長くなる可能性があります。デフォルト値は10で、典型的な範囲は0.1から1000です。
注意

trip_costパラメータはlogisticsパス制約モードと互換性がなく、有効にしても機能しません。

設定例​

注記

この設定は、一部の選択されたSWATソルバーでのみ機能し、デフォルトでは利用できません。

以下は、node_schedulerリクエストでこれらのパラメータを設定する方法を示すJSONスニペットです。この例では、エージェントID dc1e... を持つ車両のスラックタイムが最小化されます。

{
  "engine_settings": {
    "model_parameters": {
      "path_constraints_mode": "logistics",
      "slack_cost_factor": 10
    },
    "calculation_parameters": {
      "scheduling_mode": "prebook_cvrptw"
    }
    // ... その他の設定
  },
  "vehicles": [
    {
      "agent_id": "dc1e0000-2024-0731-aaaa-5206f1c21d09",
      "logistics_optimize_slack": true
      // ... その他の車両プロパティ
    }
  ]
  // ... その他のリクエストプロパティ
}