複数車種の運行を伴う VRP
車両の運行管理 がさまざまな積載量、コスト、車両タイプによって特徴付けられている場合、VRP の既知の制約条件となります。 たとえば、運行管理 は、異なるシフト時間、能力、距離/時間、コストの、トラック、徒歩、スクーター、自転車で構成されます。これは複数車種の運行を伴うVRP と呼ばれ、解決するには車両に関していくつかの特定の設定が必要です。いくつか特定の制約を伴うこのような問題の解決策について考えてみましょう。
たとえば、乗用車とトラックの 2 種類の車両から成る運行管理 があるとします。 シフト時間、積載量、最大距離、コストが異なります。 さらに、両方の車両が同じ場所でシフトを開始しますが、車両は別のデポでツアーを終了します。つまり、その最終位置が開始位置とは異なります。 両方の車両でこれらの異なる制約を考慮して、 CAR_1 と TRACK_1 にすべての制約を個別に指定する必要があります。
ツアーに割り当てるジョブについては、アルゴリズムが車両に指定されたすべての制約を考慮し、それらに応じたルートを計算するため、具体的な制約はありません。そのため、ジョブには、ジョブ ID 、時間、場所、需要、優先度 ( 必要な場合 ) などのルーチンデータを指定します この問題の主な制約は、車両のタイプと積載量、開始位置と終了位置、シフト時間、およびジョブの需要です。車両の積載量は 10、トラックの積載量は 40 で、需要がそれぞれ 2、2、6、40 の 4 つの作業を行います。 上記のすべてについて、複数種の車両を伴う VRP の問題は次のようになります。
Problems
{
"fleet": {
"types": [
{
"id": "6d1dc02e19d6",
"profile": "car_1",
"costs": {
"fixed": 8.0,
"distance": 0.002,
"time": 0.009
},
"shifts": [
{
"start": {
"time": "2021-08-27T06:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T13:03:00Z",
"location": {
"lat": 52.529953,
"lng": 13.314877
}
}
}
],
"capacity": [
10
],
"amount": 1
},
{
"id": "b47bb0d26e4c",
"profile": "truck_1",
"costs": {
"fixed": 13.0,
"distance": 0.002,
"time": 0.006
},
"shifts": [
{
"start": {
"time": "2021-08-27T14:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T19:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
40
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
},
{
"type": "truck",
"name": "truck_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T09:03:00Z",
"2021-08-27T15:03:00Z"
]
],
"location": {
"lat": 52.46274034612159,
"lng": 13.381744271815766
},
"duration": 780
}
],
"demand": [
2
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T09:03:00Z",
"2021-08-27T15:03:00Z"
]
],
"location": {
"lat": 52.495709703500346,
"lng": 13.383026814092966
},
"duration": 840
}
],
"demand": [
2
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T10:03:00Z",
"2021-08-27T18:03:00Z"
]
],
"location": {
"lat": 52.489639267111066,
"lng": 13.305679494421426
},
"duration": 540
}
],
"demand": [
6
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T10:03:00Z",
"2021-08-27T19:03:00Z"
]
],
"location": {
"lat": 52.60353049998964,
"lng": 13.42085512158312
},
"duration": 1080
}
],
"demand": [
40
]
}
]
}
}
]
}
}
Solution
この問題の解決方法は次のとおりです。
{
"statistic": {
"cost": 184.654,
"distance": 48104,
"duration": 8949,
"times": {
"driving": 5709,
"serving": 3240,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "6d1dc02e19d6_1",
"typeId": "6d1dc02e19d6",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T06:03:00Z",
"departure": "2021-08-27T09:06:45Z"
},
"load": [
10
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.495709703500346,
"lng": 13.383026814092966
},
"time": {
"arrival": "2021-08-27T09:17:02Z",
"departure": "2021-08-27T09:31:02Z"
},
"load": [
8
],
"activities": [
{
"jobId": "job_2",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.46274034612159,
"lng": 13.381744271815766
},
"time": {
"arrival": "2021-08-27T09:39:50Z",
"departure": "2021-08-27T09:52:50Z"
},
"load": [
6
],
"activities": [
{
"jobId": "job_1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.489639267111066,
"lng": 13.305679494421426
},
"time": {
"arrival": "2021-08-27T10:03:00Z",
"departure": "2021-08-27T10:12:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.529953,
"lng": 13.314877
},
"time": {
"arrival": "2021-08-27T10:23:09Z",
"departure": "2021-08-27T10:23:09Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 100.082,
"distance": 25413,
"duration": 4584,
"times": {
"driving": 2424,
"serving": 2160,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "b47bb0d26e4c_1",
"typeId": "b47bb0d26e4c",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T14:03:00Z",
"departure": "2021-08-27T14:03:00Z"
},
"load": [
40
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.60353049998964,
"lng": 13.42085512158312
},
"time": {
"arrival": "2021-08-27T14:32:08Z",
"departure": "2021-08-27T14:50:08Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T15:15:45Z",
"departure": "2021-08-27T15:15:45Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 84.572,
"distance": 22691,
"duration": 4365,
"times": {
"driving": 3285,
"serving": 1080,
"waiting": 0,
"break": 0
}
}
}
]
}
このソリューションでは、総コスト、走行距離、所要時間、総運転時間、サービス時間、待ち時間などのツアーの共通の統計情報の他、複数種の車両を伴う場合には一般的なことですが、各車両には異なる制約があり、車両毎の詳細な統計情報を個別に確認できます。