多様な車タイプに合わせて旅程を最適化する
車両の運行管理がさまざまな積載量、コスト、車両タイプによって特徴付けられている場合、VRPの既知の制約条件となります。たとえば、運行管理は、シフト時間、積載量、距離/所要時間、コストが異なるCar、Truck、Pedestrian、Scooter、またはBicycleで構成されている場合があります。これは複数車種の運行管理を伴うVRPと呼ばれ、解決するには車両に関していくつかの特定の設定が必要です。いくつかの特定の制約を伴うこのような問題のソリューションについて考えてみましょう。
たとえば、乗用車とトラックの2種類の車両からなる運行管理があるとします。シフト時間、積載量、最大距離、コストが異なります。さらに、両方の車両が同じ場所でシフトを開始しますが、乗用車は別の集配センターでツアーを終了します。つまり、その最後の場所が開始場所と異なります。両方の車両でこれらの異なる制約を考慮して、car_1とtruck_1にすべての制約を個別に指定する必要があります。
ツアーに割り当てるジョブに関しては、アルゴリズムが車両に指定されたすべての制約を考慮し、それを考慮してルートを計算するため、特定の制約はありません。したがって、必要に応じてjobs ID、time、location、demand、priorityなどの定常データをジョブに指定します。この問題における重要な制約は、車両のtypeとcapacity、startとendの場所、shift time、ジョブのdemandです。乗用車の積載量が10、トラックの積載量が40であるため、需要がそれぞれ2、2、6、40となる4つのジョブを実行します。上記すべてに関して、複数車種の運行管理を伴うVRPの問題は次のようになります。
問題
{
"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
]
}
]
}
}
]
}
}ソリューション
この問題のソリューションは次のようになります。
{
"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"
}
],
"distance": 0
},
{
"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"
}
],
"distance": 5299
},
{
"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"
}
],
"distance": 9504
},
{
"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"
}
],
"distance": 16674
},
{
"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"
}
],
"distance": 25453
}
],
"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"
}
],
"distance": 0
},
{
"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"
}
],
"distance": 11280
},
{
"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"
}
],
"distance": 22692
}
],
"statistic": {
"cost": 84.572,
"distance": 22691,
"duration": 4365,
"times": {
"driving": 3285,
"serving": 1080,
"waiting": 0,
"break": 0
}
}
}
]
}このソリューションからは、総コスト、距離と所要時間、総運転時間、総サービス時間、総待機時間などのツアーの一般的な統計を確認できる他、各車両のツアーの詳細な統計も個別に確認できます。これは、複数車種の運行管理で一般的なさまざまな制約があったためです。
次のステップ
詳細については、以下を参照してください。
- Submit a Vehicle Routing Problem to solve it synchronously (車両ルート検索問題を送信して同期的に解決する)
- Submit a Vehicle Routing Problem to solve it asynchronously (車両ルート検索問題を送信して非同期的に解決する)
26 日前の更新