CPVRPTW問題における時間枠
時間枠付き容量制約付き車両ルーティング問題（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となるように、ノードの終了時刻後に出発する車両は有効なシナリオです。
以下の図は、あるノードから次のノードへの車両の移動におけるイベントと時間構成要素のシーケンスを示しています。移動時間、サービス時間、休憩などのさまざまな時間ベースの制約や活動が、運用タイムライン内でどのようにスケジュールされるかを視覚化します。