マルチリロード
場合によっては、車両の容量に制限があるため、1回のツアーですべてのアイテムを配送できないことがあります。 したがって、シフト時間が許せば、より多くの品目を配送できるように、車両を複数回移動させる必要がある場合があります。 reloads
この機能により、車両はデポ(またはその他の場所)に戻り、前回のトリップのすべてのタスクが完了した後で、さらに多くのアイテムを受け取ることができます。
この使用例の最も簡単な例は、特定の容量を持つ車両と総需要が容量を超えるジョブがある場合です。 車両の能力に合わないジョブの一部は、ツアーに割り当てられないことが予想されます。 したがって、車両の容量を増やしたり車両を追加したりする機会はないが、それでも既存の車両でツアーを完了する必要がある場合は、車両に対してさらに車両を追加できるようにする問題の制約にリロード オプションを追加する必要があります。 これにより、以前のタスクが完了した後に車両がツアーに追加できるようになります。 リロードは、出発倉庫、配達場所、集荷場所、またはその他の場所で行うことができます。 リロード オプションは、次のようにリロードの location
とその duration
を含む問題の fleet
の部分に追加する必要があります。
"reloads":[
{
"location":{
"lat": 52.530976,
"lng": 13.384916
},
"duration":60
},
{
"location":{
"lat": 52.530976,
"lng": 13.384916
},
"duration":60
},
]
車両の容量が総作業需要(キャパシティ3、デマンド5)よりも小さい場合、つまり需要が車両の容量を超えている場合を考えてみましょう。 この場合は、リンクの容量制約を伴う VRPセクションでこのドキュメントを確認できます。 前述の例の車両がツアーを完了できるようにするには、 問題にオプションreloads
を追加します。 次の問題例では 、車両がツアーを開始した場所と同じ場所にreloads
を追加しました。
Problems
{
"fleet": {
"types": [
{
"id": "e429c9c1e6df",
"profile": "car_bd5be9a38474",
"costs": {
"fixed": 6.0,
"distance": 0.002,
"time": 0.007
},
"shifts": [
{
"start": {
"time": "2022-06-01T08:05:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2022-06-01T18:05:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"reloads": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"duration": 60
}
]
}
],
"capacity": [
3
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_bd5be9a38474"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2022-06-01T14:05:00Z",
"2022-06-01T18:05:00Z"
]
],
"location": {
"lat": 52.44664947511696,
"lng": 13.484988905387555
},
"duration": 300
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2022-06-01T08:05:00Z",
"2022-06-01T13:05:00Z"
]
],
"location": {
"lat": 52.632489506294235,
"lng": 13.341605471791963
},
"duration": 300
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2022-06-01T08:05:00Z",
"2022-06-01T13:05:00Z"
]
],
"location": {
"lat": 52.5983459422347,
"lng": 13.392007658723308
},
"duration": 300
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2022-06-01T08:05:00Z",
"2022-06-01T12:05:00Z"
]
],
"location": {
"lat": 52.577856866026835,
"lng": 13.423782100910442
},
"duration": 300
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_5",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2022-06-01T08:05:00Z",
"2022-06-01T13:05:00Z"
]
],
"location": {
"lat": 52.5983459422347,
"lng": 13.392007658723308
},
"duration": 300
}
],
"demand": [
1
]
}
]
}
}
]
}
}
Solution
以下の解決策から、3つのジョブを提供し、そのすべての容量を使用した後、車両はリロード場所(私たちの場合は出発デポ)に向かい、その後ツアーに残っている最後のジョブを提供することがわかります。
{
"statistic": {
"cost": 273.482,
"distance": 92161,
"duration": 11880,
"times": {
"driving": 9568,
"serving": 1560,
"waiting": 752,
"break": 0
}
},
"tours": [
{
"vehicleId": "e429c9c1e6df_1",
"typeId": "e429c9c1e6df",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2022-06-01T08:05:00Z",
"departure": "2022-06-01T11:20:56Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.577856866026835,
"lng": 13.423782100910442
},
"time": {
"arrival": "2022-06-01T11:38:11Z",
"departure": "2022-06-01T11:43:11Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_4",
"type": "pickup"
}
],
"distance": 16100
},
{
"location": {
"lat": 52.5983459422347,
"lng": 13.392007658723308
},
"time": {
"arrival": "2022-06-01T11:57:43Z",
"departure": "2022-06-01T12:07:43Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_3",
"type": "pickup",
"location": {
"lat": 52.5983459422347,
"lng": 13.392007658723308
},
"time": {
"start": "2022-06-01T11:57:43Z",
"end": "2022-06-01T12:02:43Z"
}
},
{
"jobId": "job_5",
"type": "pickup",
"location": {
"lat": 52.5983459422347,
"lng": 13.392007658723308
},
"time": {
"start": "2022-06-01T12:02:43Z",
"end": "2022-06-01T12:07:43Z"
}
}
],
"distance": 27415
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2022-06-01T12:32:18Z",
"departure": "2022-06-01T12:33:18Z"
},
"load": [
0
],
"activities": [
{
"jobId": "reload",
"type": "reload"
}
],
"distance": 36817
},
{
"location": {
"lat": 52.632489506294235,
"lng": 13.341605471791963
},
"time": {
"arrival": "2022-06-01T13:05:00Z",
"departure": "2022-06-01T13:10:00Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_2",
"type": "pickup"
}
],
"distance": 44396
},
{
"location": {
"lat": 52.44664947511696,
"lng": 13.484988905387556
},
"time": {
"arrival": "2022-06-01T13:52:28Z",
"departure": "2022-06-01T14:10:00Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
],
"distance": 65595
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2022-06-01T14:38:56Z",
"departure": "2022-06-01T14:38:56Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 82587
}
],
"statistic": {
"cost": 273.482,
"distance": 92161,
"duration": 11880,
"times": {
"driving": 9568,
"serving": 1560,
"waiting": 752,
"break": 0
}
},
"shiftIndex": 0
}
]
}
これが基本的にこのオプションreloads
が機能する方法ですが、場合によっては、リロードを使用するときに他の制約を考慮する必要があります。 以下では、複数のリロードがあり、さらにリロードがデポ以外の場所でも行われる問題の例を作成してみましょう。 さらに、リロード場所は日中の特定の時間に稼働するため、リロードの時間帯も考慮する必要があります。
ツアープランでは 、車両シフトごとにreloads
を最大5つまで追加できます。 それぞれの reloads
は、独自の location
、duration
、および times
を持つことができます (オプション)。
次の例では、需要が容量を超える状況が再び発生しています(容量5と 7ジョブのリクエスト)だけでなく、リロードのための特定の時間帯もあり、車両シフト時間の制約に追加します。 また、リロードの場所を追加できますが、デポだけではありません。 この例では、リロードの1つは車両出発地(デポ)で行われ、もう1つはいずれかの作業場所で行われます。
Problems
{
"fleet": {
"types": [
{
"id": "e429c9c1e6df",
"profile": "car_bd5be9a38474",
"costs": {
"fixed": 6.0,
"distance": 0.002,
"time": 0.007
},
"shifts": [
{
"start": {
"time": "2022-06-01T08:05:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2022-06-01T18:05:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"reloads": [
{
"times": [
[
"2022-06-01T09:05:00Z",
"2022-06-01T13:05:00Z"
]
],
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"duration": 60
},
{
"times": [
[
"2022-06-01T13:05:00Z",
"2022-06-01T18:05:00Z"
]
],
"location": {
"lat": 52.57541509905306,
"lng": 13.409878314747719
},
"duration": 60
}
]
}
],
"capacity": [
5
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_bd5be9a38474"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2022-06-01T09:05:00Z",
"2022-06-01T13:05:00Z"
]
],
"location": {
"lat": 52.44664947511696,
"lng": 13.484988905387555
},
"duration": 300
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2022-06-01T08:05:00Z",
"2022-06-01T13:05:00Z"
]
],
"location": {
"lat": 52.632489506294235,
"lng": 13.341605471791963
},
"duration": 300
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2022-06-01T08:05:00Z",
"2022-06-01T13:05:00Z"
]
],
"location": {
"lat": 52.5983459422347,
"lng": 13.392007658723308
},
"duration": 300
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2022-06-01T08:05:00Z",
"2022-06-01T12:05:00Z"
]
],
"location": {
"lat": 52.577856866026835,
"lng": 13.423782100910442
},
"duration": 300
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_5",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2022-06-01T09:05:00Z",
"2022-06-01T14:05:00Z"
]
],
"location": {
"lat": 52.57541509905306,
"lng": 13.409878314747719
},
"duration": 300
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_6",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2022-06-01T09:05:00Z",
"2022-06-01T14:05:00Z"
]
],
"location": {
"lat": 52.486595664301646,
"lng": 13.423728674699783
},
"duration": 300
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_7",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2022-06-01T08:05:00Z",
"2022-06-01T13:05:00Z"
]
],
"location": {
"lat": 52.471783668934606,
"lng": 13.469038314828833
},
"duration": 300
}
],
"demand": [
1
]
}
]
}
}
]
}
}
Solution
以下の解決策から、車両が job_2
、 job_3
、 job_6
、 job_1
、および job_7
を処理し、指定された時間内にデポの場所でリロードを行うことがわかります。 その後 job_5
と job_4
が提供されます。
{
"statistic": {
"cost": 260.9809999999999,
"distance": 81441,
"duration": 13157,
"times": {
"driving": 10997,
"serving": 2160,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "e429c9c1e6df_1",
"typeId": "e429c9c1e6df",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2022-06-01T08:05:00Z",
"departure": "2022-06-01T08:05:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.632489506294235,
"lng": 13.341605471791963
},
"time": {
"arrival": "2022-06-01T08:36:42Z",
"departure": "2022-06-01T08:41:42Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_2",
"type": "pickup"
}
],
"distance": 6640
},
{
"location": {
"lat": 52.5983459422347,
"lng": 13.392007658723308
},
"time": {
"arrival": "2022-06-01T09:05:56Z",
"departure": "2022-06-01T09:10:56Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_3",
"type": "pickup"
}
],
"distance": 8022
},
{
"location": {
"lat": 52.486595664301646,
"lng": 13.423728674699785
},
"time": {
"arrival": "2022-06-01T09:49:34Z",
"departure": "2022-06-01T09:54:34Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_6",
"type": "pickup"
}
],
"distance": 24199
},
{
"location": {
"lat": 52.44664947511696,
"lng": 13.484988905387556
},
"time": {
"arrival": "2022-06-01T10:10:22Z",
"departure": "2022-06-01T10:15:22Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
],
"distance": 29363
},
{
"location": {
"lat": 52.471783668934606,
"lng": 13.469038314828833
},
"time": {
"arrival": "2022-06-01T10:24:23Z",
"departure": "2022-06-01T10:29:23Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_7",
"type": "pickup"
}
],
"distance": 37457
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2022-06-01T10:56:26Z",
"departure": "2022-06-01T10:57:26Z"
},
"load": [
0
],
"activities": [
{
"jobId": "reload",
"type": "reload"
}
],
"distance": 45849
},
{
"location": {
"lat": 52.57541509905306,
"lng": 13.40987831474772
},
"time": {
"arrival": "2022-06-01T11:12:34Z",
"departure": "2022-06-01T11:17:34Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_5",
"type": "pickup"
}
],
"distance": 61949
},
{
"location": {
"lat": 52.577856866026835,
"lng": 13.423782100910442
},
"time": {
"arrival": "2022-06-01T11:21:24Z",
"departure": "2022-06-01T11:26:24Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_4",
"type": "pickup"
}
],
"distance": 73264
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2022-06-01T11:44:17Z",
"departure": "2022-06-01T11:44:17Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 82666
}
],
"statistic": {
"cost": 260.9809999999999,
"distance": 81441,
"duration": 13157,
"times": {
"driving": 10997,
"serving": 2160,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}