ジョブごとに複数のタスクを処理する
単純なジョブとは対照的に、マルチジョブは複数の集荷と配送で構成されるジョブです。このようなジョブの特徴として、ジョブ内のすべてのタスクが完了した場合にのみ遂行されたと見なされ、そうでなければどのタスクも遂行されていないと見なされます。また、集荷と配達の需要の合計が等しくなければなりません。マルチジョブの問題の非常に一般的なシナリオは、異なる場所で複数の集荷を遂行してから、1つの場所に配達するというものです。
現実のマルチジョブVRPとして、たとえば、異なる住所で数人の子供を乗せて学校に降ろさなければならないスクールバスの日常業務を想像できます。論理的には、同じスクールバスで子供たちを学校から家に連れていくこともマルチジョブVRPです。
マルチジョブVRPの実際の使用例としては、他に次のようなものがあります。
- オンデマンドのライドシェア - 1台の車両をオンデマンドで使用して、異なる乗車場所から複数の人が同じ方面に移動する。
- チャーター輸送によって従業員を異なる場所から作業現場/オフィス/企業施設に輸送する。
- 商品が最大3か所の集配センター/配達センターから集荷され、ショップ/サブDCに配達される。
それでは、複数の集荷と1つの配達を含むマルチジョブがあるとしましょう。3人の子供を特定の住所からスクールバスで地元の学校に連れていく必要があるとします。バスで他の3人の子供たちを別の学校に連れていくには、問題に別のマルチジョブを追加します。車両に関しては、1つの集配センター、つまり同じ場所でシフトを開始および終了する必要があります。コスト、距離、シフト時間、積載人数、量などの日常的な車両の制約を指定します。ただし、たとえばスクールバスの場合、積載単位を人/子供と仮定できます。
{
"fleet": {
"types": [
{
"id": "b0130d2f754d",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.002
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T16:03:00Z",
"location": {
"lat": 52.48693181589403,
"lng": 13.308748991045801
}
}
}
],
"capacity": [
20
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},ジョブに関しては、このケースでは、すべての乗車 (集荷) と最後に1つの降車 (配達) を含むマルチジョブを指定できます。マルチジョブごとに最大3つの乗車/降車が可能です。3つの乗車と1つの降車を含む1つのマルチジョブがあり、乗車したすべての子供を1つの場所で降車させるという問題を作成してみましょう。
問題
{
"fleet": {
"types": [
{
"id": "b0130d2f754d",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.002
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T16:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
30
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.47706593757918,
"lng": 13.390815701172201
},
"duration": 660,
"tag": "Address_1"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.473571009931106,
"lng": 13.389035169086807
},
"duration": 1140,
"tag": "Address_2"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.53090538774364,
"lng": 13.384692097156309
},
"duration": 840,
"tag": "Address_3"
}
],
"demand": [
1
]
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.58919138279804,
"lng": 13.462161100698735
},
"duration": 1020,
"tag": "Address_4"
}
],
"demand": [
3
]
}
]
}
}
]
}
}ソリューション
この問題のソリューションは次のようになります。
{
"statistic": {
"cost": 273.77500000000003,
"distance": 36041,
"duration": 8244,
"times": {
"driving": 4584,
"serving": 3660,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "b0130d2f754d_1",
"typeId": "b0130d2f754d",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.53090538774364,
"lng": 13.384692097156307
},
"time": {
"arrival": "2021-08-27T08:03:02Z",
"departure": "2021-08-27T08:17:02Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"jobTag": "Address_3"
}
],
"distance": 17
},
{
"location": {
"lat": 52.473571009931106,
"lng": 13.389035169086808
},
"time": {
"arrival": "2021-08-27T08:34:57Z",
"departure": "2021-08-27T08:53:57Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"jobTag": "Address_2"
}
],
"distance": 8305
},
{
"location": {
"lat": 52.47706593757918,
"lng": 13.3908157011722
},
"time": {
"arrival": "2021-08-27T08:54:51Z",
"departure": "2021-08-27T09:05:51Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"jobTag": "Address_1"
}
],
"distance": 8827
},
{
"location": {
"lat": 52.58919138279804,
"lng": 13.462161100698737
},
"time": {
"arrival": "2021-08-27T09:40:21Z",
"departure": "2021-08-27T09:57:21Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_1",
"type": "delivery",
"jobTag": "Address_4"
}
],
"distance": 25365
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T10:20:24Z",
"departure": "2021-08-27T10:20:24Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 36263
}
],
"statistic": {
"cost": 273.77500000000003,
"distance": 36041,
"duration": 8244,
"times": {
"driving": 4584,
"serving": 3660,
"waiting": 0,
"break": 0
}
}
}
]
}このソリューションから、車両が集配センターから出発し、その後3つの乗車と1つの降車のマルチジョブを実行して、集配センターに戻ることがわかります。
複数のマルチジョブ
たとえば、3人以上の子供を複数の学校に連れていく必要がある問題を考えてみましょう。以下の問題では、9人の子供たちがそれぞれ異なる場所におり、子供たちを3つの異なる学校で降ろします。したがって、シナリオには3つのマルチジョブがあり、それぞれ3つの乗車と1つの降車が含まれます。このような制約の問題は次のようになります。
問題
{
"fleet": {
"types": [
{
"id": "b0130d2f754d",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.002
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T16:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
30
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.47706593757918,
"lng": 13.390815701172201
},
"duration": 660,
"tag": "Address_1"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.473571009931106,
"lng": 13.389035169086807
},
"duration": 1140,
"tag": "Address_2"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.53090538774364,
"lng": 13.384692097156309
},
"duration": 840,
"tag": "Address_3"
}
],
"demand": [
1
]
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.55919138279804,
"lng": 13.402161100698735
},
"duration": 1020,
"tag": "Address_4"
}
],
"demand": [
3
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.50706593757918,
"lng": 13.410815701172201
},
"duration": 660,
"tag": "Address_9"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.533571009931106,
"lng": 13.409035169086807
},
"duration": 1140,
"tag": "Address_10"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.59090538774364,
"lng": 13.394692097156309
},
"duration": 840,
"tag": "Address_11"
}
],
"demand": [
1
]
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.50919138279804,
"lng": 13.402161100698735
},
"duration": 1020,
"tag": "Address_12"
}
],
"demand": [
3
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.49706593757918,
"lng": 13.350815701172201
},
"duration": 660,
"tag": "Address_5"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.413571009931106,
"lng": 13.309035169086807
},
"duration": 1140,
"tag": "Address_6"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.58090538774364,
"lng": 13.344692097156309
},
"duration": 840,
"tag": "Address_7"
}
],
"demand": [
1
]
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.50919138279804,
"lng": 13.402161100698735
},
"duration": 1020,
"tag": "Address_8"
}
],
"demand": [
3
]
}
]
}
}
]
}
}ソリューション
このような制約のソリューションは次のようになります。
{
"statistic": {
"cost": 505.63500000000005,
"distance": 66289,
"duration": 18306,
"times": {
"driving": 7326,
"serving": 10980,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "b0130d2f754d_1",
"typeId": "b0130d2f754d",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.53090538774364,
"lng": 13.384692097156307
},
"time": {
"arrival": "2021-08-27T08:03:01Z",
"departure": "2021-08-27T08:17:01Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"jobTag": "Address_3"
}
],
"distance": 17
},
{
"location": {
"lat": 52.47706593757918,
"lng": 13.3908157011722
},
"time": {
"arrival": "2021-08-27T08:30:39Z",
"departure": "2021-08-27T08:41:39Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"jobTag": "Address_1"
}
],
"distance": 7780
},
{
"location": {
"lat": 52.473571009931106,
"lng": 13.389035169086808
},
"time": {
"arrival": "2021-08-27T08:43:03Z",
"departure": "2021-08-27T09:02:03Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"jobTag": "Address_2"
}
],
"distance": 8337
},
{
"location": {
"lat": 52.413571009931104,
"lng": 13.309035169086808
},
"time": {
"arrival": "2021-08-27T09:18:26Z",
"departure": "2021-08-27T09:37:26Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_2",
"type": "pickup",
"jobTag": "Address_6"
}
],
"distance": 19915
},
{
"location": {
"lat": 52.49706593757918,
"lng": 13.3508157011722
},
"time": {
"arrival": "2021-08-27T09:55:35Z",
"departure": "2021-08-27T10:06:35Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_2",
"type": "pickup",
"jobTag": "Address_5"
}
],
"distance": 31612
},
{
"location": {
"lat": 52.58090538774364,
"lng": 13.34469209715631
},
"time": {
"arrival": "2021-08-27T10:28:48Z",
"departure": "2021-08-27T10:42:48Z"
},
"load": [
6
],
"activities": [
{
"jobId": "job_2",
"type": "pickup",
"jobTag": "Address_7"
}
],
"distance": 43367
},
{
"location": {
"lat": 52.59090538774364,
"lng": 13.394692097156309
},
"time": {
"arrival": "2021-08-27T10:51:38Z",
"departure": "2021-08-27T11:05:38Z"
},
"load": [
7
],
"activities": [
{
"jobId": "job_3",
"type": "pickup",
"jobTag": "Address_11"
}
],
"distance": 48011
},
{
"location": {
"lat": 52.55919138279804,
"lng": 13.402161100698734
},
"time": {
"arrival": "2021-08-27T11:16:30Z",
"departure": "2021-08-27T11:33:30Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_1",
"type": "delivery",
"jobTag": "Address_4"
}
],
"distance": 53175
},
{
"location": {
"lat": 52.53357100993111,
"lng": 13.409035169086806
},
"time": {
"arrival": "2021-08-27T11:42:23Z",
"departure": "2021-08-27T12:01:23Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_3",
"type": "pickup",
"jobTag": "Address_10"
}
],
"distance": 57148
},
{
"location": {
"lat": 52.50706593757918,
"lng": 13.4108157011722
},
"time": {
"arrival": "2021-08-27T12:10:57Z",
"departure": "2021-08-27T12:21:57Z"
},
"load": [
6
],
"activities": [
{
"jobId": "job_3",
"type": "pickup",
"jobTag": "Address_9"
}
],
"distance": 61346
},
{
"location": {
"lat": 52.50919138279804,
"lng": 13.402161100698734
},
"time": {
"arrival": "2021-08-27T12:24:12Z",
"departure": "2021-08-27T12:58:12Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_3",
"type": "delivery",
"jobTag": "Address_12",
"location": {
"lat": 52.50919138279804,
"lng": 13.402161100698734
},
"time": {
"start": "2021-08-27T12:24:12Z",
"end": "2021-08-27T12:41:12Z"
}
},
{
"jobId": "job_2",
"type": "delivery",
"jobTag": "Address_8",
"location": {
"lat": 52.50919138279804,
"lng": 13.402161100698734
},
"time": {
"start": "2021-08-27T12:41:12Z",
"end": "2021-08-27T12:58:12Z"
}
}
],
"distance": 62122
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T13:08:06Z",
"departure": "2021-08-27T13:08:06Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 66313
}
],
"statistic": {
"cost": 505.63500000000005,
"distance": 66289,
"duration": 18306,
"times": {
"driving": 7326,
"serving": 10980,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}上記のソリューションからわかるように、マルチジョブが完了したかどうかに関係なく、さまざまなジョブからのジョブタスクが遂行される形でツアーが最適化されます。車両はさまざまなジョブからの乗車 (集荷) に対応し、その後、降車 (配達) に対応します。
job_1-Address_3-pickupjob_1-Address_1-pickupjob_1-Address_2-pickupjob_2-Address_6-pickupjob_2-Address_5-pickupjob_2-Address_7-pickupjob_3-Address_11-pickupjob_1-Address_4-deliveryjob_3-Address_10-pickupjob_3-Address_9-pickupjob_3-Address_12-deliveryjob_2-Address_8-delivery
次のステップ
詳細については、以下を参照してください。
- Submit a Vehicle Routing Problem to solve it synchronously (車両ルート検索問題を送信して同期的に解決する)
- Submit a Vehicle Routing Problem to solve it asynchronously (車両ルート検索問題を送信して非同期的に解決する)
26 日前の更新