オンデマンドルーティングと運用 (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つのパラメータは、乗客の最大移動期間です。移動期間に関連するコストを計算するために、次のようないくつかの方法がサポートされています。

値	最大移動期間
constant	max_additional_journey_time
routing	DDT + max(max_additional_journey_time, DDT * max_additional_journey_time_percent)
routing_max_cap	min(absolute_max_trip_duration, DDT + max(max_additional_journey_time, DDT * max_additional_journey_time_percent)
routing_min	DDT + min(max_additional_journey_time, DDT * max_additional_journey_time_percent)
routing_min_cap	min(absolute_max_trip_duration, DDT + min(max_additional_journey_time, DDT * max_additional_journey_time_percent)
different	max_dropoff_time - min_pickup_time

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

予約のリードタイムと到着指定の時間枠 (Booking lead time and arrive-by windows)

旅客輸送の予約は、出発時刻を指定する出発指定 (depart-at) と、到着時刻を指定する到着指定 (arrive-by) のいずれかです。以下のシミュレーションパラメータ（単位：秒）で、予約可能な最短の時刻と、到着指定のドロップオフ時間枠の作り方を制御します。

パラメータ	デフォルト	効果
min_lead_time_depart_at	0	出発指定の予約は、現在時刻からこの秒数以上先の出発時刻を指定する必要があります。
min_lead_time_arrive_by	7200	到着指定の予約は、現在時刻からこの秒数以上先の到着時刻を指定する必要があります。
arrive_by_traffic_buffer_sec	0	交通遅延への余裕として、指定された到着時刻から差し引いて最遅ドロップオフ時刻 (max_dropoff_time) を求めます。
acceptable_early_dropoff_time	null	ドロップオフ時間枠が max_dropoff_time の何秒前に開くかを指定します。null の場合は acceptable_waiting_time が使用されます。

リードタイムのチェックは、乗客アプリからの予約と、オペレーターが POST /api/v2/microservices/bookings で作成する予約に適用されます。時刻が近すぎる予約は 400 エラーで拒否されます。min_lead_time_arrive_by のデフォルトは 2 時間のため、直前の到着指定予約を受け付けるサービスでは 0 に設定してください。

例：09:00 到着指定、arrive_by_traffic_buffer_sec: 300、acceptable_early_dropoff_time: 900 の場合、ドロップオフ時間枠は 08:40～08:55 になります。乗客が指定した元の 09:00 は、予約の requested_target_time に保持されます。

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

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

割り当て時の時間枠の固定 (Pinning time windows on assignment)

継続的な再最適化では、すでに割り当てられた予約を元の時間枠内のどこへでも移動できます。ピックアップ時刻をすでに顧客やドライバーに伝えている場合、このようなずれは望ましくありません。

2 つの任意パラメータを使うと、予約が車両に割り当てられた時点でその時間枠を狭めることができます。以降の最適化ラウンドでは、計画時刻の前後の狭い範囲内でしか予約を移動できなくなります。

システム設定（秒単位、simulation.data に設定）:

{
  "shrink_time_delta": 300,
  "reverse_shrink_time_delta": 120
}

パラメータ	効果
shrink_time_delta	計画時刻よりどれだけ遅くまで停車を許容するか
reverse_shrink_time_delta	計画時刻よりどれだけ早く停車を許容するか

どちらのパラメータも単独で使用できます。両方とも未設定（またはデフォルトの null）の場合、この機能は無効です。

仕組み — デフォルトの移動タイプである depart-at 予約の場合:

pickup.open_time_ts  = max(scheduled_ts - reverse_shrink_time_delta, pickup.open_time_ts)
pickup.close_time_ts = min(scheduled_ts + shrink_time_delta,         pickup.close_time_ts)

scheduled_ts は、オプティマイザーがその停車に対して計画した時刻です。min/max によるクランプのため、時間枠は予約の元の時間枠に対して狭められるだけです。これらのパラメータで時間枠が広がったり、実行不可能な計画が実行可能になったりすることはありません。

狭める処理は、まだ車両に割り当てられていない停車にのみ適用されます。そのため、予約が最初にルートに確定した時点で一度だけ適用されます。狭められた時間枠はノードに保存され、以降のすべての最適化ラウンドで使用されます。

例 — ピックアップ時間枠が 09:00–11:00、ピックアップ計画時刻が 09:40 の注文に、上記の設定を適用した場合:

	割り当て前	割り当て後
ピックアップ時間枠	09:00 – 11:00	09:38 – 09:45

以降のラウンドで予約が別の車両に再割り当てされることはありますが、ピックアップを 09:38–09:45 の範囲外に移動することはできなくなります。

ドロップオフ時間枠への影響

depart-at 予約では、ドロップオフ時間枠は狭められるのではなく、ピックアップから導出されます。ドロップオフはピックアップの開始時刻に開き、その max_trip_duration 後に閉じます。

物流では max_trip_duration が max_dropoff_time - min_pickup_time の全期間となるため、注文自体の min_dropoff_time が破棄されます。また、reverse_shrink_time_delta によってピックアップの開始時刻が動いた秒数だけ、ドロップオフの終了時刻も max_dropoff_time を超えて動きます。配送時間枠を守る必要がある運用では、これらのパラメータを使用しないでください。

arrive-by 予約ではロジックが逆になります。ドロップオフ時間枠が計画時刻の前後に固定され、ピックアップ時間枠はそこから導出されます。

旅客輸送 (People transport)

旅客輸送では、これらのパラメータによって乗客に伝えた時刻を固定します。どの停車が固定されるかは、予約の移動タイプによって決まります。max_trip_duration は乗客の最大乗車時間です（上記の journey_duration_source を参照）。

depart-at 予約（乗客が指定時刻以降のピックアップを希望）— ピックアップが固定されます:

フィールド	shrink_time_delta のみ	reverse_shrink_time_delta を設定（shrink_time_delta の有無を問わない）
ピックアップ開始	変更なし	max(scheduled_ts - reverse_shrink_time_delta, open)
ピックアップ終了	min(scheduled_ts + shrink_time_delta, close)	shrink_time_delta が設定されていれば左と同じ、なければ変更なし
ドロップオフ開始	= ピックアップ開始	= ピックアップ開始
ドロップオフ終了	ピックアップ開始 + max_trip_duration	algo_type: dynamic: ピックアップ開始 + max_trip_duration algo_type: static: 変更なし
ドロップオフ終了（dynamic 期限）	ピックアップ終了 + max_trip_duration	ピックアップ終了 + max_trip_duration

例 — 08:00 以降のピックアップを希望、acceptable_waiting_time 20 分（時間枠 08:00–08:20）、計画時刻 08:12、max_trip_duration 30 分、shrink_time_delta: 180、reverse_shrink_time_delta: 120 の場合:

	割り当て前	割り当て後
ピックアップ時間枠	08:00 – 08:20	08:10 – 08:15
ドロップオフ開始		08:10
ドロップオフ終了（dynamic 期限）		08:45

「バスは 08:12 頃に到着します」と伝えられた乗客は、後からどの予約が同じ車両に相乗りされても、08:10 から 08:15 の間にピックアップされます。

arrive-by 予約（乗客が指定時刻までの到着を希望）— ドロップオフが固定されます:

フィールド	shrink_time_delta のみ	reverse_shrink_time_delta を設定（shrink_time_delta の有無を問わない）
ドロップオフ開始	max(scheduled_ts - shrink_time_delta, open)	max(scheduled_ts - reverse_shrink_time_delta, open)
ドロップオフ終了	min(scheduled_ts + shrink_time_delta, close)	shrink_time_delta が設定されていれば左と同じ、なければ変更なし
ピックアップ終了	= ドロップオフ終了	= ドロップオフ終了
ピックアップ開始	ドロップオフ終了 - max_trip_duration	ドロップオフ終了 - max_trip_duration
ピックアップ開始（dynamic）	ドロップオフ開始 - max_trip_duration	ドロップオフ開始 - max_trip_duration

shrink_time_delta のみの arrive-by は前後対称

shrink_time_delta のみを設定した場合、arrive-by のドロップオフはその値で前後両側が狭められます。depart-at のように「遅い側のみ」ではありません。早い側を個別に制御するには、reverse_shrink_time_delta も設定してください。

例 — 09:00 までに到着（ドロップオフ時間枠 08:40–09:00）、ドロップオフ計画時刻 08:50、max_trip_duration 30 分の場合:

設定	割り当て後のドロップオフ時間枠	割り当て後のピックアップ時間枠
shrink_time_delta: 300	08:45 – 08:55	08:25 – 08:55
shrink_time_delta: 300、reverse_shrink_time_delta: 120	08:48 – 08:55	08:25 – 08:55

クランプにより元の時間枠を超えることはないため、乗客の到着期限は常に守られます。

combined_on_demand: true の場合の到着指定予約 — 同じサービスで出発指定と到着指定の両方の予約を受け付ける場合は、このシミュレーションパラメータを設定します。この場合、ピックアップはドロップオフから導出されるのではなく、出発指定と同様に自身の計画時刻を基準に固定されます。

フィールド	shrink_time_delta のみ	reverse_shrink_time_delta を設定（shrink_time_delta の有無を問わない）
ピックアップ開始	変更なし	max(scheduled_ts - reverse_shrink_time_delta, open)
ピックアップ終了	min(scheduled_ts + shrink_time_delta, close)	shrink_time_delta が設定されていれば左と同じ、それ以外は変更なし
ドロップオフ開始	ドロップオフの scheduled_ts	ドロップオフの scheduled_ts
ドロップオフ終了	requested_target_time	requested_target_time

ドロップオフは計画時刻より遅くなることがありますが、乗客が指定した到着時刻までに限られます。この時刻は arrive_by_traffic_buffer_sec を差し引く前の、指定されたままの時刻です。予約に requested_target_time がない場合、ドロップオフの終了時刻は変更されません。combined_on_demand のデフォルトは false で、その場合は上の表のとおりです。

注意事項

• 影響を受けるのは車両が未割り当ての予約のみです。そのため、狭める処理は予約が最初に割り当てられたときに一度だけ行われます。すでに車両に載っている予約の時間枠は変わりません。
• reverse_shrink_time_delta を設定した depart-at では、algo_type: static の場合、ドロップオフの終了時刻を意図的に変更しません。これにより、到着時刻が固定されたサービスの乗客は元のドロップオフ期限まで乗車できます。それ以外の組み合わせでは、上表のとおり上書きされます。
• 値は秒単位です。少なくとも想定される ETA 誤差以上の値にしてください。時間枠が狭すぎると、その車両への以降の挿入（および遅延後の再最適化）が実行不可能になります。

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

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

要求されたピックアップ場所 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