優先度を伴うジョブ VRP
VRP の問題を解決するには、ジョブの優先度を考慮する必要がある場合があります。 たとえば、今日実行する必要がある緊急のジョブがいくつかあり、緊急ではないため延期できるジョブがあるとします。 同時に、保有車両で、緊急でないジョブの一部を緊急のジョブとともに実行できます。この機会を使用して、できるだけ多くのジョブを実行したいと考えています。 この場合、ジョブの優先順位を設定することが必要です。
優先度を設定する場合、優先度だけが実行に対する制約になるのではなく、他のすべての制約も考慮されることに注意してください。このため、アルゴリズムは、優先度の高いジョブをスキップしないようにし、制約のためにすべてのジョブを処理できないシナリオでは、優先度の低いジョブをまずスキップします。 優先度レベルは、ツアーでのジョブの直接的な順序を意味するものではありません。その位置は、実際にはルート内のどこにでもありえ、必ずしも優先度の低いジョブよりも前にあるとは限りません。
1 台の車両の積載量が 5 である状況を考えてみましょう。 そのうちの 3 つは優先度が設定されておらず、別の 3 つは優先度 1 であることを考慮して、6 つの集荷ジョブを実行する必要があります。つまり、他のすべての制約が満たされている場合、これらの 3 つのジョブは残りの前にツアーに組み込まれる必要があります。 同時に、車両の容量が全体的なジョブの需要を満たしていないことも理解しています。そのため、一部のジョブは実行されず、それらのジョブは非優先ジョブになると予想されます。このため、次の制約があります。
-
車両積載量 - 5
-
job_1 - 優先度なし
- job_2 - 優先度なし
- job_3 - 優先度なし
- job_4 - 優先度 1
- job_5 - 優先度 1
- job_6 - 優先度 1
このような状況では、次のような問題が発生します。
Problems
{
"fleet": {
"types": [
{
"id": "7f5209042664",
"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-27T16:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
5
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.585527238853984,
"lng": 13.364236346248592
},
"duration": 840
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.47946109276297,
"lng": 13.298179193858115
},
"duration": 1140
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.60291926054419,
"lng": 13.440503699397226
},
"duration": 780
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_4",
"priority": 1,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.505480479124714,
"lng": 13.42064470670394
},
"duration": 540
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_5",
"priority": 1,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.56627920665773,
"lng": 13.338970191939882
},
"duration": 720
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_6",
"priority": 1,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.50945064762406,
"lng": 13.385190908809543
},
"duration": 840
}
],
"demand": [
1
]
}
]
}
}
]
}
}
Solution
{
"statistic": {
"cost": 689.597,
"distance": 37371,
"duration": 8460,
"times": {
"driving": 4740,
"serving": 3720,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "7f5209042664_1",
"typeId": "7f5209042664",
"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.56627920665773,
"lng": 13.338970191939882
},
"time": {
"arrival": "2021-08-27T08:17:26Z",
"departure": "2021-08-27T08:29:26Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_5",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.585527238853984,
"lng": 13.364236346248592
},
"time": {
"arrival": "2021-08-27T08:37:10Z",
"departure": "2021-08-27T08:51:10Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.60291926054419,
"lng": 13.440503699397226
},
"time": {
"arrival": "2021-08-27T09:06:18Z",
"departure": "2021-08-27T09:19:18Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_3",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.505480479124714,
"lng": 13.42064470670394
},
"time": {
"arrival": "2021-08-27T09:44:37Z",
"departure": "2021-08-27T09:53:37Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_4",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.50945064762406,
"lng": 13.385190908809545
},
"time": {
"arrival": "2021-08-27T10:01:52Z",
"departure": "2021-08-27T10:15:52Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_6",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T10:24:00Z",
"departure": "2021-08-27T10:24:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 689.597,
"distance": 37371,
"duration": 8460,
"times": {
"driving": 4740,
"serving": 3720,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": [
{
"jobId": "job_2",
"reasons": [
{
"code": "CAPACITY_CONSTRAINT",
"description": "does not fit into any vehicle due to capacity"
}
]
}
]
}
Solutionの評価
このソリューションでは、ジョブが次の順序で実行されます。
- job_5
- job_1
- job_3.
- job_4.
- job_6
つまり、優先度の高いジョブは必ずしも最初に実行されるわけではありませんが、他のジョブ(優先度のないジョブ)よりも前にツアープランに含まれます。 アルゴリズムに応じて、場所、ジョブタイプ、優先度を含むすべての制約がツアーの計画時に考慮され、優先度の高いジョブ(job_4 および job_6)が最初に実行されることはありませんが、優先度は他の制約と共に考慮され、これらのジョブがツアーに含まれます。 同時に、 job_2 が車両の積載量のために実行されなかったことがわかります。これは、この特定のジョブが優先順位付けられていなかったために、予想されていたことです。