複数ジョブの VRP
単純なジョブとは対照的に、複数のジョブは複数の集荷と配達で構成されるジョブです。 このようなジョブに特徴的なことは、ジョブ内のすべてのタスクが完了したときにのみ実行済みと見なすことができるということです。それが不可能な場合、どのジョブも実行されません。 また、集荷と配達の需要の合計も同じである必要があります。 複数ジョブの問題でよくあるシナリオは、さまざまな場所で複数の集荷を行ってから、1 つの場所に配達するということです。
現実の複数ジョブのVRP を、たとえば、異なる住所で数人の子供を乗せて学校に降ろさなければならないスクールバスの日常業務として想像できます。論理的に、同じスクールバスによって学校からの彼らの家に戻すことも、複数ジョブのVRP です
実環境での複数ジョブの VRP の使用例としては、次のものがあります。
- オンデマンドの配車サービス - 複数の集荷場所から同じ方向に移動したい複数の人が、 1 台の車両をオンデマンドで使用します。
- チャーター輸送による、さまざまな場所の従業員の職場 / オフィス / 会社の施設への輸送。
- 最大 3 つの拠点 / 配送センターから荷物を受け取り、その配達先をショップ / サブ DC に配送します。
複数の集荷と配達を行う複数ジョブがあるとしましょう。 たとえば、特定の住所からスクールバスを経由して、 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 つの場所で配達するという問題を作成してみましょう。
Problems
{
"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
]
}
]
}
}
]
}
}
Solution
この問題の解決方法は次のとおりです。
{
"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"
}
]
},
{
"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"
}
]
},
{
"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"
}
]
},
{
"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"
}
]
},
{
"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"
}
]
},
{
"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"
}
]
}
],
"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 つの配達があります。 このような制約の問題は、次のようになります。
Problems
{
"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
]
}
]
}
}
]
}
}
Solution
このような制約の解決策は次のとおりです。
{
"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"
}
]
},
{
"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"
}
]
},
{
"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"
}
]
},
{
"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"
}
]
},
{
"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"
}
]
},
{
"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"
}
]
},
{
"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"
}
]
},
{
"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"
}
]
},
{
"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"
}
]
},
{
"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"
}
]
},
{
"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"
}
]
},
{
"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"
}
}
]
},
{
"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"
}
]
}
],
"statistic": {
"cost": 505.63500000000005,
"distance": 66289,
"duration": 18306,
"times": {
"driving": 7326,
"serving": 10980,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}
上記の解決策からわかるように、複数の作業が完了したかどうかにかかわらず、さまざまな作業の作業タスクが提供されるように、ツアーが最適化されます。車両は、異なる作業の集荷を行い、その後配達を行います。
-
job_1
-- Address_3
pickup
-
job_1
-- Address_1
pickup
-
job_1
-- Address_2
pickup
-
job_2
-- Address_6
pickup
-
job_2
-- Address_5
pickup
-
job_2
-- Address_7
pickup
-
job_3
-- Address_11
pickup
-
job_1
-- Address_4
delivery
-
job_3
-- Address_10
pickup
-
job_3
-- Address_9
pickup
-
job_3
-- Address_12
delivery
-
job_2
-- Address_8
delivery