複数ジョブの VRP
単純なジョブとは対照的に、複数のジョブは複数の集荷と配達で構成されるジョブです。 このようなジョブに特徴的なことは、ジョブ内のすべてのタスクが完了したときにのみ実行済みと見なすことができるということです。それが不可能な場合、どのジョブも実行されません。 また、集荷と配達の需要の合計も同じである必要があります。 複数ジョブの問題でよくあるシナリオは、さまざまな場所で複数の集荷を行ってから、1 つの場所に配達するということです。
複数ジョブの VRP は、たとえば、異なる住所の複数の子供を乗せて学校に送り届けるスクールバスの日常業務のように現実のものです。 私達が推測できるように、同じスクールバスによって学校から彼らの家に子供を送り返すこともまた複数ジョブの VRP である。
複数ジョブの VRP を実際に使用するもう 1 つの例は、車両が複数の集荷と 1 つの配達をジョブ内で実行する必要がある場合のゴミ収集会社の作業です (都市の複数の場所からゴミを収集して、集積場所に配達)。
複数の集荷と一つの配達を行う一連ののジョブがあるとしましょう。たとえば、特定の住所からスクールバスで 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 つの方法は、すべての集荷を個別のジョブとして追加してから、配達ジョブを追加することです。 もう 1 つの方法は、1 つの「複数ジョブ」を使用することです。この方法では、すべての集荷と最後に配達を行う複数ジョブを追加できます。集荷した全ての荷物を 1 箇所に届ける、3つの集荷と 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 つの配達の複数ジョブを実行してデポに到着することを確認できます。