オープン VRP
これは、配送会社が自社スタッフ以外の車両を使用する場合に非常に頻繁に発生します。これは、それらの車両がデポに戻らない可能性があるか、請負業者として特定のシフトで勤務する可能性があることを意味します。このような問題は、オープン VRP と呼ばれます。 オープン VRP では、配達会社の従業員ではない請負業者が自身の車両を使用し、最後の顧客のサービスを行った後、デポには戻りません。オープン VRP は、製品やサービスの宅配、フードデリバリーなど、現実の生活で遭遇する可能性があります
Open VRP は、オープン パス形式という独特の特徴を持つ配車ルート問題の変形です。これは、すべてのタスクを完了した後で車両をデポに戻す必要がないことを意味します。そのため、このような問題の主な制約は、集荷場所と配達場所、および車両の時間シフトです。
基本的に、オープン VRP を構築するには、シフトの終了時間と位置を追加せずに、希望する車両にシフトの開始時間と位置を追加して、最後にサービスを受けた作業場所で車両の配達を完了できるようにする必要があります。
シフトの重複を避けるため、1 つのツアーで 1 台の車両に複数の空きシフト (終了時間のないシフト) を使用することはできないことに注意してください。車両に複数のシフトを設定する必要がある場合、車両の最後のシフトのみがシフト終了時間を持たないことが許可されます。そうしないと、検証エラーが返されます。
配達会社が顧客に製品を配達するために 2 台の車両を使用する状況について考えてみましょう。 これらの車両は会社に属しておらず、ドライバーは請負業者です。 会社には、これらの車両が配達を開始するデポはありませんが、配達する必要がある商品を受け取る必要がある倉庫があります。
そのため、この倉庫の場所が両方の車両の出発地点になります。 最終配達を行った後、車両をデポに戻す必要がないことを考慮すると、最終配達時に配達を終了します。 また、この状況では、ドライバーの作業時間を制御するために、車両の制限時間の shiftTime を設定する必要があります。
Problems
上記のすべての制約事項を考慮すると、この特定の未完了の VRP の問題は次のようになります。
{
"fleet": {
"types": [
{
"id": "048d43e6e61c",
"profile": "car_1",
"costs": {
"fixed": 10.0,
"distance": 0.002,
"time": 0.01
},
"shifts": [
{
"start": {
"time": "2021-07-13T08:20:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
100
],
"limits": {
"shiftTime": 43200
},
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.513365341037485,
"lng": 13.325000854641972
},
"duration": 780
}
],
"demand": [
40
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"duration": 120
}
],
"demand": [
5
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"duration": 360
}
],
"demand": [
10
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.55783238016377,
"lng": 13.304436007504957
},
"duration": 720
}
],
"demand": [
10
]
}
]
}
},
{
"id": "job_5",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.60592698633012,
"lng": 13.360660447014226
},
"duration": 240
}
],
"demand": [
5
]
}
]
}
},
{
"id": "job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.547429320898374,
"lng": 13.303190999428224
},
"duration": 780
}
],
"demand": [
15
]
}
]
}
}
]
}
}
Solution
このような問題の解決策は次のとおりです。
{
"statistic": {
"cost": 267.092,
"distance": 73626,
"duration": 10984,
"times": {
"driving": 7984,
"serving": 3000,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "048d43e6e61c_2",
"typeId": "048d43e6e61c",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-07-13T08:20:00Z",
"departure": "2021-07-13T08:20:00Z"
},
"load": [
35
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"time": {
"arrival": "2021-07-13T08:48:16Z",
"departure": "2021-07-13T08:54:16Z"
},
"load": [
45
],
"activities": [
{
"jobId": "job_3",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.513365341037485,
"lng": 13.325000854641972
},
"time": {
"arrival": "2021-07-13T09:19:01Z",
"departure": "2021-07-13T09:32:01Z"
},
"load": [
85
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.547429320898374,
"lng": 13.303190999428224
},
"time": {
"arrival": "2021-07-13T09:48:41Z",
"departure": "2021-07-13T10:01:41Z"
},
"load": [
70
],
"activities": [
{
"jobId": "job_6",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.55783238016377,
"lng": 13.304436007504956
},
"time": {
"arrival": "2021-07-13T10:11:56Z",
"departure": "2021-07-13T10:23:56Z"
},
"load": [
60
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.60592698633012,
"lng": 13.360660447014226
},
"time": {
"arrival": "2021-07-13T10:40:28Z",
"departure": "2021-07-13T10:44:28Z"
},
"load": [
55
],
"activities": [
{
"jobId": "job_5",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"time": {
"arrival": "2021-07-13T11:21:04Z",
"departure": "2021-07-13T11:23:04Z"
},
"load": [
50
],
"activities": [
{
"jobId": "job_2",
"type": "delivery"
}
]
}
],
"statistic": {
"cost": 267.092,
"distance": 73626,
"duration": 10984,
"times": {
"driving": 7984,
"serving": 3000,
"waiting": 0,
"break": 0
}
}
}
]
}
このソリューションから、制約に関連して訪問したすべての場所での運転とサービスに費やした総コスト、所要時間、距離、時間など、車両のツアーの統計を確認できます。 車両の最後のアクティビティ時間と場所がツアーの最後の時間と場所であることに注意してください。