オンデマンドルーティングと運用
配車計画問題（VRP）におけるオンデマンド運用とは、顧客の要求（注文）が事前にわかっているのではなく、リアルタイムで動的に発生するシナリオを指します。これは、すべての注文が通常事前にわかっていると想定される従来のVRPモデルとは対照的です。
このユースケースは、オンデマンドサービスの最も典型的なユースケースである乗客の移動を中心にしていますが、ロジスティクスなど他の業界のライブ注文管理にも適用できます。
オンデマンドVRPの主な特徴：
- 動的な要求：顧客は、運用期間中にさまざまな配送場所と要件で注文を出します。
- リアルタイムの意思決定：システムは、新しい着信注文に反応し、車両ルートを動的に調整する必要があります。
- 不確実性：将来の需要は不明であり、計画と最適化がより複雑になります。
オンデマンド運用は、静的VRPと比較してVRPソリューションの複雑さを大幅に増大させます。
- 継続的な再最適化：新しい注文が到着すると、既存のルートを再最適化して、新しい要求を効率的に組み込む必要があります。これには頻繁な再計画が必要であり、計算量が多くなる可能性があります。
- リアルタイム応答：システムは、顧客にタイムリーなサービスを提供するために、新しい注文に迅速に応答する必要があります。これには、効率的なアルゴリズムと、車両との潜在的なリアルタイム通信が必要です。
- 不確実性管理：未知の将来の需要に対処するには、計画プロセスに不確実性を組み込む必要があります。これには、需要の潜在的な変動を考慮するために、確率モデルまたは堅 牢な最適化手法を使用することが含まれる場合があります。
- 動的な制約：時間枠やその他の制約も動的である可能性があり、新しい注文が入ると変化します。これにより、最適化問題に別の複雑さの層が追加されます。
課題と考慮事項：
- アルゴリズムの効率：オンデマンドVRPのアルゴリズムは、リアルタイムの更新と再最適化を処理するのに十分効率的である必要があります。
- 情報管理：システムは、着信注文、車両の位置、および変化する制約に関する情報を効果的に管理する必要があります。
- 通信：動的ルーティングには、中央システムと車両間のリアルタイム通信が不可欠です。
- 顧客サービス：効率と顧客サービスのバランスをとることが不可欠です。システムは、妥当な配達時間見積もりを提供し、動的な変化に直面してお客様の期待を管理する必要があります。
オンデマンドVRPの例：
- 宅配便サービス：FedExやUPSなどの企業は、荷物の集荷と配達のオンデマンド要求に対応しています。
- ライドシェアサービス：UberやLyftは、純粋にオンデマンドで運営されており、リアルタイムで乗客と利用可能なドライバーをマッチングしています。
- フードデリバリーサービス：DoorDashやGrubhubなどのサービスは、顧客から動的に入ってくる注文を処理します。
SWAT APIはオンデマンドでの運用をサポートしており、このようなワークフローはロジステ ィクスと人の輸送の両方のシナリオに適用できます。
サービス品質パラメータ
オンデマンドサービスの品質は、次のようなさまざまな種類の運用をサポートするように構成できます。
- 「タクシー」モデルの乗車（車両ごとに1回の乗車）
- オンデマンドプーリング
- 事前に定義された場所でのピックアップのための乗客の歩行のサポート
サービスの品質は、乗客の待ち時間、乗車時間、および乗車料金によって決まります。
SWATモデルは、最小化を目的として次のコスト関数をサポートしています。
- 最適化目標：
- 合計時間を最適化する（コスト関数は秒単位で設定され、構成されているすべての時間ベースのパラメータを尊重します）
- 合計距離を最適化する（コスト関数はメートル単位で設定され、構成されているすべての距離ベースのパラメータを尊重します）
- 乗客の最適化（車両関連のすべてのコストを削除します）
- 車両関連のコスト：
- 車両のトリップ（すべての車両トリップの期間の合計）
- 車両コスト（車両の使用コスト）
- 乗客関連のコスト：
- 乗客のトリップ（す べての乗客トリップの期間の合計）
- 乗客の歩行（乗客がピックアップ/ドロップオフの場所まで歩くことを許可する追加コスト）
- ペナルティ：
- 一部の制約はソフトにすることができ、それらを破るとペナルティが課せられます
サービス品質の主要なパラメータの1つは、乗客のピックアップの最大待ち時間です。この時間枠は、acceptable_waiting_timeパラメータによって制御されます。
乗客をプールする能力を制御し、サービス品質を決定するもう1つのパラメータは、乗客の最大乗車時間です。乗車時間に関連するコストを計算するために、次のような複数の方法がサポートされています。
| 値 | 最大乗車時間 |
|---|---|
| 定数 | max_additional_journey_time |
| ルーティング | 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) |
| 異なる | max_dropoff_time - min_pickup_time |
計算モードは、simulation.journey_duration_sourceパラメータによって制御されます。
新しい予約の挿入
新しい予約は、その車両の新規および既存の予約に対して制約（ピックアップおよびドロップオフウィンドウ）が違反されていない場合にのみ、同じ車両に追加できます。挿入を成功させるには、時間枠またはその他の種類の制約を満たす必要があります。柔軟な時間枠をサポートすることで、制約を破ることなく車両の初期計画を調整できます。
場所への歩行
SWATアルゴリズムは、最適化プロセスの一部として、乗客が特定の事前に定義された停車地まで歩く機能をサポートしています。近隣に複数のピックアップ場所がある場合、最適な場所（選択された最適化基準に基づく）が提供されます。
要求されたピックアップ場所Aについて、最大歩行距離が0より大きい場合、システムはその歩行距離範囲内の指定されたトランジットストップセット内のウェイポイントを検索します。
これらのウェイポイントは、予約の 可能なピックアップ場所になります。アルゴリズムは、ピックアップに最も適したものを決定します。
歩行時間または距離をコスト関数に含めて、より近い停車地を優先することを示すことができます。
例：
システム構成：
simulation.data.max_distance_to_neighbor_stops= 300simulation.data.max_number_of_neighbor_stops= 4simulation.data.calculation_parameters.node_weight_coeff= 0.5
結果：
- 要求された場所から300m以内のすべてのウェイポイントを検索します
- 4つを超える場合は、最も近い4つのウェイポイントのみを取得します
- 4つのウェイポイントが予約のピックアップノードになります
- 選択されたノードについては、全体的なコスト関数+ 0.5 *
walking_time