容量制約を伴う VRP
HERE では、需要、積載量の相互関係、追加の積載量パラメータなどの特定の制約を使用して、ラストマイル配送の問題を解決する方法を模索しています。
需要とキャパシティの相関関係
容量制約を伴う車両の取り回しの問題を解決するには、車両の取り回し時に車両の積載量を考慮する必要があります。 作業の需要と車両の積載量を考慮して、複数の場所を訪問する複数の車両に最適なルートを見つける必要がある状況を考えてみましょう。 すべての作業の総需要がすべての車両の総積載量を超えない場合、この特定の問題を解決できるものと想定する必要があります。
4 つの場所と 2 台の車両があるとします。 各場所には、集荷または配達するアイテムの数量に対応するジョブの特定の需要があります (5,4,2,3) 。 また、各車両の最大積載量は 10 です。 車両の積載量は、車両が保持できる最大積載量です。 車両が運搬できる荷物の合計量が、その積載量を超えることはありません。
ここで解決する必要のある問題は、車両の総走行距離が最短となり、車両が運搬している総量がその車両の積載量に適しているルートの車両への割り当てを見つけることです。私たちは、需要や積載量に対する単位を指定しません。単位は、事業毎、組織毎に定義されるものです。(集荷または配達される品目の重量や量など)。したがって、需要及び積載量には正の数のみを入力する必要があります。
この問題の解決策を計算するには、次の情報を提供する必要があります。
この例では、次の主な制約があります。
Location : 4.
各場所での需要 : 5 、 4 、 2 、 3
車両 : 2.
各車両の積載量 : 10 、 10.
この例では、運行管理 プロファイル、各車両コスト、シフトフィールドの開始時間と終了時間、それらの積載量と数を指定しました。 積載量については 10、数は 2 を指定しています。つまり、このソリューションでは同じ積載量の車両を最大 2 台使用できます。 以下の例では、特に車両タイプについて、距離と時間の両方で 0 より大きいコストを指定しています。 その結果、このアルゴリズムによって、指定した 2 台の車両の走行距離とツアー時間の両方が最適化されることが予想されます。
{
"fleet": {
"types": [
{
"id": "069ea42ae3e9",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.002
},
"shifts": [
{
"start": {
"time": "2021-07-10T08:37:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-07-10T17:37:00Z",
"location": {
"lat": 52.5281430596138,
"lng": 13.36381375834569
}
}
}
],
"capacity": [
10
],
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
前述のように、 4 つのジョブを実行します。 ジョブごとに、そのタイプ ( 集荷または配達 ) 、場所、期間、需要を指定します。 この特定のケースで重要なパラメータは、上記車両に指定した積載量と直接関連するので、「需要」です。
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.484104043903585,
"lng": 13.386732295521801
},
"duration": 840
}
],
"demand": [
5
]
}
]
}
},
Problems
上記の4 つの配達ジョブを伴う例について、問題を設定しましょう。
{
"fleet": {
"types": [
{
"id": "d3e7bb8d20c5",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.05
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T19:03:00Z",
"location": {
"lat": 52.43119084052164,
"lng": 13.39255783460401
}
}
}
],
"capacity": [
10
],
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.484104043903585,
"lng": 13.386732295521801
},
"duration": 840
}
],
"demand": [
5
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747735
},
"duration": 600
}
],
"demand": [
4
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"duration": 60
}
],
"demand": [
2
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087625
},
"duration": 1140
}
],
"demand": [
3
]
}
]
}
}
]
}
}
Solution
このような問題の解決策は次のとおりです。
{
"statistic": {
"cost": 679.9580000000001,
"distance": 39944,
"duration": 7807,
"times": {
"driving": 5167,
"serving": 2640,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "d3e7bb8d20c5_2",
"typeId": "d3e7bb8d20c5",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
"load": [
7
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087623
},
"time": {
"arrival": "2021-08-27T08:21:09Z",
"departure": "2021-08-27T08:40:09Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747737
},
"time": {
"arrival": "2021-08-27T08:46:35Z",
"departure": "2021-08-27T08:56:35Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_2",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.43119084052164,
"lng": 13.39255783460401
},
"time": {
"arrival": "2021-08-27T09:14:16Z",
"departure": "2021-08-27T09:14:16Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 364.68,
"distance": 20840,
"duration": 4276,
"times": {
"driving": 2536,
"serving": 1740,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "d3e7bb8d20c5_1",
"typeId": "d3e7bb8d20c5",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
"load": [
7
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"time": {
"arrival": "2021-08-27T08:12:53Z",
"departure": "2021-08-27T08:13:53Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.484104043903585,
"lng": 13.3867322955218
},
"time": {
"arrival": "2021-08-27T08:32:38Z",
"departure": "2021-08-27T08:46:38Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.43119084052164,
"lng": 13.39255783460401
},
"time": {
"arrival": "2021-08-27T09:01:51Z",
"departure": "2021-08-27T09:01:51Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 315.278,
"distance": 19104,
"duration": 3531,
"times": {
"driving": 2631,
"serving": 900,
"waiting": 0,
"break": 0
}
}
}
]
}
このレスポンスから、各場所を最も適切な車両で訪問する最も適切な順序と、走行距離と、個々のジョブを実行する車両の積載量に適合する車両総積載量と、運転、サービス、待ち、シフト休憩に対する正確なタイミングを含む総運行時間を確認できます。
異なるジョブタイプを含む問題
1 つの問題で複数のジョブの種類 ( 集荷と配達 ) を設定する場合は、次のように問題を設定する必要があります。
{
"fleet": {
"types": [
{
"id": "d3e7bb8d20c5",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.05
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T19:03:00Z",
"location": {
"lat": 52.43119084052164,
"lng": 13.39255783460401
}
}
}
],
"capacity": [
10
],
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.484104043903585,
"lng": 13.386732295521801
},
"duration": 840
}
],
"demand": [
5
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747735
},
"duration": 600
}
],
"demand": [
4
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"duration": 60
}
],
"demand": [
2
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087625
},
"duration": 1140
}
],
"demand": [
3
]
}
]
}
}
]
}
}
Solution
この問題の解決方法は次のとおりです。
{
"statistic": {
"cost": 552.719,
"distance": 31667,
"duration": 6521,
"times": {
"driving": 3881,
"serving": 2640,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "d3e7bb8d20c5_1",
"typeId": "d3e7bb8d20c5",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
"load": [
5
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"time": {
"arrival": "2021-08-27T08:12:53Z",
"departure": "2021-08-27T08:13:53Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.484104043903585,
"lng": 13.3867322955218
},
"time": {
"arrival": "2021-08-27T08:32:38Z",
"departure": "2021-08-27T08:46:38Z"
},
"load": [
8
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087623
},
"time": {
"arrival": "2021-08-27T08:58:34Z",
"departure": "2021-08-27T09:17:34Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747737
},
"time": {
"arrival": "2021-08-27T09:24:00Z",
"departure": "2021-08-27T09:34:00Z"
},
"load": [
9
],
"activities": [
{
"jobId": "job_2",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.43119084052164,
"lng": 13.39255783460401
},
"time": {
"arrival": "2021-08-27T09:51:41Z",
"departure": "2021-08-27T09:51:41Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 552.719,
"distance": 31667,
"duration": 6521,
"times": {
"driving": 3881,
"serving": 2640,
"waiting": 0,
"break": 0
}
}
}
]
}
このソリューションで、最も適切な車両で集荷・配達ジョブを実行する最も適切な順序と、走行距離と、個々のジョブを実行する車両の積載量に適合する車両総積載量と、運転、サービス、待ち、シフト休憩に対する正確なタイミングを含む総運行時間を確認できます。
複数の次元
車両の積載量は複数の次元で指定できます。 この機能は、たとえば、パレット数と重量の両面でトラックが過積載になっていないことを確認する必要がある、ミドルマイルのロジスティクス企業で使用できます。 このようにして、希望する単位で表現されたアイテム数だけでなく、サイズや重量なども指定できます たとえば、トラックを使用する場合は、パレット数とその重量を指定できます。 積載量の単位は累積する必要があります。つまり、長さや高さなどの寸法は指定できませんが、ユニットの重量などを使用できます。 ジョブの需要は同じ次元で指定され、容量データを考慮して計算されます。 このような制約を設定するには、車両の積載量とジョブの需要の両方を、コンマで区切って正確に同じ順序で指定する必要があります。
以下では、積載量がそれぞれ 50 ユニットと 20 ユニットの 2 台の車両で、経路指定の問題に対する制約を指定する方法を説明します。 この問題では、 2 つの集荷ジョブと 2 つの配達ジョブを実行する必要があります。ジョブの需要( 50 、 20 )は、車両の積載量と同じ順序で指定されます。
{
"fleet": {
"types": [
{
"id": "069ea42ae3e9",
"profile": "car_1",
"costs": {
"fixed": 10.0,
"distance": 0.07,
"time": 0.1
},
"shifts": [
{
"start": {
"time": "2021-07-10T08:37:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-07-10T17:37:00Z",
"location": {
"lat": 52.5281430596138,
"lng": 13.36381375834569
}
}
}
],
"capacity": [
50,20
],
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.484104043903585,
"lng": 13.386732295521801
},
"duration": 840
}
],
"demand": [
50, 20
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747735
},
"duration": 600
}
],
"demand": [
50, 20
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"duration": 60
}
],
"demand": [
50, 20
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087625
},
"duration": 1140
}
],
"demand": [
50, 20
]
}
]
}
}
]
}
}
このような問題の解決策を確認すると、 2 台の車両が、その積載量と 2 つのディメンションで指定された作業要求に基づいて集荷と配達の作業を行うことがわかります。
{
"statistic": {
"cost": 3663.9000000000005,
"distance": 41390,
"duration": 7466,
"times": {
"driving": 4826,
"serving": 2640,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "069ea42ae3e9_2",
"typeId": "069ea42ae3e9",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-07-10T08:37:00Z",
"departure": "2021-07-10T08:37:00Z"
},
"load": [
50,
20
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"time": {
"arrival": "2021-07-10T08:46:29Z",
"departure": "2021-07-10T08:47:29Z"
},
"load": [
0,
0
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.484104043903585,
"lng": 13.3867322955218
},
"time": {
"arrival": "2021-07-10T09:04:35Z",
"departure": "2021-07-10T09:18:35Z"
},
"load": [
50,
20
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.5281430596138,
"lng": 13.36381375834569
},
"time": {
"arrival": "2021-07-10T09:30:33Z",
"departure": "2021-07-10T09:30:33Z"
},
"load": [
0,
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 1642.0500000000002,
"distance": 18725,
"duration": 3213,
"times": {
"driving": 2313,
"serving": 900,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "069ea42ae3e9_1",
"typeId": "069ea42ae3e9",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-07-10T08:37:00Z",
"departure": "2021-07-10T08:37:00Z"
},
"load": [
50,
20
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087623
},
"time": {
"arrival": "2021-07-10T08:54:30Z",
"departure": "2021-07-10T09:13:30Z"
},
"load": [
0,
0
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747737
},
"time": {
"arrival": "2021-07-10T09:19:48Z",
"departure": "2021-07-10T09:29:48Z"
},
"load": [
50,
20
],
"activities": [
{
"jobId": "job_2",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.5281430596138,
"lng": 13.36381375834569
},
"time": {
"arrival": "2021-07-10T09:47:53Z",
"departure": "2021-07-10T09:47:53Z"
},
"load": [
0,
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 2021.8500000000001,
"distance": 22665,
"duration": 4253,
"times": {
"driving": 2513,
"serving": 1740,
"waiting": 0,
"break": 0
}
}
}
]
}
需要が積載量を超えている場合
輸送しようとする荷物の合計量 ( 需要 ) が利用可能な車両の総積載量を超える状況を考えてみましょう。 この状況では、優先度が指定されている場合、解決策は主にジョブの優先度に基づきます。 ジョブに優先度が指定されていない場合、すべての優先度が等しいことを意味します。そのため、最適化は挿入コスト ( 場所間の距離、待機時間、処理時間 ) に基づいて行われます。
3 ユニット分の積載量の車両を保有しているが、すべての作業の合計需要は 4 ユニットであるとします。 これらのすべてのジョブの場所が異なり、各ジョブの需要が 1 を超えていません。 このようなシナリオの問題リクエストは、次のようになります。
{
"fleet": {
"types": [
{
"id": "d3e7bb8d20c5",
"profile": "car_1",
"costs": {
"fixed": 10.0,
"distance": 0.005,
"time": 0.07
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T19:03:00Z",
"location": {
"lat": 52.43119084052164,
"lng": 13.39255783460401
}
}
}
],
"capacity": [
5
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.484104043903585,
"lng": 13.386732295521801
},
"duration": 840
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747735
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087625
},
"duration": 1140
}
],
"demand": [
1
]
}
]
}
}
]
}
}
この問題の解決方法は次のとおりです。
{
"statistic": {
"cost": 624.8050000000001,
"distance": 31667,
"duration": 6521,
"times": {
"driving": 3881,
"serving": 2640,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "d3e7bb8d20c5_1",
"typeId": "d3e7bb8d20c5",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
"load": [
2
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"time": {
"arrival": "2021-08-27T08:12:53Z",
"departure": "2021-08-27T08:13:53Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.484104043903585,
"lng": 13.3867322955218
},
"time": {
"arrival": "2021-08-27T08:32:38Z",
"departure": "2021-08-27T08:46:38Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087623
},
"time": {
"arrival": "2021-08-27T08:58:34Z",
"departure": "2021-08-27T09:17:34Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747737
},
"time": {
"arrival": "2021-08-27T09:24:00Z",
"departure": "2021-08-27T09:34:00Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_2",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.43119084052164,
"lng": 13.39255783460401
},
"time": {
"arrival": "2021-08-27T09:51:41Z",
"departure": "2021-08-27T09:51:41Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 624.8050000000001,
"distance": 31667,
"duration": 6521,
"times": {
"driving": 3881,
"serving": 2640,
"waiting": 0,
"break": 0
}
}
}
]
}
このソリューションでは、車両の総コスト、所要時間、走行距離に関する情報を、各場所で最適なルートで取得できます。 同時に、超過需要のために現在のツアー内の車両が実行できなかった作業については、以下の説明とともに記載されます。 "capacity_constraint- does not fit any vehicle due to capacity" (容量の制約により、どの車両にも積載できません)
この状況では、問題の定義を再確認する必要があります。車両を追加するか、または需要に対応する積載量の車両を変更して、問題を解決してください。
高度なヒント
車両が受け取る荷物の数の制限など、他の目的にも積載量 - 需要の相互関係を使用できます。 ジョブの需要を 1 、車両の積載量を 10 などに指定すると、車両は積載量で指定された量( 10 など)を超える荷物を受け取れません。