オープンな車両ルート検索問題を解決する
オープンVRPは、オープンパス形式という独特の特徴を持つ車両ルート検索問題 (VRP) のバリエーションの1つです。これは、車両がすべてのタスクを完了した後に集配センターに戻る必要がないことを意味します。代わりに、これらの問題に対する車両シフトの主な制約は、主に集荷と配達のための場所と時間です。
これは、会社所有ではない車両を使用する配送会社に一般的なシナリオです。つまり、これらの車両は、最後の顧客に対応した後に集配センターまたは特定の場所に戻る必要がないことがあります。オープンVRP (車両ルート検索問題) は、さまざまな商品やサービスの宅配、フードデリバリー、その他の同様の業務などの実際のシナリオで発生します。
HERE Tour Planningには、開始場所または終了場所が定義されていないオープンツアーを作成する機能が用意されています。したがって、問題の定義に応じて、集荷地点と配達地点を含む任意のタスクの場所でツアーを開始または終了できます。オープンVRPの次のバリエーションがサポートされています。
- シフトの終了がない問題 (シフトの終了時刻と場所が指定されていない)
- シフトの終了場所がない問題
- シフトの開始場所がない問題
- シフトの開始場所と終了場所がない問題
このチュートリアルではいくつかの例を取り上げます。
シフトの終了がない問題
このバリエーションではシフトの終了が完全に省略されています。
配送会社が顧客に商品を配達するために車両をレンタルするシナリオを考えてみましょう。配達する商品を受け取るために、車両は集配センターや倉庫などの指定された場所から出発する必要がある場合があります。
したがって、その集配センター/倉庫の場所が車両の出発地点となります。割り当てられたタスクが完了すると、車両は集配センター/倉庫に戻ることなく自由にツアーを終了できます。さらに、ドライバーの労働時間を管理するために車両のshiftTime制限を設定できます。
このケースでは、シフトの重複を避けるために、同じツアー内の車両に対して複数のオープンシフト (終了時間のないシフト) を使用できない点が重要です。1台の車両に複数のシフトを割り当てる必要がある場合、その車両の最後のシフトにのみ終了時刻を指定しないことができます。そうしないと検証エラーが発生します。
以下は、シフトの開始 (場所あり) が定義されており、シフトの終了が定義されていない場合の一例です。
{
"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
]
}
]
}
}
]
}
}ソリューション
このような問題のソリューションは次のようになります。
{
"statistic": {
"cost": 252.23600000000002,
"distance": 71323,
"duration": 9959,
"times": {
"driving": 6959,
"serving": 3000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "048d43e6e61c_2",
"typeId": "048d43e6e61c",
"stops": [
{
"time": {
"arrival": "2021-07-13T08:20:00Z",
"departure": "2021-07-13T08:20:00Z"
},
"load": [
35
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"start": "2021-07-13T08:20:00Z",
"end": "2021-07-13T08:20:00Z"
}
}
],
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"distance": 0
},
{
"time": {
"arrival": "2021-07-13T08:43:06Z",
"departure": "2021-07-13T08:49:06Z"
},
"load": [
45
],
"activities": [
{
"jobId": "job_3",
"type": "pickup",
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"time": {
"start": "2021-07-13T08:43:06Z",
"end": "2021-07-13T08:49:06Z"
}
}
],
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"distance": 14796
},
{
"time": {
"arrival": "2021-07-13T09:11:11Z",
"departure": "2021-07-13T09:24:11Z"
},
"load": [
85
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"location": {
"lat": 52.513365341037485,
"lng": 13.325000854641972
},
"time": {
"start": "2021-07-13T09:11:11Z",
"end": "2021-07-13T09:24:11Z"
}
}
],
"location": {
"lat": 52.513365341037485,
"lng": 13.325000854641972
},
"distance": 30106
},
{
"time": {
"arrival": "2021-07-13T09:39:28Z",
"departure": "2021-07-13T09:52:28Z"
},
"load": [
70
],
"activities": [
{
"jobId": "job_6",
"type": "delivery",
"location": {
"lat": 52.547429320898374,
"lng": 13.303190999428224
},
"time": {
"start": "2021-07-13T09:39:28Z",
"end": "2021-07-13T09:52:28Z"
}
}
],
"location": {
"lat": 52.547429320898374,
"lng": 13.303190999428224
},
"distance": 36717
},
{
"time": {
"arrival": "2021-07-13T10:02:13Z",
"departure": "2021-07-13T10:14:13Z"
},
"load": [
60
],
"activities": [
{
"jobId": "job_4",
"type": "delivery",
"location": {
"lat": 52.55783238016377,
"lng": 13.304436007504956
},
"time": {
"start": "2021-07-13T10:02:13Z",
"end": "2021-07-13T10:14:13Z"
}
}
],
"location": {
"lat": 52.55783238016377,
"lng": 13.304436007504956
},
"distance": 39363
},
{
"time": {
"arrival": "2021-07-13T10:28:13Z",
"departure": "2021-07-13T10:32:13Z"
},
"load": [
55
],
"activities": [
{
"jobId": "job_5",
"type": "delivery",
"location": {
"lat": 52.60592698633012,
"lng": 13.360660447014226
},
"time": {
"start": "2021-07-13T10:28:13Z",
"end": "2021-07-13T10:32:13Z"
}
}
],
"location": {
"lat": 52.60592698633012,
"lng": 13.360660447014226
},
"distance": 47447
},
{
"time": {
"arrival": "2021-07-13T11:03:59Z",
"departure": "2021-07-13T11:05:59Z"
},
"load": [
50
],
"activities": [
{
"jobId": "job_2",
"type": "delivery",
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"time": {
"start": "2021-07-13T11:03:59Z",
"end": "2021-07-13T11:05:59Z"
}
}
],
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"distance": 71323
}
],
"statistic": {
"cost": 252.23600000000002,
"distance": 71323,
"duration": 9959,
"times": {
"driving": 6959,
"serving": 3000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}このソリューションから、制約に関連して訪問したすべての場所での運転とサービスに費やした合計コスト、所要時間、距離、時間など、車両のツアーの統計を確認できます。車両の最後のアクティビティ時間と場所が、ツアーの最後の時間と場所であることに注意してください。
シフトの開始場所と終了場所がない問題
ここでは、シフトの開始場所と終了場所を定義せず、シフトの開始時刻と終了時刻のみを指定する例を示します。
Open 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"
},
"end": {
"time": "2021-07-13T14:20:00Z"
}
}
],
"capacity": [
100
],
"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
]
}
]
}
}
]
}
}ソリューション
このような問題のソリューションは次のようになります。
{
"statistic": {
"cost": 207.94,
"distance": 56495,
"duration": 8495,
"times": {
"driving": 5495,
"serving": 3000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "048d43e6e61c_2",
"typeId": "048d43e6e61c",
"stops": [
{
"time": {
"arrival": "2021-07-13T08:20:00Z",
"departure": "2021-07-13T08:22:00Z"
},
"load": [
30
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"time": {
"start": "2021-07-13T08:20:00Z",
"end": "2021-07-13T08:20:00Z"
}
},
{
"jobId": "job_2",
"type": "delivery",
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"time": {
"start": "2021-07-13T08:20:00Z",
"end": "2021-07-13T08:22:00Z"
}
}
],
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"distance": 0
},
{
"time": {
"arrival": "2021-07-13T08:53:11Z",
"departure": "2021-07-13T08:57:11Z"
},
"load": [
25
],
"activities": [
{
"jobId": "job_5",
"type": "delivery",
"location": {
"lat": 52.60592698633012,
"lng": 13.360660447014226
},
"time": {
"start": "2021-07-13T08:53:11Z",
"end": "2021-07-13T08:57:11Z"
}
}
],
"location": {
"lat": 52.60592698633012,
"lng": 13.360660447014226
},
"distance": 23646
},
{
"time": {
"arrival": "2021-07-13T09:10:40Z",
"departure": "2021-07-13T09:22:40Z"
},
"load": [
15
],
"activities": [
{
"jobId": "job_4",
"type": "delivery",
"location": {
"lat": 52.55783238016377,
"lng": 13.304436007504956
},
"time": {
"start": "2021-07-13T09:10:40Z",
"end": "2021-07-13T09:22:40Z"
}
}
],
"location": {
"lat": 52.55783238016377,
"lng": 13.304436007504956
},
"distance": 31705
},
{
"time": {
"arrival": "2021-07-13T09:31:36Z",
"departure": "2021-07-13T09:44:36Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_6",
"type": "delivery",
"location": {
"lat": 52.547429320898374,
"lng": 13.303190999428224
},
"time": {
"start": "2021-07-13T09:31:36Z",
"end": "2021-07-13T09:44:36Z"
}
}
],
"location": {
"lat": 52.547429320898374,
"lng": 13.303190999428224
},
"distance": 34750
},
{
"time": {
"arrival": "2021-07-13T10:01:37Z",
"departure": "2021-07-13T10:14:37Z"
},
"load": [
40
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"location": {
"lat": 52.513365341037485,
"lng": 13.325000854641972
},
"time": {
"start": "2021-07-13T10:01:37Z",
"end": "2021-07-13T10:14:37Z"
}
}
],
"location": {
"lat": 52.513365341037485,
"lng": 13.325000854641972
},
"distance": 41184
},
{
"time": {
"arrival": "2021-07-13T10:35:35Z",
"departure": "2021-07-13T10:41:35Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_3",
"type": "pickup",
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"time": {
"start": "2021-07-13T10:35:35Z",
"end": "2021-07-13T10:41:35Z"
}
},
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"time": {
"start": "2021-07-13T10:41:35Z",
"end": "2021-07-13T10:41:35Z"
}
}
],
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"distance": 56495
}
],
"statistic": {
"cost": 207.94,
"distance": 56495,
"duration": 8495,
"times": {
"driving": 5495,
"serving": 3000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}このソリューションでは、車両のツアーは配達地点の1つから始まり、最後の配達が行われる停車地で終了します。
次のステップ
詳細については、以下を参照してください。
- Submit a Vehicle Routing Problem to solve it synchronously (車両ルート検索問題を送信して同期的に解決する)
- Submit a Vehicle Routing Problem to solve it asynchronously (車両ルート検索問題を送信して非同期的に解決する)
26 日前の更新