最大トリップ期間

配車計画問題（VRP）では、トリップとは、単一の車両が訪問する一連のノードを指し、デポから始まりデポで終わります。ルートは、最大トリップ期間や車両容量などの制約に対処する場合、1つ以上のトリップで構成できます。最大トリップ期間の制約は、車両が1回のトリップに費やすことができる合計時間を制限します。

最大トリップ期間：

最大トリップ期間の制約は、車両が1回のトリップ中に「路上」にいることができる合計時間の上限を設定します。この時間には、ノード間の移動時間、各ノードでのサービス時間（荷積み/荷降ろし、配達時間など）、およびルート中に車両が費やすその他の時間が含まれます。この制約は、多くの場合、ドライバーの労働時間規制、車両の稼働時間、または輸送される商品の腐りやすい性質などの要因によって課せられます。

VRPにおけるトリップ：

前述のように、トリップは、単一の車両による連続したノード訪問のシーケンスであり、デポで始まり終わります。車両は、勤務日中に複数のトリップを行い、再積載またはドライバーの休憩のためにデポに戻る場合があります。各トリップは、最大トリップ期間の制約に従う必要があります。したがって、ルートは1つ以上のトリップで構成できます。

最大トリップ期間とトリップの関係：

最大トリップ期間の制約は、個々のトリップの長さと複雑さを直接制限します。これにより、車両が1回のトリップで現実的にサービスを提供できるノードの数が決まります。

それらがどのように関連しているか：

• トリップ期間は制限を尊重する必要があります：車両がトリップに費やす合計時間は、最大トリップ期間を超えることはできません。
• トリップの長さは期間によって制約されます：1回のトリップで訪問できるノードの数は、最大トリップ期間によって制限されます。
• 複数のトリップが必要になる場合があります：すべての顧客にサービスを提供するために必要な合計サービス時間と移動時間が最大トリップ期間を超える場合、車両は複数のトリップを行う必要があります。
• トリップ期間はルート計画に影響します：実現可能性を確保するために、ルートを設計する際に最大トリップ期間の制約を考慮する必要があります。

例：

ドライバーの最大トリップ期間が8時間の配送会社を想像してみてください。ドライバーはデポから出発し、いくつかの顧客を訪問し、デポに戻ります。顧客間の移動時間と各顧客の場所での配達時間を含む、この一連の訪問に費やされる合計時間は、8時間以下でなければなりません。合計時間が8時間を超える場合、ドライバーはすべての顧客にサービスを提供する前にデポに戻る必要があり、ルートを複数のトリップに効果的に分割します。

SWATモデルはこの制約の設定をサポートしています：