ルートを動的に再計画する
Tour Planningを利用すると、複数の車両の旅程だけでなく、1台の車両の旅程を計画する場合にも、多くのメリットを得ることができます。ここで役立つオプションの1つはツアーの再計画です。これは、ドライバーがツアーの実行中に修正を加え、その修正の瞬間にツアー全体をリアルタイムで最適化できる機能です。このオプションは、ドライバーの到着の遅れ、交通状況の変化、ツアー中のジョブのキャンセルなど、不測の障害が発生した場合に非常に役立ちます。
通常の再計画の手順は次のようになります。ツアーの計画と最適化 (問題の構築) が行われ、ドライバーがツアーの実行を開始します。最初のジョブを実行した後、ドライバーは次のジョブに進みます。その時点で、ドライバーの現在地が残りのジョブのシフト開始時刻となります。したがって、ドライバーがツアーに何らかの変更を加えた場合 (ジョブがキャンセルされたため場所をスキップした、遅れにより他のジョブが優先されたためルートを変更したなど)、ツアーはドライバーの現在地から新しい制約条件で再計算されます。
容量が10アイテムの車両が1台あり、異なる場所で6つのジョブを実行する必要があり、そのうち1つのジョブは優先度が高い (priority=1) という単純な状況をモデル化してみましょう。
{
"fleet": {
"types": [
{
"id": "Vehicle_1",
"profile": "car_1",
"costs": {
"fixed": 9.0,
"distance": 0.004,
"time": 0.005
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T18:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
10
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1",
"departureTime": "2021-08-27T08:00:00Z"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T09:03:00Z",
"2021-08-27T18:03:00Z"
]
],
"location": {
"lat": 52.59175589353722,
"lng": 13.350747750372257
},
"duration": 360
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T11:03:00Z",
"2021-08-27T20:03:00Z"
]
],
"location": {
"lat": 52.43363386232821,
"lng": 13.403232562191313
},
"duration": 540
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T10:03:00Z",
"2021-08-27T16:03:00Z"
]
],
"location": {
"lat": 52.473321658918245,
"lng": 13.28972099097991
},
"duration": 660
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T10:03:00Z",
"2021-08-27T16:03:00Z"
]
],
"location": {
"lat": 52.503321,
"lng": 13.299720
},
"duration": 660
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_5",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T10:03:00Z",
"2021-08-27T16:03:00Z"
]
],
"location": {
"lat": 52.403321658918245,
"lng": 13.19972099097991
},
"duration": 660
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_6",
"priority": 1,
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T14:03:00Z",
"2021-08-27T17:03:00Z"
]
],
"location": {
"lat": 52.54165532725351,
"lng": 13.365047170290309
},
"duration": 1140
}
],
"demand": [
1
]
}
]
}
}
]
}
}- 最適化が完了すると、ドライバーがツアーの実行を開始します。この問題の最初のソリューションは次のようになります。ジョブは、
job_2、job_5、job_3、job_4、job_1、job_6の順序で実行されます。job_6の優先度は1ですが、現時点ではドライバーがすべてのジョブを時間内に実行するのに十分な時間があるため、ツアーの最後に実行されます。
{
"statistic": {
"cost": 399.456,
"distance": 83354,
"duration": 11408,
"times": {
"driving": 7388,
"serving": 4020,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "Vehicle_1_1",
"typeId": "Vehicle_1",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T11:16:48Z"
},
"load": [
6
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.43363386232821,
"lng": 13.403232562191311
},
"time": {
"arrival": "2021-08-27T11:41:25Z",
"departure": "2021-08-27T11:50:25Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_2",
"type": "delivery"
}
],
"distance": 14847
},
{
"location": {
"lat": 52.40332165891824,
"lng": 13.19972099097991
},
"time": {
"arrival": "2021-08-27T12:20:46Z",
"departure": "2021-08-27T12:31:46Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_5",
"type": "delivery"
}
],
"distance": 28933
},
{
"location": {
"lat": 52.473321658918245,
"lng": 13.28972099097991
},
"time": {
"arrival": "2021-08-27T12:50:19Z",
"departure": "2021-08-27T13:01:19Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
],
"distance": 45017
},
{
"location": {
"lat": 52.503321,
"lng": 13.29972
},
"time": {
"arrival": "2021-08-27T13:10:48Z",
"departure": "2021-08-27T13:21:48Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
],
"distance": 62482
},
{
"location": {
"lat": 52.59175589353722,
"lng": 13.350747750372255
},
"time": {
"arrival": "2021-08-27T13:42:21Z",
"departure": "2021-08-27T13:48:21Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_1",
"type": "delivery"
}
],
"distance": 75917
},
{
"location": {
"lat": 52.54165532725351,
"lng": 13.365047170290309
},
"time": {
"arrival": "2021-08-27T14:03:00Z",
"departure": "2021-08-27T14:22:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_6",
"type": "delivery"
}
],
"distance": 83354
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T14:26:56Z",
"departure": "2021-08-27T14:26:56Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 85458
}
],
"statistic": {
"cost": 399.456,
"distance": 83354,
"duration": 11408,
"times": {
"driving": 7388,
"serving": 4020,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}- ドライバーが最初のジョブを実行したと仮定します。その後、ドライバーは交通状況の変化を考慮して、出発時刻を更新するためにツアーを再計算することにしました。これ以降、ツアーはこの変化を考慮し、現在のドライバーの位置を新しいシフトの開始地点と見なして最適化されます。次に、ドライバーは新しい制約条件を考慮して次のジョブを実行します。このため、すでに完了した
job_2は問題の制約条件から除外されます。新しい開始地点はjob_2の場所になり、開始時刻はjob_2からの出発時刻となります。問題は次のようになります。
{
"fleet": {
"types": [
{
"id": "Vehicle_1",
"profile": "car_1",
"costs": {
"fixed": 9.0,
"distance": 0.004,
"time": 0.005
},
"shifts": [
{
"start": {
"time": "2021-08-27T11:50:17Z",
"location": {
"lat": 52.43363386232821,
"lng": 13.403232562191311
}
},
"end": {
"time": "2021-08-27T18:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
10
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1",
"departureTime": "2021-08-27T11:50:17Z"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T09:03:00Z",
"2021-08-27T18:03:00Z"
]
],
"location": {
"lat": 52.59175589353722,
"lng": 13.350747750372257
},
"duration": 360
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T10:03:00Z",
"2021-08-27T16:03:00Z"
]
],
"location": {
"lat": 52.473321658918245,
"lng": 13.28972099097991
},
"duration": 660
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T10:03:00Z",
"2021-08-27T16:03:00Z"
]
],
"location": {
"lat": 52.503321,
"lng": 13.299720
},
"duration": 660
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_5",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T10:03:00Z",
"2021-08-27T16:03:00Z"
]
],
"location": {
"lat": 52.403321658918245,
"lng": 13.19972099097991
},
"duration": 660
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_6",
"priority": 1,
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T14:03:00Z",
"2021-08-27T17:03:00Z"
]
],
"location": {
"lat": 52.54165532725351,
"lng": 13.365047170290309
},
"duration": 1140
}
],
"demand": [
1
]
}
]
}
}
]
}
}ソリューションは、ジョブがjob_5、job_3、job_4、job_1、job_6の順序で実行されることを示しています。
{
"statistic": {
"cost": 329.975,
"distance": 68505,
"duration": 9391,
"times": {
"driving": 5911,
"serving": 3480,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "Vehicle_1_1",
"typeId": "Vehicle_1",
"stops": [
{
"location": {
"lat": 52.43363386232821,
"lng": 13.403232562191311
},
"time": {
"arrival": "2021-08-27T11:50:25Z",
"departure": "2021-08-27T11:50:25Z"
},
"load": [
5
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.40332165891824,
"lng": 13.19972099097991
},
"time": {
"arrival": "2021-08-27T12:20:46Z",
"departure": "2021-08-27T12:31:46Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_5",
"type": "delivery"
}
],
"distance": 14086
},
{
"location": {
"lat": 52.473321658918245,
"lng": 13.28972099097991
},
"time": {
"arrival": "2021-08-27T12:50:19Z",
"departure": "2021-08-27T13:01:19Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
],
"distance": 30170
},
{
"location": {
"lat": 52.503321,
"lng": 13.29972
},
"time": {
"arrival": "2021-08-27T13:10:48Z",
"departure": "2021-08-27T13:21:48Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
],
"distance": 47635
},
{
"location": {
"lat": 52.59175589353722,
"lng": 13.350747750372255
},
"time": {
"arrival": "2021-08-27T13:42:21Z",
"departure": "2021-08-27T13:48:21Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_1",
"type": "delivery"
}
],
"distance": 61070
},
{
"location": {
"lat": 52.54165532725351,
"lng": 13.365047170290309
},
"time": {
"arrival": "2021-08-27T14:03:00Z",
"departure": "2021-08-27T14:22:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_6",
"type": "delivery"
}
],
"distance": 68507
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T14:26:56Z",
"departure": "2021-08-27T14:26:56Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 70611
}
],
"statistic": {
"cost": 329.975,
"distance": 68505,
"duration": 9391,
"times": {
"driving": 5911,
"serving": 3480,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}job_5の実行時に、顧客が指定された場所にいなかったため、荷物は顧客に配達されず、ドライバーは近くの集荷場所に配達するために追加の時間を費やしました。これ以降、新しい制約 (場所が若干異なり、出発時刻が予定よりも遅くなる) を考慮して、ツアーが再計算されます。運行管理の制約は次のようになります。
{
"fleet": {
"types": [
{
"id": "Vehicle_1",
"profile": "car_1",
"costs": {
"fixed": 9.0,
"distance": 0.004,
"time": 0.005
},
"shifts": [
{
"start": {
"time": "2021-08-27T12:38:38Z",
"location": {
"lat": 52.40332165891824,
"lng": 13.19972099097991
}
},
"end": {
"time": "2021-08-27T18:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
10
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1",
"departureTime": "2021-08-27T12:38:38Z"
}
]
}
ソリューションからわかるように、残りのジョブはjob_3、job_4、job_1、job_6の順序で実行されます。
{
"statistic": {
"cost": 218.14999999999998,
"distance": 43650,
"duration": 6910,
"times": {
"driving": 4090,
"serving": 2820,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "Vehicle_1_1",
"typeId": "Vehicle_1",
"stops": [
{
"location": {
"lat": 52.40332165891824,
"lng": 13.19972099097991
},
"time": {
"arrival": "2021-08-27T12:40:46Z",
"departure": "2021-08-27T12:40:46Z"
},
"load": [
4
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.473321658918245,
"lng": 13.28972099097991
},
"time": {
"arrival": "2021-08-27T12:59:19Z",
"departure": "2021-08-27T13:10:19Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
],
"distance": 15600
},
{
"location": {
"lat": 52.503321,
"lng": 13.29972
},
"time": {
"arrival": "2021-08-27T13:19:48Z",
"departure": "2021-08-27T13:30:48Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
],
"distance": 20560
},
{
"location": {
"lat": 52.59175589353722,
"lng": 13.350747750372255
},
"time": {
"arrival": "2021-08-27T13:51:21Z",
"departure": "2021-08-27T13:57:21Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_1",
"type": "delivery"
}
],
"distance": 33995
},
{
"location": {
"lat": 52.54165532725351,
"lng": 13.365047170290309
},
"time": {
"arrival": "2021-08-27T14:12:00Z",
"departure": "2021-08-27T14:31:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_6",
"type": "delivery"
}
],
"distance": 41432
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T14:35:56Z",
"departure": "2021-08-27T14:35:56Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 43536
}
],
"statistic": {
"cost": 218.14999999999998,
"distance": 43650,
"duration": 6910,
"times": {
"driving": 4090,
"serving": 2820,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}- ドライバーが次のジョブを実行しているときに、交通状況が劇的に変化したか、車両に問題が発生して修理に時間がかかったと仮定します。その結果、
job_3の実行が大幅に遅れました。13:10に完了する予定でしたが、実際には16:15に完了しました。遅れはあったものの、job_3は無事に完了し、制約は再度更新されました。
{
"fleet": {
"types": [
{
"id": "Vehicle_1",
"profile": "car_1",
"costs": {
"fixed": 9.0,
"distance": 0.004,
"time": 0.005
},
"shifts": [
{
"start": {
"time": "2021-08-27T16:15:11Z",
"location": {
"lat": 52.473321658918245,
"lng": 13.28972099097991
}
},
"end": {
"time": "2021-08-27T18:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
10
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1",
"departureTime": "2021-08-27T16:15:11Z"
}
]
}ツアーが再計算されると、優先度1のjob_6が、優先度が設定されていないjob_4の前に実行されるように移動されました。これは、新しい時間制約により、ドライバーが両方を実行するのに十分な時間がなくなるためです。この更新はドライバーのアプリケーションにすぐに表示されるため、ドライバーはjob_1の実行に進み、次にjob_6の実行に進みます。job_4は優先度が設定されていないため、ツアーへの割り当てが解除されました。
{
"statistic": {
"cost": 134.247,
"distance": 26318,
"duration": 3995,
"times": {
"driving": 2495,
"serving": 1500,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "Vehicle_1_1",
"typeId": "Vehicle_1",
"stops": [
{
"location": {
"lat": 52.473321658918245,
"lng": 13.28972099097991
},
"time": {
"arrival": "2021-08-27T16:15:19Z",
"departure": "2021-08-27T16:15:19Z"
},
"load": [
2
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.59175589353722,
"lng": 13.350747750372255
},
"time": {
"arrival": "2021-08-27T16:37:19Z",
"departure": "2021-08-27T16:43:19Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_1",
"type": "delivery"
}
],
"distance": 16775
},
{
"location": {
"lat": 52.54165532725351,
"lng": 13.365047170290309
},
"time": {
"arrival": "2021-08-27T16:57:58Z",
"departure": "2021-08-27T17:16:58Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_6",
"type": "delivery"
}
],
"distance": 24212
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T17:21:54Z",
"departure": "2021-08-27T17:21:54Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 26316
}
],
"statistic": {
"cost": 134.247,
"distance": 26318,
"duration": 3995,
"times": {
"driving": 2495,
"serving": 1500,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
}
],
"unassigned": [
{
"jobId": "job_4",
"reasons": [
{
"code": "TIME_WINDOW_CONSTRAINT",
"description": "cannot be visited within time window"
}
]
}
]
}job_1の実行後、運行管理の制約は次のようになります。
{
"fleet": {
"types": [
{
"id": "Vehicle_1",
"profile": "car_1",
"costs": {
"fixed": 9.0,
"distance": 0.004,
"time": 0.005
},
"shifts": [
{
"start": {
"time": "2021-08-27T16:43:20Z",
"location": {
"lat": 52.59175589353722,
"lng": 13.350747750372255
}
},
"end": {
"time": "2021-08-27T18:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
10
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1",
"departureTime": "2021-08-27T16:43:20Z"
}
]
},実行が残っているジョブは、優先度の高いjob_6のみです。
{
"statistic": {
"cost": 58.743,
"distance": 9542,
"duration": 2315,
"times": {
"driving": 1175,
"serving": 1140,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "Vehicle_1_1",
"typeId": "Vehicle_1",
"stops": [
{
"location": {
"lat": 52.59175589353722,
"lng": 13.350747750372255
},
"time": {
"arrival": "2021-08-27T16:43:19Z",
"departure": "2021-08-27T16:43:19Z"
},
"load": [
1
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.54165532725351,
"lng": 13.365047170290309
},
"time": {
"arrival": "2021-08-27T16:57:58Z",
"departure": "2021-08-27T17:16:58Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_6",
"type": "delivery"
}
],
"distance": 7437
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T17:21:54Z",
"departure": "2021-08-27T17:21:54Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 14991
}
],
"statistic": {
"cost": 58.743,
"distance": 9542,
"duration": 2315,
"times": {
"driving": 1175,
"serving": 1140,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
}
],
"unassigned": [
{
"jobId": "job_4",
"reasons": [
{
"code": "TIME_WINDOW_CONSTRAINT",
"description": "cannot be visited within time window"
}
]
}
]
}次のステップ
詳細については、以下を参照してください。
- Submit a Vehicle Routing Problem to solve it synchronously (車両ルート検索問題を送信して同期的に解決する)
- Submit a Vehicle Routing Problem to solve it asynchronously (車両ルート検索問題を送信して非同期的に解決する)
26 日前の更新