オープン VRP
これは、配送会社が自社スタッフ以外の車両を使用する場合に非常に頻繁に発生します。これは、それらの車両がデポに戻らない可能性があるか、請負業者として特定のシフトで勤務する可能性があることを意味します。このような問題は、オープン VRP と呼ばれます。 オープン VRP では、配達会社の従業員ではない請負業者が自身の車両を使用し、最後の顧客のサービスを行った後、デポには戻りません。オープン VRP は、製品やサービスの宅配、フードデリバリーなど、現実の生活で遭遇する可能性があります
オープン VRP は、車両ルーティングの問題の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
}
}
}
]
}
このソリューションでは、車両のツアーの統計情報を確認できます。これには、制約条件を考慮し、総コスト、所要時間、走行距離、運転にかかる時間、訪問するすべての場所でのサービスに費やす時間が含まれます。