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

CVRPTW vs. PDP スケジューリングモード (CVRPTW vs. PDP Scheduling Modes)

Stateless Optimization API は、prebook_cvrptw と prebook (PDP) という2つの異なるスケジューリングモードを提供することにより、車両ルーティング問題 (VRP) の2つの主要なクラスを解決するように設計されています。各モードは特定の運用ワークフローに合わせて調整されており、正しいモードを選択することは、効率的で正確な最適化結果を達成するために重要です。

これらのモードは、リクエストの engine_settings.calculation_parameters.scheduling_mode フィールドで構成されます。

PDP (ピックアップおよびドロップオフモード)​

prebook モードは、時間枠付きピックアップおよび配達問題 (PDPTW) をモデル化します。これは最も柔軟で汎用的なモードです。

ワークフロー (Workflow)​

PDP モデルでは、車両のルートは、ピックアップとドロップオフの混合シーケンスで構成できます。車両は空で開始し、複数の場所から商品をピックアップし、いくつかの配達を行い、さらに商品をピックアップし、というようにすることができます。これは、車両の積載量がルート全体で動的に変化する、宅配便サービス、オンデマンド輸送、または小口トラック輸送 (LTL) などの複雑なロジスティクスシナリオを正確にモデル化します。

需要モデリング (Demand Modeling)​

車両にかかる変化する負荷を正しくモデル化するために、需要は次のように扱われます。

  • ピックアップノード: 正の demand 値を持ち、アイテムが車両に積み込まれ、その負荷が増加することを表します。
  • ドロップオフノード: 負の demand 値を持ち、アイテムが降ろされ、車両の負荷が減少することを表します。

利点と制限 (Benefits and Limitations)​

  • 利点:
    • 高い柔軟性: ピックアップとドロップオフが交互に行われる複雑なマルチトリップルートをモデル化できます。
    • 汎用性: ロジスティクスから旅客輸送まで、幅広いユースケースに適しています。
  • 制限:
    • 計算負荷が高い: 柔軟性が高いということは、ソルバーが探索する問題空間がはるかに大きくなることを意味し、特にノード数が多い問題では計算時間が長くなる可能性があります。

CVRPTW モード​

prebook_cvrptw モードは、古典的な 時間枠付き容量制約車両ルーティング問題 (CVRPTW) 向けに高度に最適化されたモデルです。

ワークフロー (Workflow)​

このモードは、より単純で一般的な配送モデル向けに設計されています。車両は単一の中心的な場所（デポや配送センターなど）で開始し、その日のすべての商品をピックアップしてから、ドロップオフのみで構成されるルートを実行します。また、その逆をモデル化することもできます。空で開始し、単一の目的地に戻る前に複数のピックアップを行う車両です。

各車両は、最適化実行ごとに1回のトリップに制限されています。

重要な要件

prebook_cvrptw モードが正しく機能するには、各車両に、デポノード（point ノード）をルートの開始点として明示的に設定する partial_route が定義されている 必要があります。これがないと、ソルバーはデポ開始を想定せず、無効または予期しないルートを生成する可能性があります。

"vehicles": [
    {
        "agent_id": "vehicle-1",
        "partial_route": ["node-depot"],
        ...
    }
]

需要モデリング (Demand Modeling)​

このモードでは、需要ロジックが簡素化されています。

  • すべてのノード: 正の demand 値を持ちます。
  • ソルバーは、車両が割り当てられたすべてのドロップオフノードの総需要を完全に積載してデポからルートを開始すると想定します。その後、車両の負荷は各停留所で減少します。

利点と制限 (Benefits and Limitations)​

  • 利点:
    • 高度に最適化: ソルバーはすべてのピックアップリクエストを単一の概念的なポイントに結合し、問題の複雑さを大幅に軽減します。
    • 高速パフォーマンス: この複雑さの軽減により、PDP モードと比較して計算時間が大幅に短縮され、大規模なラストマイル配送シナリオに最適です。
    • 機能サポート: 配送優先順位付けのための groups_order などの特定の高度な機能は、このモード専用に設計されており、このモードでのみ機能します。
  • 制限:
    • 柔軟性が低い: シングルトリップ、デポからドロップオフ（またはピックアップからデポ）のワークフローのみをサポートします。交互に行われるピックアップとドロップオフはモデル化できません。

主な違いの概要 (Key Differences at a Glance)​

機能prebook (PDP)prebook_cvrptw (CVRPTW)
ワークフロー任意の順序での複数のピックアップとドロップオフ単一のデポ開始、その後に複数のドロップオフ
車両トリップ複数のトリップを実行可能車両ごとに単一のトリップに制限
需要モデルピックアップは +、ドロップオフは -常に +; 車両は満杯で開始
パフォーマンスより遅く、より複雑より速く、高度に最適化
partial_routeオプション開始デポを定義するために 必須
機能互換性汎用groups_order 優先順位付けなどの機能に必要

これらの違いを理解することで、運用上のニーズに最も適した scheduling_mode を選択し、最適化エンジンから最も効率的な結果を得ることができます。

プレイグラウンド (Playground)​

PDP モード​

以下のプレイグラウンドを使用して、PDP スケジューリングモードを試すことができます。

Loading...

CVRPTW モード​

以下のプレイグラウンドを使用して、CVRPTW スケジューリングモードを試すことができます。

Loading...