休憩を伴う VRP
ドライバーがシフト中に休憩を取ることがよくあります。最もよくあるケースは、たとえば昼休みです。ジョブに対する休憩時間枠が指定されたツアーを計画する場合、それらの休憩を考慮する必要があります。 実際には、休憩時間枠の任意の場所で休憩が発生することがあります。 Breaksには、プロパティduration
と times
が必要です。 車両に休憩が定義されている場合、休憩時間が shiftTime
に追加されます。 以下の例では、3 台の車両に固定シフトと休憩があり、特定の時間枠で実行すべき 6 つの作業があります。
Problems
{
"fleet": {
"types": [
{
"id": "6290a20b08a7",
"profile": "car_1",
"costs": {
"fixed": 10.0,
"distance": 0.001,
"time": 0.006
},
"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
}
},
"breaks": [
{
"duration": 1800,
"times": [
[
"2021-08-27T12:03:00Z",
"2021-08-27T13:03:00Z"
]
]
}
]
}
],
"capacity": [
7
],
"limits": {
"maxDistance": 300000
},
"amount": 1
},
{
"id": "973bccabf941",
"profile": "car_1",
"costs": {
"fixed": 12.0,
"distance": 0.004,
"time": 0.005
},
"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
}
},
"breaks": [
{
"duration": 1800,
"times": [
[
"2021-08-27T11:03:00Z",
"2021-08-27T13:03:00Z"
]
]
}
]
}
],
"capacity": [
3
],
"limits": {
"maxDistance": 300000
},
"amount": 1
},
{
"id": "92d3cd5cca04",
"profile": "car_1",
"costs": {
"fixed": 10.0,
"distance": 0.004,
"time": 0.009
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T17:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"breaks": [
{
"duration": 1800,
"times": [
[
"2021-08-27T12:03:00Z",
"2021-08-27T13:03:00Z"
]
]
}
]
}
],
"capacity": [
2
],
"limits": {
"maxDistance": 300000
},
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T09:03:00Z",
"2021-08-27T10:03:00Z"
]
],
"location": {
"lat": 52.59175589353722,
"lng": 13.350747750372257
},
"duration": 360
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T14:03:00Z",
"2021-08-27T16:03:00Z"
]
],
"location": {
"lat": 52.43363386232821,
"lng": 13.403232562191313
},
"duration": 540
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T10:03:00Z",
"2021-08-27T16:03:00Z"
]
],
"location": {
"lat": 52.473321658918245,
"lng": 13.28972099097991
},
"duration": 660
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T06:03:00Z",
"2021-08-27T17:03:00Z"
]
],
"location": {
"lat": 52.54165532725351,
"lng": 13.365047170290309
},
"duration": 1140
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_5",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T06:03:00Z",
"2021-08-27T17:03:00Z"
]
],
"location": {
"lat": 52.569368,
"lng": 13.314579
},
"duration": 1140
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T06:03:00Z",
"2021-08-27T17:03:00Z"
]
],
"location": {
"lat": 52.593857,
"lng": 13.338440
},
"duration": 1140
}
],
"demand": [
1
]
}
]
}
}
]
}
}
Solution
このような問題の解決策は次のとおりです。
{
"statistic": {
"cost": 180.973,
"distance": 63465,
"duration": 17918,
"times": {
"driving": 6897,
"serving": 4980,
"waiting": 4241,
"break": 1800
}
},
"tours": [
{
"vehicleId": "6290a20b08a7_1",
"typeId": "6290a20b08a7",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T09:43:41Z"
},
"load": [
6
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.59175589353722,
"lng": 13.350747750372255
},
"time": {
"arrival": "2021-08-27T10:03:00Z",
"departure": "2021-08-27T10:09:00Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.593857,
"lng": 13.33844
},
"time": {
"arrival": "2021-08-27T10:13:08Z",
"departure": "2021-08-27T10:32:08Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_6",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.569368,
"lng": 13.314579
},
"time": {
"arrival": "2021-08-27T10:40:26Z",
"departure": "2021-08-27T10:59:26Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_5",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.54165532725351,
"lng": 13.365047170290309
},
"time": {
"arrival": "2021-08-27T11:10:41Z",
"departure": "2021-08-27T12:33:00Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_4",
"type": "delivery",
"location": {
"lat": 52.54165532725351,
"lng": 13.365047170290309
},
"time": {
"start": "2021-08-27T11:10:41Z",
"end": "2021-08-27T11:29:41Z"
}
},
{
"jobId": "break",
"type": "break",
"location": {
"lat": 52.54165532725351,
"lng": 13.365047170290309
},
"time": {
"start": "2021-08-27T11:29:41Z",
"end": "2021-08-27T12:33:00Z"
}
}
]
},
{
"location": {
"lat": 52.473321658918245,
"lng": 13.28972099097991
},
"time": {
"arrival": "2021-08-27T12:54:53Z",
"departure": "2021-08-27T13:05:53Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.43363386232821,
"lng": 13.403232562191311
},
"time": {
"arrival": "2021-08-27T13:25:38Z",
"departure": "2021-08-27T14:12:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_2",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T14:42:19Z",
"departure": "2021-08-27T14:42:19Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 180.973,
"distance": 63465,
"duration": 17918,
"times": {
"driving": 6897,
"serving": 4980,
"waiting": 4241,
"break": 1800
}
}
}
]
}
このソリューションでは、総コスト、走行距離、走行時間、休憩時間、休憩時間など、ツアーのルーチンに関するすべての統計情報を確認できます。車両のシフト休憩も考慮され、それらの制約を考慮してツアーが計画されました。
現在、Breaks機能はソフト制約として実装されているため、場合によっては、追加のジョブを優先してアルゴリズムによってBreaksがスキップされる可能性があることに注意してください (たとえば、休憩を挿入すると、割り当てられていないジョブの量が大幅に増加する場合)。