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

オンデマンドルーティングと運用 (On demand routing and operations)

車両ルーティング問題 (VRP) におけるオンデマンド運用とは、顧客のリクエスト（注文）が事前にわかっているのではなく、リアルタイムで動的に発生するシナリオを指します。これは、通常すべての注文が事前にわかっていると想定される従来の VRP モデルとは対照的です。

ヒント

このユースケースは、オンデマンドサービスの最も典型的なユースケースである乗客の移動を中心にしていますが、ロジスティクスなどの他の業界のライブ注文管理にも適用できます。

オンデマンド VRP の主な特徴:

  • 動的リクエスト: 顧客は、運用期間中にさまざまな配達場所と要件で注文を行います。
  • リアルタイムの意思決定: システムは、新しい着信注文に反応し、車両ルートを動的に調整する必要があります。
  • 不確実性: 将来の需要は不明であり、計画と最適化がより複雑になります。

オンデマンド運用は、静的 VRP と比較して、VRP ソリューションの複雑さを大幅に増大させます。

  • 継続的な再最適化: 新しい注文が到着すると、既存のルートを再最適化して、新しいリクエストを効率的に組み込む必要があります。これには頻繁な再計画が必要であり、計算量が多くなる可能性があります。
  • リアルタイム応答: システムは、顧客にタイムリーなサービスを提供するために、新しい注文に迅速に応答する必要があります。これには、効率的なアルゴリズムと、車両とのリアルタイム通信が必要になる可能性があります。
  • 不確実性管理: 未知の将来の需要に対処するには、計画プロセスに不確実性を組み込む必要があります。これには、確率モデルやロバスト最適化手法を使用して、潜在的な需要の変動を考慮することが含まれる場合があります。
  • 動的制約: 時間枠やその他の制約も動的であり、新しい注文が入ると変化する可能性があります。これにより、最適化問題に別の複雑さのレイヤーが追加されます。

課題と考慮事項:

  • アルゴリズム効率: オンデマンド VRP のアルゴリズムは、リアルタイムの更新と再最適化を処理できるほど効率的である必要があります。
  • 情報管理: システムは、着信注文、車両の位置、および変化する制約に関する情報を効果的に管理する必要があります。
  • 通信: 中央システムと車両間のリアルタイム通信は、動的ルーティングにとって重要です。
  • 顧客サービス: 効率と顧客サービスのバランスをとることが不可欠です。システムは、合理的な配達時間見積もりを提供し、動的な変化に直面しても顧客の期待を管理する必要があります。

オンデマンド VRP の例:

  • 宅配便サービス: FedEx や UPS などの企業は、パッケージの集荷と配達のオンデマンドリクエストを処理します。
  • ライドシェアリングサービス: Uber と Lyft は純粋にオンデマンドベースで運営されており、ライダーと利用可能なドライバーをリアルタイムでマッチングします。
  • 食品配達サービス: DoorDash や Grubhub などのサービスは、顧客から動的に入ってくる注文を処理します。

SWAT API はオンデマンド運用をサポートし、そのようなワークフローをロジスティクスと人輸送 シナリオ の両方に適用できるようにします。

サービス品質パラメータ (Service quality parameters)​

オンデマンドサービスの品質は、以下を含むさまざまな種類の運用をサポートするように構成できます。

  • 「タクシー」モデルの乗車（車両あたり1回のトリップ）
  • オンデマンドプーリング
  • 事前に定義された場所でのピックアップのための乗客の歩行のサポート

サービスの品質は、乗客の待ち時間、トリップ期間、およびトリップコストによって決まります。

SWAT モデルは、最小化を目的とした次のコスト関数をサポートしています。

  • 最適化の目標:
    • 合計時間を最適化する（コスト関数は秒単位で設定され、構成されたすべての時間ベースのパラメータを尊重します）
    • 合計距離を最適化する（コスト関数はメートル単位で設定され、構成されたすべての距離ベースのパラメータを尊重します）
    • 乗客の最適化（すべての車両関連コストを削除します）
  • 車両関連コスト:
    • 車両トリップ（すべての車両トリップの期間の合計）
    • 車両コスト（車両使用コスト）
  • 乗客関連コスト:
    • 乗客トリップ（すべての乗客トリップの期間の合計）
    • 乗客の歩行（乗客がピックアップ/ドロップオフ場所まで歩くことを許可する追加コスト）
  • ペナルティ:
    • 一部の制約はソフトにすることができ、それらを破ることに対するペナルティがあります

サービス品質の重要なパラメータの1つは、ピックアップに対する乗客の最大待ち時間です。この時間枠は acceptable_waiting_time パラメータによって制御されます。

乗客をプールする機能を制御し、サービス品質を決定するもう1つのパラメータは、乗客の最大移動期間です。移動期間に関連するコストを計算するために、次のようないくつかの方法がサポートされています。

値最大移動期間
constantmax_additional_journey_time
routingDDT + max(max_additional_journey_time, DDT * max_additional_journey_time_percent)
routing_max_capmin(absolute_max_trip_duration, DDT + max(max_additional_journey_time, DDT * max_additional_journey_time_percent)
routing_minDDT + min(max_additional_journey_time, DDT * max_additional_journey_time_percent)
routing_min_capmin(absolute_max_trip_duration, DDT + min(max_additional_journey_time, DDT * max_additional_journey_time_percent)
differentmax_dropoff_time - min_pickup_time

計算モードは simulation.journey_duration_source パラメータによって制御されます。

service parameters

新規予約の挿入 (Insertion of a new booking)​

新しい予約は、その車両の新しい予約と既存の予約に対して制約（ピックアップおよびドロップオフウィンドウ）が違反されていない場合にのみ、同じ車両に追加できます。挿入を成功させるには、時間枠またはその他の種類の制約が満たされている必要があります。柔軟な時間枠をサポートすることで、制約を破ることなく車両の初期計画を調整できます。

live insertion

場所への歩行 (Walking to the locations)​

SWAT アルゴリズムは、最適化プロセスの一環として、乗客が特定の事前定義された停留所まで歩く機能をサポートしています。近くに利用可能なピックアップ場所が複数ある場合、最適なもの（選択された最適化基準に基づく）が提供されます。

walking proximity

要求されたピックアップ場所 A について、最大歩行距離が > 0 の場合、システムはその歩行距離範囲内の指定されたトランジットストップセット内のウェイポイントを見つけます。

これらのウェイポイントは、予約の可能なピックアップ場所になります。アルゴリズムは、どちらがピックアップにより適しているかを決定します。

歩行時間または距離は、より近い停留所を優先することを示すために、コスト関数に含めることができます。

例:

システム構成:

  • simulation.data.max_distance_to_neighbor_stops = 300
  • simulation.data.max_number_of_neighbor_stops = 4
  • simulation.data.calculation_parameters.node_weight_coeff = 0.5

結果:

  • 要求された場所から 300m 以内のすべてのウェイポイントを見つける
  • 4つを超える場合は、最も近い4つのウェイポイントのみを取得する
  • 4つのウェイポイントは、予約のピックアップノードになります
  • 選択された任意のノードについて、全体的なコスト関数 + 0.5 * walking_time