ラストマイルの配達時間枠を伴う VRP
顧客訪問が特定の時間枠にのみ可能である場合、ラストマイルの配達問題を解決するには、特定の時間を考慮する必要があることがよくあります。このような問題は、時間枠を伴う車両ルーティング問題(VRPTW)と呼ばれ、ほとんどの配送サービスで広く発生している問題です。 この問題を解決するには、該当する問題に含まれる他のすべての制約とともに、タイミング制約も考慮する必要があります。
ジョブごとに 1 つの時間枠
車両が異なる時間枠に 2 つの配達ジョブを実行する必要がある状況を確認してみましょう。
- job_1 は 9:00 ~ 18:00 の間
- job_2 は 10:00 ~ 16:00の間
車両のシフト時間が 8 時から 18 時までの 10 時間であると仮定します。
ここで、各作業には 1 つの時間枠があり、車両の総走行時間を最小限に抑えて、指定された時間枠内にその場所に到着することを目標としています。 この場合、極めて重要な条件は、ジョブの時間枠だけでなく、正確なシフトの開始時間と終了時間も指定することです。 shiftTime
プロパティは、車両タイプの最大許容作業時間を定義します。 車両に休憩が定義されている場合、休憩時間が shiftTime
に追加されます。 今回の場合、車種は休憩なしで10時間のシフトなので、合計shiftTime
は10時間と定義されます。
VehicleShift
の プロパティstart.time
および end.time
は、車両シフトが割り当てられる時間枠の下限および上限を定義します。車両は、start.time
の前に作業を開始できません。または、end.time
の後で作業を終了できません。 start.time
および end.time
は、車両が配達を開始および終了する場所であり、ラストマイルの配達シナリオでは通常、荷物が車両に積み込まれる場所であるデポの、開始時間および終了時間であると想像できます。
同時に、start.time
と end.time
は、定義された shiftTime
を上書きできます。つまり、プロパティshiftTime
によって定義された時間が start.time
~ end.time
の間の時間間隔よりも長い場合、車両の最大作業時間が短縮され、その時間間隔を超えることはありません。
{
"fleet": {
"types": [
{
"id": "2695492ea0a5",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.00,
"time": 0.02
},
"shifts": [
{
"start": {
"time": "2021-07-13T08:00:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-07-13T18:00:00Z",
"location": {
"lat": 52.540850339546864,
"lng": 13.435575785242161
}
}
}
],
"capacity": [
10
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-07-13T09:00:00Z",
"2021-07-13T18:00:00Z"
]
],
"location": {
"lat": 52.605284383450964,
"lng": 13.293433615477289
},
"duration": 1140
}
],
"demand": [
2
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-07-13T10:00:00Z",
"2021-07-13T16:00:00Z"
]
],
"location": {
"lat": 52.48000596392929,
"lng": 13.458654687378955
},
"duration": 1020
}
],
"demand": [
2
]
}
]
}
}
]
}
}
このような問題の解決策は次のようになります。
{
"statistic": {
"cost": 144.94,
"distance": 51941,
"duration": 6997,
"times": {
"driving": 4837,
"serving": 2160,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "2695492ea0a5_1",
"typeId": "2695492ea0a5",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-07-13T08:00:00Z",
"departure": "2021-07-13T08:43:48Z"
},
"load": [
4
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.60528438345096,
"lng": 13.293433615477287
},
"time": {
"arrival": "2021-07-13T09:06:09Z",
"departure": "2021-07-13T09:25:09Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.48000596392929,
"lng": 13.458654687378957
},
"time": {
"arrival": "2021-07-13T10:00:00Z",
"departure": "2021-07-13T10:17:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.540850339546864,
"lng": 13.43557578524216
},
"time": {
"arrival": "2021-07-13T10:40:25Z",
"departure": "2021-07-13T10:40:25Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 144.94,
"distance": 51941,
"duration": 6997,
"times": {
"driving": 4837,
"serving": 2160,
"waiting": 0,
"break": 0
}
}
}
]
}
このソリューションでは、総コスト、距離、所要時間、設定した時間枠を考慮したジョブの実行順序など、系統立ったツアーの統計情報を確認できます。
ジョブごとの複数時間枠
クライアントの特定の要件により、 1 日以内に複数の時間枠でジョブを実行できる場合があります。この場合、最適化のための選択肢が増え、ツアーの計画時に考慮する必要があります。この場合、ジョブの時間枠が重複しないようにする必要があり、したがって、時間枠の開始時間と終了時間が別のジョブの時間枠に含まれていてはいけません。
車両が異なる時間に 2 つのジョブを実行する必要がある状況について考えてみましょう。
- job_1 は 9:00 ~ 11:00 、または 16:00 ~ 19:00 の間
- Job_2 は 11:00 ~ 14:00 、または 17:00 ~ 19:00 の間
車両のシフト時間が 8 時から 18 時までの 10 時間であると仮定します。 ここで、各ジョブには、2 つの時間枠があります。
この場合、車両のシフト時間は job_1 の両方の時間枠にマッチしますが、job_2 は最初の時間枠にのみ部分的にマッチします。このため、解決策では、これらの制約条件を考慮して、車両のより適切なルートを計算します。
{
"fleet": {
"types": [
{
"id": "2695492ea0a5",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.02
},
"shifts": [
{
"start": {
"time": "2021-07-13T08:00:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-07-13T18:00:00Z",
"location": {
"lat": 52.540850339546864,
"lng": 13.435575785242161
}
}
}
],
"capacity": [
5
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2021-07-13T09:00:00Z",
"2021-07-13T11:00:00Z"
],
[
"2021-07-13T16:00:00Z",
"2021-07-13T19:00:00Z"
]
],
"location": {
"lat": 52.605284383450964,
"lng": 13.293433615477289
},
"duration": 1140
}
],
"demand": [
2
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2021-07-13T11:00:00Z",
"2021-07-13T14:00:00Z"
],
[
"2021-07-13T17:00:00Z",
"2021-07-13T19:00:00Z"
]
],
"location": {
"lat": 52.54217501128922,
"lng": 13.31486008054587
},
"duration": 120
}
],
"demand": [
2
]
}
]
}
}
]
}
}
このような問題の解決策は次のとおりです。
{
"statistic": {
"cost": 334.486,
"distance": 33638,
"duration": 4701,
"times": {
"driving": 3441,
"serving": 1260,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "2695492ea0a5_1",
"typeId": "2695492ea0a5",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-07-13T08:00:00Z",
"departure": "2021-07-13T10:07:02Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.60528438345096,
"lng": 13.293433615477287
},
"time": {
"arrival": "2021-07-13T10:29:23Z",
"departure": "2021-07-13T10:48:23Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.54217501128922,
"lng": 13.31486008054587
},
"time": {
"arrival": "2021-07-13T11:00:00Z",
"departure": "2021-07-13T11:02:00Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_2",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.540850339546864,
"lng": 13.43557578524216
},
"time": {
"arrival": "2021-07-13T11:25:23Z",
"departure": "2021-07-13T11:25:23Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 334.486,
"distance": 33638,
"duration": 4701,
"times": {
"driving": 3441,
"serving": 1260,
"waiting": 0,
"break": 0
}
}
}
]
}
これにより、総コスト、走行距離、所要時間などの定期的なツアーの統計情報、および各ジョブに設定した両方の時間枠を考慮したジョブの実行順序を確認できます。
時間枠がシフト終了に近すぎるため、割り当てられていないジョブ
時間枠が車両シフトの終了時間に近すぎるために、車両にジョブを割り当てることができない状況に遭遇することがあります。 たとえば、作業時間枠が 16:00 ~ 18:00 で、車両シフトの終了時間が 19:00 の場合です。 このような状況では、ジョブは割り当てられず、それぞれのメッセージが通知されます。
車両が異なる時間に 2 つのジョブを実行する必要がある状況について考えてみましょう。
- job_1 は 9:00 ~ 19:00 の間
- job_2 は 17:45 ~ 18:30 の間
車両のシフト時間が 8 時から 18 時までの 10 時間であると仮定します。
{
"fleet": {
"types": [
{
"id": "2695492ea0a5",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.02
},
"shifts": [
{
"start": {
"time": "2021-07-13T08:00:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-07-13T18:00:00Z",
"location": {
"lat": 52.540850339546864,
"lng": 13.435575785242161
}
}
}
],
"capacity": [
5
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2021-07-13T09:00:00Z",
"2021-07-13T19:00:00Z"
]
],
"location": {
"lat": 52.605284383450964,
"lng": 13.293433615477289
},
"duration": 1140
}
],
"demand": [
2
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2021-07-13T17:50:00Z",
"2021-07-13T18:30:00Z"
]
],
"location": {
"lat": 52.54217501128922,
"lng": 13.31486008054587
},
"duration": 120
}
],
"demand": [
2
]
}
]
}
}
]
}
}
このような問題の解決策は次のとおりです。
{
"statistic": {
"cost": 300.415,
"distance": 30005,
"duration": 4269,
"times": {
"driving": 3129,
"serving": 1140,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "2695492ea0a5_1",
"typeId": "2695492ea0a5",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-07-13T08:00:00Z",
"departure": "2021-07-13T08:37:39Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.60528438345096,
"lng": 13.293433615477287
},
"time": {
"arrival": "2021-07-13T09:00:00Z",
"departure": "2021-07-13T09:19:00Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.540850339546864,
"lng": 13.43557578524216
},
"time": {
"arrival": "2021-07-13T09:48:48Z",
"departure": "2021-07-13T09:48:48Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 300.415,
"distance": 30005,
"duration": 4269,
"times": {
"driving": 3129,
"serving": 1140,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": [
{
"jobId": "job_2",
"reasons": [
{
"code": "TIME_WINDOW_CONSTRAINT",
"description": "cannot be visited within time window"
}
]
}
]
}
このソリューションでは、総コスト、距離、所要時間、時間枠を考慮したジョブの実行順序など、定期的なツアーの統計情報を確認できます。 時間枠が車両シフト終了時間に近いため、ここでは 1 つのジョブを実行できず、また、その旨メッセージが返されます。