CPVRPTW 問題の時間枠 (Time windows in CPVRPTW problems)
時間枠付き容量制約付き車両ルーティング問題 (CVRPTW) は、車両容量と時間枠という2つの重要な現実世界の制約を組み込むことにより、従来の VRP を拡張します。顧客にいつサービスを提供できるかを制限する時間枠は、現実的なシナリオをモデル化するために不可欠であり、ソリューションの実現可能性と コストに大きく影響します。
時間枠は、配達またはサービス時間が制限されている現実世界の状況を表すために不可欠です。食料品や荷物の配達、フィールドサービスなどの業界を考えてみてください。顧客は多くの場合、優先または必須の配達時間を指定し、企業は顧客満足度と運用効率を維持するためにこれらを遵守する必要があります。これらの制約を無視すると、配達の失敗、再訪問によるコストの増加、顧客の不満につながる可能性があります。時間枠を効果的に組み込むことで、顧客の好みを尊重し、移動時間を最小限に抑え、車両使用率を最大化する最適化されたルートが可能になり、最終的にサービスレベルの向上と運用コストの削減につながります。
時間枠は、開始時間（最も早い到着時間）と終了時間（最も遅い到着時間）によって定義されます。それらは通常、次のように分類されます。
- ハード時間枠: サービスは指定された枠内で行われる必要があります。開始前または終了時間後に到着することは受け入れられず、ソリューションは実行不可能になります。
- ソフト時間枠: 枠内のサービスが推奨されますが、多くの場合ペナルティ付きで逸脱が許可されます。早く到着すると待機時間が発生する可能性があり、遅く到着するとペナルティコストが発生する可能性があります。
時間枠は、CVRPTW 内のさまざまなエンティティに適用できます。
- 顧客: これは最も一般的なアプリケーションであり、顧客の希望するサービス時間を表します。
- デポ: デポ（車両の出発および終了場所）にも時間枠制約があり、車両が出発および戻ることができる時間を制限する場合があります。
- 車両: ドライバーの可用性や車両の制限により、車両自体に時間枠がある場合があります。
SWAT API における予約（注文）のタイミングモデル:
さらに、SWAT モデルは車両の時間制限をサポートしています。ドライバーの労働時間を規制するには、vehicle.start_time および vehicle.end_time プロパティを活用してください。任意の時間の組み合わせを利用でき、各車両に制限付きおよび無制限の時間枠の両方を可能にします。api
ノード（たとえば、店舗）が車両を受け入れることができる営業時間内にギャップがある可能性があるより複雑なケースの場合、SWAT モデルは、booking.pickup_time_windows または booking.dropoff_time_windows を介して、各予約（またはノード）api に対して複数の時間枠をサポートします。
これにより、次のように注文または場所レベルで複数の営業時間を設定できます。
"8am-11am; 11am-3pm; 7pm-8pm"
典型的な時間枠付き集配問題 (PDP-TW) では、SWAT 最適化モデルは、車両が指定された時間枠内（ノードの開店時間と閉店時間の間）にノードに到着することを要求します。ただし、ノードの閉店時間後の出発は許可されており、そのノードで必要なサービス時間に対応します。したがって、node.scheduled_ts + node.service_time > node.close_time_ts となる、閉店時間後に車両がノードを出発することは有効なシナリオです。
以下の図は、あるノードから次のノードへの車両の移動のイベントシーケンスと時間コンポーネントを示しています。移動時間、サービス時間、休憩などのさまざまな時間ベースの制約とアクティビティが、運用タイムライン内でどのようにスケジュールされるかを視覚化します。