従業員の送迎を計画する
このチュートリアルでは、Tour Planningを使用して従業員の送迎業務を最適化するための車両ルート検索問題について説明します。このシナリオでは、容量やコスト構造が異なる複数の車両を運行する会社を想定します。コストを最小限に抑え、時間の制約を遵守しながら、複数の場所から従業員をピックアップし、午前8時までに中央の目的地に送迎することが目的です。このアプローチは、通学の送迎にも適用でき、コストを抑えながらさまざまな場所から生徒をピックアップし、時間どおりに確実に学校に到着するようにします。
ヒント
自宅と学校の往復など、生徒が目的地への行きと帰りの両方で同じドライバーによって運行される必要がある別の送迎のユースケースについては、「フレキシブルグループ」を参照してください。
問題
以下のセクションでは、このケーススタディを目的とした運行管理の詳細とツアー計画の設定について詳しく説明します。
運行管理設定
2つの車両タイプ (car_aとvan_a) を使用できます。各車両タイプには、特定のコスト構造、容量、シフト時間があります。次の表は、運行管理の車両タイプの概要を示しており、コスト、容量、利用可能台数を簡単に比較できます。
| 車両タイプ | コスト (固定) | 容量 | 台数 | シフト開始 | シフト終了 |
|---|---|---|---|---|---|
car_a | $25.00 | 4 | 3 | 06:30:00 | 08:00:00 |
van_a | $20.00 | 7 | 2 | 06:30:00 | 08:00:00 |
バンの車両の方がスペースは広くなっていますが、送迎での使用頻度を高めるために、固定コストは低く設定されています。つまり、より多くの乗客や荷物を運ぶことで車両の運行コストが分散され、運行1回あたりのコストが安くなります。
以下のスニペットは、運行管理設定を問題のJSONのコンテキストに当てはめています。
{
"fleet": {
"types": [
{
"id": "car_a",
"profile": "car",
"costs": {
"fixed": 25,
"distance": 0.005,
"time": 0.005
},
"capacity": [
4
],
"amount": 3
},
{
"id": "van_a",
"profile": "car",
"costs": {
"fixed": 20,
"distance": 0.005,
"time": 0.005
},
"capacity": [
7
],
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car"
}
]
}
}ツアー計画
次のスニペットに示すように、この車両ルート検索問題のツアー計画は、各従業員をピックアップする12件のジョブタスクで構成されています。
{
"id": "Employee_1",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.56182,
"lng": 13.497167
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
}各ジョブの所要時間はdurationプロパティによって60秒間に設定されており、従業員が車両内で過ごすことができる最大時間はmaxTimeOnVehicleプロパティによって3600秒 (1時間) に指定されています。このmaxTimeOnVehicleの指定により、ツアーの所要時間と各車両の容量の両方にソフト制約が課されます。
-
ツアーの所要時間：
maxTimeOnVehicleパラメーターにより、各従業員が車両内で過ごす時間は指定された時間 (3600秒または1時間) を超えないようになります。この制約により、従業員を乗せ降ろしするのに車両が費やすことのできる合計時間が影響を受け、事実上、最初の従業員を乗せてから最後に降ろすまでのツアーの所要時間が制限されます。 -
容量：
maxTimeOnVehicleは主にツアーの所要時間を制限しますが、間接的に車両の容量にも影響します。車両は1時間以内にツアーを完了しなければならないため、従業員が広いエリアに分散していたり、ピックアップ地点間の移動時間が長かったりすると、最大限の従業員をピックアップできない可能性があります。
次のセクションには、完全な問題のJSONファイルが含まれています。
Click to expand/collapse the sample JSON
{
"fleet": {
"types": [
{
"id": "car_a",
"profile": "car",
"costs": {
"fixed": 25,
"distance": 0.005,
"time": 0.005
},
"shifts": [
{
"start": {
"time": "2023-05-28T06:30:00Z"
},
"end": {
"time": "2023-05-28T08:00:00Z",
"location": {
"lat": 52.508884,
"lng": 13.386738
}
}
}
],
"capacity": [
4
],
"amount": 3
},
{
"id": "van_a",
"profile": "car",
"costs": {
"fixed": 20,
"distance": 0.005,
"time": 0.005
},
"shifts": [
{
"start": {
"time": "2023-05-28T06:30:00Z"
},
"end": {
"time": "2023-05-28T08:00:00Z",
"location": {
"lat": 52.508884,
"lng": 13.386738
}
}
}
],
"capacity": [
7
],
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car"
}
]
},
"plan": {
"jobs": [
{
"id": "Employee_1",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.56182,
"lng": 13.497167
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_2",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.534553,
"lng": 13.519429
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_3",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.482275,
"lng": 13.502456
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_4",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.473537,
"lng": 13.505414
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_5",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.463341,
"lng": 13.49061
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_6",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.434003,
"lng": 13.466142
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_7",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.447476,
"lng": 13.433062
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_8",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.458414,
"lng": 13.392079
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_9",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.446407,
"lng": 13.36047
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_10",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.440807,
"lng": 13.351399
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_11",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.441913,
"lng": 13.339028
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_12",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.458232,
"lng": 13.338698
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
}
]
}
}ソリューション
次の図は、ソリューションを図示したものです。
次の表は、ジョブに割り当てられた各車両のツアー統計を分析したものです。
| 車両ID | 車両タイプ | 総コスト | 総走行距離 | 総所要時間 | 運転時間 (秒) | 運転時間 (分) | サービス時間 (秒) | 停車地の数 | ピックアップした従業員数 |
|---|---|---|---|---|---|---|---|---|---|
| van_a_2 | van_a | $159.19 | 24,889m | 2,949秒 | 2,529秒 | 42.15分 | 420秒 | 7 | Employee_6、Employee_7、Employee_8、Employee_9、Employee_10、Employee_11、Employee_12 |
| van_a_1 | van_a | $169.98 | 26,867m | 3,129秒 | 2,829秒 | 47.15分 | 300秒 | 5 | Employee_1、Employee_2、Employee_3、Employee_4、Employee_5 |
ソリューションが示すように、最適化アルゴリズムは、以下の理由によりvan_aタイプの車両のみを選択しました。
van_aは固定コストが低いため、car_aと比較してコスト効率の高いオプションとして選択されました。car_aよりも容量が大きいため、van_aは2台の車両のみを使用してすべてのジョブに対応し、時間制約を満たすことができました。2台のバンのみを使用することで、運行管理する車両数の削減における最適化アルゴリズムの有効性が強調されます。さらに、道路上の車両が減ることで、排気量や環境負荷の低減につながる可能性があります。- 各車両は、車両制約の最大時間である
3600秒 (1時間) を満たし、すべての従業員が目的地に時間どおりに到着できるようになりました。指定された時間制限内に、時間どおりに従業員を乗せ降ろしすることで、ソリューションは従業員の満足度と時間厳守に貢献します。
次のセクションには、完全なソリューションのJSONファイルが含まれています。
Click to expand/collapse the sample JSON
{
"statistic": {
"cost": 329.17,
"distance": 51756,
"duration": 6078,
"times": {
"driving": 5358,
"serving": 720,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "van_a_2",
"typeId": "van_a",
"stops": [
{
"time": {
"arrival": "2023-05-28T06:30:00Z",
"departure": "2023-05-28T06:31:00Z"
},
"load": [
1
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 52.434003,
"lng": 13.466142
},
"time": {
"start": "2023-05-28T06:30:00Z",
"end": "2023-05-28T06:30:00Z"
}
},
{
"jobId": "Employee_6",
"type": "pickup",
"location": {
"lat": 52.434003,
"lng": 13.466142
},
"time": {
"start": "2023-05-28T06:30:00Z",
"end": "2023-05-28T06:31:00Z"
}
}
],
"location": {
"lat": 52.434003,
"lng": 13.466142
},
"distance": 0
},
{
"time": {
"arrival": "2023-05-28T06:36:50Z",
"departure": "2023-05-28T06:37:50Z"
},
"load": [
2
],
"activities": [
{
"jobId": "Employee_7",
"type": "pickup",
"location": {
"lat": 52.447476,
"lng": 13.433062
},
"time": {
"start": "2023-05-28T06:36:50Z",
"end": "2023-05-28T06:37:50Z"
}
}
],
"location": {
"lat": 52.447476,
"lng": 13.433062
},
"distance": 3529
},
{
"time": {
"arrival": "2023-05-28T06:44:17Z",
"departure": "2023-05-28T06:45:17Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Employee_8",
"type": "pickup",
"location": {
"lat": 52.458414,
"lng": 13.392079
},
"time": {
"start": "2023-05-28T06:44:17Z",
"end": "2023-05-28T06:45:17Z"
}
}
],
"location": {
"lat": 52.458414,
"lng": 13.392079
},
"distance": 7553
},
{
"time": {
"arrival": "2023-05-28T06:50:32Z",
"departure": "2023-05-28T06:51:32Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Employee_9",
"type": "pickup",
"location": {
"lat": 52.446407,
"lng": 13.36047
},
"time": {
"start": "2023-05-28T06:50:32Z",
"end": "2023-05-28T06:51:32Z"
}
}
],
"location": {
"lat": 52.446407,
"lng": 13.36047
},
"distance": 10367
},
{
"time": {
"arrival": "2023-05-28T06:55:02Z",
"departure": "2023-05-28T06:56:02Z"
},
"load": [
5
],
"activities": [
{
"jobId": "Employee_10",
"type": "pickup",
"location": {
"lat": 52.440807,
"lng": 13.351399
},
"time": {
"start": "2023-05-28T06:55:02Z",
"end": "2023-05-28T06:56:02Z"
}
}
],
"location": {
"lat": 52.440807,
"lng": 13.351399
},
"distance": 11951
},
{
"time": {
"arrival": "2023-05-28T06:59:23Z",
"departure": "2023-05-28T07:00:23Z"
},
"load": [
6
],
"activities": [
{
"jobId": "Employee_11",
"type": "pickup",
"location": {
"lat": 52.441913,
"lng": 13.339028
},
"time": {
"start": "2023-05-28T06:59:23Z",
"end": "2023-05-28T07:00:23Z"
}
}
],
"location": {
"lat": 52.441913,
"lng": 13.339028
},
"distance": 13550
},
{
"time": {
"arrival": "2023-05-28T07:04:36Z",
"departure": "2023-05-28T07:05:36Z"
},
"load": [
7
],
"activities": [
{
"jobId": "Employee_12",
"type": "pickup",
"location": {
"lat": 52.458232,
"lng": 13.338698
},
"time": {
"start": "2023-05-28T07:04:36Z",
"end": "2023-05-28T07:05:36Z"
}
}
],
"location": {
"lat": 52.458232,
"lng": 13.338698
},
"distance": 15677
},
{
"time": {
"arrival": "2023-05-28T07:19:09Z",
"departure": "2023-05-28T07:19:09Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 52.508884,
"lng": 13.386738
},
"time": {
"start": "2023-05-28T07:19:09Z",
"end": "2023-05-28T07:19:09Z"
}
}
],
"location": {
"lat": 52.508884,
"lng": 13.386738
},
"distance": 24889
}
],
"statistic": {
"cost": 159.19,
"distance": 24889,
"duration": 2949,
"times": {
"driving": 2529,
"serving": 420,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
},
{
"vehicleId": "van_a_1",
"typeId": "van_a",
"stops": [
{
"time": {
"arrival": "2023-05-28T06:30:00Z",
"departure": "2023-05-28T06:31:00Z"
},
"load": [
1
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 52.56182,
"lng": 13.497167
},
"time": {
"start": "2023-05-28T06:30:00Z",
"end": "2023-05-28T06:30:00Z"
}
},
{
"jobId": "Employee_1",
"type": "pickup",
"location": {
"lat": 52.56182,
"lng": 13.497167
},
"time": {
"start": "2023-05-28T06:30:00Z",
"end": "2023-05-28T06:31:00Z"
}
}
],
"location": {
"lat": 52.56182,
"lng": 13.497167
},
"distance": 0
},
{
"time": {
"arrival": "2023-05-28T06:37:37Z",
"departure": "2023-05-28T06:38:37Z"
},
"load": [
2
],
"activities": [
{
"jobId": "Employee_2",
"type": "pickup",
"location": {
"lat": 52.534553,
"lng": 13.519429
},
"time": {
"start": "2023-05-28T06:37:37Z",
"end": "2023-05-28T06:38:37Z"
}
}
],
"location": {
"lat": 52.534553,
"lng": 13.519429
},
"distance": 3749
},
{
"time": {
"arrival": "2023-05-28T06:52:39Z",
"departure": "2023-05-28T06:53:39Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Employee_3",
"type": "pickup",
"location": {
"lat": 52.482275,
"lng": 13.502456
},
"time": {
"start": "2023-05-28T06:52:39Z",
"end": "2023-05-28T06:53:39Z"
}
}
],
"location": {
"lat": 52.482275,
"lng": 13.502456
},
"distance": 12529
},
{
"time": {
"arrival": "2023-05-28T06:55:29Z",
"departure": "2023-05-28T06:56:29Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Employee_4",
"type": "pickup",
"location": {
"lat": 52.473537,
"lng": 13.505414
},
"time": {
"start": "2023-05-28T06:55:29Z",
"end": "2023-05-28T06:56:29Z"
}
}
],
"location": {
"lat": 52.473537,
"lng": 13.505414
},
"distance": 13815
},
{
"time": {
"arrival": "2023-05-28T07:02:29Z",
"departure": "2023-05-28T07:03:29Z"
},
"load": [
5
],
"activities": [
{
"jobId": "Employee_5",
"type": "pickup",
"location": {
"lat": 52.463341,
"lng": 13.49061
},
"time": {
"start": "2023-05-28T07:02:29Z",
"end": "2023-05-28T07:03:29Z"
}
}
],
"location": {
"lat": 52.463341,
"lng": 13.49061
},
"distance": 16756
},
{
"time": {
"arrival": "2023-05-28T07:22:09Z",
"departure": "2023-05-28T07:22:09Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 52.508884,
"lng": 13.386738
},
"time": {
"start": "2023-05-28T07:22:09Z",
"end": "2023-05-28T07:22:09Z"
}
}
],
"location": {
"lat": 52.508884,
"lng": 13.386738
},
"distance": 26867
}
],
"statistic": {
"cost": 169.98000000000002,
"distance": 26867,
"duration": 3129,
"times": {
"driving": 2829,
"serving": 300,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}次のステップ
26 日前の更新