時間帯を使用してアクティビティの開始時間を制限する
顧客訪問が特定の時間枠にのみ可能である場合、ラストマイル配送の問題を解決するには、特定の時間枠を考慮する必要があることがよくあります。このような問題は、時間枠を伴う車両ルート検索問題 (VRPTW) と呼ばれ、ほとんどの配送サービスで広く発生している問題です。この問題を解決するには、該当する問題に含まれる他のすべての制約とともに、タイミング制約も考慮する必要があります。
ジョブごとに1つの時間枠
車両が異なる時間枠に2つの配達ジョブを実行する必要がある状況を確認してみましょう。
job_1は9:00～18:00job_2は10:00～16:00
車両のシフト時間が8:00～18:00までの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の間の時間間隔よりも長い場合、車両の最大作業時間が短縮され、その時間間隔を超えることはありません。
問題
Click to expand/collapse the sample JSON
{
"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
]
}
]
}
}
]
}
}ソリューション
この問題のソリューションは次のようになります。
Click to expand/collapse the sample JSON
{
"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"
}
],
"distance": 0
},
{
"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"
}
],
"distance": 13236
},
{
"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"
}
],
"distance": 42833
},
{
"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"
}
],
"distance": 52593
}
],
"statistic": {
"cost": 144.94,
"distance": 51941,
"duration": 6997,
"times": {
"driving": 4837,
"serving": 2160,
"waiting": 0,
"break": 0
}
}
}
]
}このソリューションでは、総コスト、距離、所要時間、設定した時間枠を考慮したジョブの実行順序など、系統立ったルートの統計情報を確認できます。
時間枠とアクティビティの所要時間
HERE Tour Planning APIでは、指定されたアクティビティ場所 (集荷/deliveryポイント、休憩エリア、再積載場所など) にドライバーが到着するまでの許容時間範囲を時間枠で定義します。これらの時間枠はアクティビティの期間とは無関係です。典型的なシナリオでは、指定された期間が、割り当てられた時間枠を超えた場合でも、時間枠を超える直前にドライバーがアクティビティ場所に到着することが許容されます。
ただし、アクティビティの期間を考慮して時間枠を最適化することはできます。次のサンプルジョブ設定に示されているように、ドライバーのシフトが8:00～18:00、時間枠が10:00～11:00でサービス時間が1800秒 (0.5時間) に設定されている集荷アクティビティの例を考えてみましょう。
{
"id": "job_X",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2021-10-23T10:00:00Z",
"2021-10-23T11:00:00Z"
]
],
"location": {
"lat": 51.06099,
"lng": 13.75245
},
"duration": 1800
}
],
"demand": [
1
]
}
]
}
}この例では、時間枠 (times配列で指定) により、指定された時間枠内の任意の時点でドライバーがアクティビティを開始できるよう徹底されます。ただし、ドライバーは午前11時までにアクティビティ場所に到着することが義務付けられています。次の図はドライバーが遅れて到着したものの、まだ時間枠内であるため、集荷アクティビティを午前11時を超えて延長できるシナリオを示しています。
たとえば、ドライバーが集荷場所に到着し、午前11時前にサービスを完了するようにするには、アクティビティ期間で指定されたサービス時間を時間枠の終了時間から減算します。この特定のユースケースでは、調整された時間枠に次の設定があり、時間枠の終了時間は午前10:30に設定されています。
{
"times": [
[
"2021-10-23T10:00:00Z",
"2021-10-23T10:30:00Z"
]
]
}結果として得られる時間枠の設定では、集荷アクティビティの期間が考慮され、次の図に示すようにドライバーがアクティビティを完了して午前11時より前に出発することが徹底されます。
ジョブごとに複数の時間枠
クライアントの特定の要件により、1日以内に複数の時間枠でジョブを実行できる場合があります。この場合、最適化のための選択肢が増え、ルートの計画時に考慮する必要があります。この場合、ジョブの時間枠が重複しないようにする必要があり、したがって、時間枠の開始時間と終了時間が別のジョブの時間枠に含まれていてはいけません。
車両が異なる時間枠に2つのジョブを実行する必要がある状況について考えてみましょう。
job_1は9:00～11:00または16:00～19:00job_2は11:00～14:00または17:00～19:00
車両のシフト時間が8:00～18:00までの10時間であると仮定します。ここで、各ジョブには2つの時間枠があります。
この場合、車両のシフト時間はjob_1の両方の時間枠にマッチしますが、job_2は最初の時間枠にのみ部分的にマッチします。このため、ソリューションではこれらの制約条件を考慮して、車両のより適切なルートを計算します。
問題
Click to expand/collapse the sample JSON
{
"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
]
}
]
}
}
]
}
}ソリューション
この問題のソリューションは次のようになります。
Click to expand/collapse the sample JSON
{
"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"
}
],
"distance": 0
},
{
"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"
}
],
"distance": 13236
},
{
"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"
}
],
"distance": 22829
},
{
"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"
}
],
"distance": 33636
}
],
"statistic": {
"cost": 334.486,
"distance": 33638,
"duration": 4701,
"times": {
"driving": 3441,
"serving": 1260,
"waiting": 0,
"break": 0
}
}
}
]
}これにより、総コスト、距離、所要時間、各ジョブに設定した時間枠を考慮したジョブの実行順序など、系統立ったルートの統計情報を確認できます。
注
ソリューションの結果の
timesは、問題の作成で使用された時間オフセットに関係なく、常にUTCで返されます。
時間枠がシフト終了に近すぎるため、割り当てられていないジョブ
時間枠が車両シフトの終了時間に近すぎるために、車両にジョブを割り当てることができない状況に遭遇することがあります。たとえば、ジョブの時間枠が16:00～18:00で、車両シフトの終了時間が19:00の場合です。このような状況では、ジョブは割り当てられず、それぞれのメッセージが通知されます。
車両が異なる時間枠に2つのジョブを実行する必要がある状況について考えてみましょう。
job_1は9:00～19:00job_2は17:45～18:30
車両のシフト時間が8:00～18:00までの10時間であると仮定します。
問題
Click to expand/collapse the sample JSON
{
"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
]
}
]
}
}
]
}
}
ソリューション
この問題のソリューションは次のようになります。
Click to expand/collapse the sample JSON
{
"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"
}
],
"distance": 0
},
{
"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"
}
],
"distance": 13236
},
{
"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"
}
],
"distance": 30008
}
],
"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つのジョブを実行できず、また、その旨メッセージが返されます。
次のステップ
詳細については、以下を参照してください。
- Submit a Vehicle Routing Problem to solve it synchronously (車両ルート検索問題を送信して同期的に解決する)
- Submit a Vehicle Routing Problem to solve it asynchronously (車両ルート検索問題を送信して非同期的に解決する)
26 日前の更新