ツアー中の動的な再計画
ツアープランを利用すると、複数の車両のツアーだけでなく、 1 台の車両のツアーを計画する場合にも、多くのメリットを得ることができます。 ここで役立つオプションの 1 つはツアーの再計画です。これは、ドライバーがツアーの実行中に修正を加え、その修正の瞬間にツアー全体をリアルタイムで最適化できる機能ですこのオプションは、ツアー中にドライバーがお客様に遅れを告げたり、交通状況の変更、ツアー中のジョブのキャンセルなど、予期しない障害事象が発生した場合に非常に役立ちます
通常の再プラン手順は次のとおりです。 ツアーが計画され、最適化され ( 問題が発生 ) 、ドライバーがツアーの実行を開始しました。 最初のジョブを実行した後、ドライバーは次のジョブに進みます。その時点以降、ドライバーの現在の位置が残りのジョブのシフト開始時間になります。 そのため、ドライバーがツアーに変更を加えた場合、キャンセルされたジョブのある場所をスキップした場合、または別のジョブの優先度によって遅れて強制されたためにルートを変更した場合、ドライバーの現在の場所から新しい制約でツアーが再計算されます。
10 個の荷物を積載できる車両を所有しており、 6 つのジョブを異なる場所で実行する必要がある場合、簡単な状況をモデル化しましょう。 1 つは高い優先順位を持つジョブです ( 優先順位 = 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"
}
]
}
]
}