最大トリップ期間 (Maximum trip duration)
車両ルーティング問題 (VRP) では、トリップとは、デポから始まりデポで終わる、単一の車両によって訪問される一連のノードを指します。特に最大トリップ期間や車両容量などの制約を扱う場合 、ルートは1つ以上のトリップで構成できます。最大トリップ期間制約は、車両が単一のトリップに費やすことができる合計時間を制限します。
最大トリップ期間:
最大トリップ期間制約は、車両が単一のトリップ中に「路上に」いることができる合計時間に上限を設定します。この時間には、ノード間の移動時間、各ノードでのサービス時間（例：積み込み/積み降ろし、配達時間）、およびルート中に車両が費やすその他の時間が含まれます。この制約は、ドライバーの労働時間規制、車両の稼働時間、または輸送される商品の腐敗しやすい性質などの要因により課されることがよくあります。
VRP におけるトリップ:
前述のように、トリップは、デポで始まりデポで終わる、単一の車両によるノード訪問の連続シーケンスです。車両は、再装填やドライバーの休憩のためにデポに戻るなど、勤務日中に複数のトリップを行う場合があります。各トリップは、最大トリップ期間制約を遵守する必要があります。したがって、ルートは1つ以上のトリップで構成できます。
最大トリップ期間とトリップの関係:
最大トリップ期間制約は、個々のトリップの長さと複雑さを直接制限します。それは、車両が単一のトリップ内で現実的にいくつのノードにサービスを提供できるかを決定します。
それらの関係の内訳は次のとおりです:
- トリップ期間は制限を尊重する必要があります: 車両がトリップに費やす合計時間は、最大トリップ期間を超えることはできません。
- トリップの長さは期間によって制限されます: 単一のトリップで訪問できるノードの数は、最大トリップ期間によって制限されます。
- 複数のトリップが必要になる場合があります: すべての顧客にサービスを提供するために必要な合計サービス時間と移動時間が最大トリップ期間を超える場合、車両は複数のトリップを行う必要があります。
- トリップ期間はルート計画に影響します: 実現可能性を確保するために、ルートを設計する際には最大トリップ期間制約を考慮する必要があります。
例:
ドライバーの最大トリップ期間が8時間の配送会社を想像してください。ドライバーはデポから開始し、数人の顧客を訪問し、デポに戻ります。顧客間の移動時間と各顧客の場所での配達時間を含む、この一連の訪問に費やされる合計時間は、8時間以下でなければなりません。合計時間が8時間を超える場合、ドライバーはすべての顧客にサービスを提供する前にデポに戻らなければならず、実質的にルートを複数のトリップに分割します。
SWAT モデルは、この制約の設定をサポートしています。
プレイグラウンド (Playground)
以下のプレイグラウンドを使用して、最大トリップ期間 の 概念を試すことができます。
この例では、max_trip_duration が3600秒（1時間）の車両を定義します。
ノードを追加したり、期間を調整したりして、ルートにどのように影響するかを確認してください。