ジョブタスクの順序
ジョブタスクの順序フィーチャーを使用すると、ツアー内でジョブを処理する順序を直接設定できます。 ジョブのタスク順序を使用する場合 、問題のタスクに目的の値 order
を割り当てることができます。この方法で、ソリューションでのタスクの処理順序に影響を与えることができます。
ジョブタスクの順序は、 2 つの方法で設定できます order
。各ジョブタスクに特定の一意の値を設定すると ( 「 ツアー計画 API リファレンス 」の「ジョブタスク」を参照) 、制約に基づいてその特定の順序でツアーが作成されることがあります。 または、 order
他のタスクよりも先に処理するジョブタスクのグループに特定の値を設定します。 このよう にすると、order
値が大きいジョブは、order
値が小さいすべてのジョブの後に処理されます。同時に、order
値が同じジョブグループは別々に最適化されます。 このようにジョブタスクをグループ化することで、たとえば、すべての配達を最初に配達してから集荷する必要がある場合に使用できます。そのため、再度荷物を積み込む前に車両が空になります。
追加の制約により、見つかったソリューションの総コストが高い場合でも、order
に設定した値が考慮されるので、タスクが指定した順序で処理されることを確認できます。
ジョブ タスク順序の値は、次のようにジョブ タスクに order
の値を追加することによって、問題のplan
の部分に設定されます。
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.53315878386378,
"lng": 13.352999270430127
},
"duration": 500
}
],
"demand": [
3
],
"order":1
}
]
}
},
ジョブのタスク順序を使用せずに、同じ問題と比較してジョブのタスク順序オプションの問題がどのように解決されるかを実際に確認するには、次の例を参照してください。
ジョブタスクの順序を指定したProblem
ここに10 のジョブを処理可能な車があります。 一部のジョブを他のジョブよりも先に処理するようにするため、 order
値を次のように設定します。 "order":1
-"job_1"
から"job_5"
までの 5 つのジョブ 、および"order":2
-"job_6"
から"job_10"
-までの残りのジョブ。同じ方法で、特定の順序でジョブを処理する場合は、各ジョブに特別な順序を設定できます。
{
"fleet": {
"types": [
{
"id": "Vehicle1",
"profile": "car_4c40316dc25b",
"costs": {
"fixed": 8.0,
"distance": 0.001,
"time": 0.007
},
"shifts": [
{
"start": {
"time": "2022-06-22T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2022-06-22T16:03:00Z",
"location": {
"lat": 52.53560051953246,
"lng": 13.351359003414167
}
}
}
],
"capacity": [
40
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_4c40316dc25b"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.58136440229602,
"lng": 13.423236627987324
},
"duration": 500
}
],
"demand": [
3
],
"order":1
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.53315878386378,
"lng": 13.352999270430127
},
"duration": 500
}
],
"demand": [
3
],
"order":1
}
]
}
},
{
"id": "job_3",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.44927857909315,
"lng": 13.365028443606981
},
"duration": 500
}
],
"demand": [
3
],
"order":1
}
]
}
},
{
"id": "job_4",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.48998701990294,
"lng": 13.286076137075746
},
"duration": 500
}
],
"demand": [
3
],
"order":1
}
]
}
},
{
"id": "job_5",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.469144533572845,
"lng": 13.497412369472363
},
"duration": 500
}
],
"demand": [
3
],
"order":1
}
]
}
},
{
"id": "job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.57604629377083,
"lng": 13.488619313215823
},
"duration": 500
}
],
"demand": [
3
],
"order":2
}
]
}
},
{
"id": "job_7",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.63186486317331,
"lng": 13.29405790954721
},
"duration": 500
}
],
"demand": [
3
],
"order":2
}
]
}
},
{
"id": "job_8",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.61900693527653,
"lng": 13.32574157985448
},
"duration": 500
}
],
"demand": [
3
],
"order":2
}
]
}
},
{
"id": "job_9",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.50926602381726,
"lng": 13.481018586655173
},
"duration": 500
}
],
"demand": [
3
],
"order":2
}
]
}
},
{
"id": "job_10",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.55137844164478,
"lng": 13.509316000155943
},
"duration": 500
}
],
"demand": [
3
],
"order":2
}
]
}
}
]
}
}
Solution
このソリューションでは 、値"order"
が 1 のすべてのジョブが 、値"order"
が 2 のすべてのジョブの前に処理されることを確認できます。 さらに 、 1 と 2 の値"order"
を持つすべてのジョブを処理する順序は、個別に最適化されており、 値"order":1
を持つジョブの処理順序は、 job_1
、job_2
、job_4
、job_3
、job_5
であり、"order":2
は、job_9
、job_10
、job_6
、job_8
、job_7
であることがわかります。
{
"statistic": {
"cost": 234.29200000000003,
"distance": 107894,
"duration": 16914,
"times": {
"driving": 11914,
"serving": 5000,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "Vehicle1_1",
"typeId": "Vehicle1",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2022-06-22T08:03:00Z",
"departure": "2022-06-22T08:03:00Z"
},
"load": [
15
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.58136440229602,
"lng": 13.423236627987324
},
"time": {
"arrival": "2022-06-22T08:23:36Z",
"departure": "2022-06-22T08:31:56Z"
},
"load": [
18
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
],
"distance": 8837
},
{
"location": {
"lat": 52.53315878386378,
"lng": 13.352999270430129
},
"time": {
"arrival": "2022-06-22T08:53:17Z",
"departure": "2022-06-22T09:01:37Z"
},
"load": [
21
],
"activities": [
{
"jobId": "job_2",
"type": "pickup"
}
],
"distance": 17327
},
{
"location": {
"lat": 52.48998701990294,
"lng": 13.286076137075746
},
"time": {
"arrival": "2022-06-22T09:18:07Z",
"departure": "2022-06-22T09:26:27Z"
},
"load": [
24
],
"activities": [
{
"jobId": "job_4",
"type": "pickup"
}
],
"distance": 28464
},
{
"location": {
"lat": 52.44927857909315,
"lng": 13.36502844360698
},
"time": {
"arrival": "2022-06-22T09:40:12Z",
"departure": "2022-06-22T09:48:32Z"
},
"load": [
27
],
"activities": [
{
"jobId": "job_3",
"type": "pickup"
}
],
"distance": 37975
},
{
"location": {
"lat": 52.469144533572845,
"lng": 13.497412369472364
},
"time": {
"arrival": "2022-06-22T10:09:24Z",
"departure": "2022-06-22T10:17:44Z"
},
"load": [
30
],
"activities": [
{
"jobId": "job_5",
"type": "pickup"
}
],
"distance": 50897
},
{
"location": {
"lat": 52.50926602381726,
"lng": 13.481018586655171
},
"time": {
"arrival": "2022-06-22T10:31:47Z",
"departure": "2022-06-22T10:40:07Z"
},
"load": [
27
],
"activities": [
{
"jobId": "job_9",
"type": "delivery"
}
],
"distance": 57922
},
{
"location": {
"lat": 52.55137844164478,
"lng": 13.509316000155945
},
"time": {
"arrival": "2022-06-22T10:55:14Z",
"departure": "2022-06-22T11:03:34Z"
},
"load": [
24
],
"activities": [
{
"jobId": "job_10",
"type": "delivery"
}
],
"distance": 65720
},
{
"location": {
"lat": 52.57604629377083,
"lng": 13.488619313215825
},
"time": {
"arrival": "2022-06-22T11:13:07Z",
"departure": "2022-06-22T11:21:27Z"
},
"load": [
21
],
"activities": [
{
"jobId": "job_6",
"type": "delivery"
}
],
"distance": 70841
},
{
"location": {
"lat": 52.61900693527653,
"lng": 13.32574157985448
},
"time": {
"arrival": "2022-06-22T11:53:21Z",
"departure": "2022-06-22T12:01:41Z"
},
"load": [
18
],
"activities": [
{
"jobId": "job_8",
"type": "delivery"
}
],
"distance": 86890
},
{
"location": {
"lat": 52.63186486317331,
"lng": 13.29405790954721
},
"time": {
"arrival": "2022-06-22T12:09:59Z",
"departure": "2022-06-22T12:18:19Z"
},
"load": [
15
],
"activities": [
{
"jobId": "job_7",
"type": "delivery"
}
],
"distance": 90930
},
{
"location": {
"lat": 52.53560051953246,
"lng": 13.351359003414167
},
"time": {
"arrival": "2022-06-22T12:44:54Z",
"departure": "2022-06-22T12:44:54Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 107479
}
],
"statistic": {
"cost": 234.29200000000003,
"distance": 107894,
"duration": 16914,
"times": {
"driving": 11914,
"serving": 5000,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}
ジョブタスクの順序が未指定のProblems
以下の問題は、上記と同じですが、ジョブに [ ジョブタスクの順序 ] オプションが追加されていません。
{
"fleet": {
"types": [
{
"id": "Vehicle1",
"profile": "car_4c40316dc25b",
"costs": {
"fixed": 8.0,
"distance": 0.001,
"time": 0.007
},
"shifts": [
{
"start": {
"time": "2022-06-22T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2022-06-22T16:03:00Z",
"location": {
"lat": 52.53560051953246,
"lng": 13.351359003414167
}
}
}
],
"capacity": [
40
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_4c40316dc25b"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.58136440229602,
"lng": 13.423236627987324
},
"duration": 500
}
],
"demand": [
3
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.53315878386378,
"lng": 13.352999270430127
},
"duration": 500
}
],
"demand": [
3
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.44927857909315,
"lng": 13.365028443606981
},
"duration": 500
}
],
"demand": [
3
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.48998701990294,
"lng": 13.286076137075746
},
"duration": 500
}
],
"demand": [
3
]
}
]
}
},
{
"id": "job_5",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.469144533572845,
"lng": 13.497412369472363
},
"duration": 500
}
],
"demand": [
3
]
}
]
}
},
{
"id": "job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.57604629377083,
"lng": 13.488619313215823
},
"duration": 500
}
],
"demand": [
3
]
}
]
}
},
{
"id": "job_7",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.63186486317331,
"lng": 13.29405790954721
},
"duration": 500
}
],
"demand": [
3
]
}
]
}
},
{
"id": "job_8",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.61900693527653,
"lng": 13.32574157985448
},
"duration": 500
}
],
"demand": [
3
]
}
]
}
},
{
"id": "job_9",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.50926602381726,
"lng": 13.481018586655173
},
"duration": 500
}
],
"demand": [
3
]
}
]
}
},
{
"id": "job_10",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.55137844164478,
"lng": 13.509316000155943
},
"duration": 500
}
],
"demand": [
3
]
}
]
}
}
]
}
}
Solution
[ ジョブタスクの順序 ] オプションを使用しない場合の解決策からわかるように、ジョブタスクの順序の制約を考慮せずにツアーが最適化されるため、最終的なツアーは異なります。 このようにして、同じツアーのジョブを処理する最終的な順序は次のようになります。job_8
、 job_7
、 job_1
、job_6
、job_10
、 job_9
、 job_5
、 job_3
、 job_4
、job_2
。 その結果、走行距離、所要時間の合計が減り、ツアーの総コストも削減されます。
{
"statistic": {
"cost": 205.85899999999998,
"distance": 91928,
"duration": 15133,
"times": {
"driving": 10133,
"serving": 5000,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "Vehicle1_1",
"typeId": "Vehicle1",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2022-06-22T08:03:00Z",
"departure": "2022-06-22T08:03:00Z"
},
"load": [
15
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.61900693527653,
"lng": 13.32574157985448
},
"time": {
"arrival": "2022-06-22T08:29:28Z",
"departure": "2022-06-22T08:37:48Z"
},
"load": [
12
],
"activities": [
{
"jobId": "job_8",
"type": "delivery"
}
],
"distance": 10059
},
{
"location": {
"lat": 52.63186486317331,
"lng": 13.29405790954721
},
"time": {
"arrival": "2022-06-22T08:46:06Z",
"departure": "2022-06-22T08:54:26Z"
},
"load": [
9
],
"activities": [
{
"jobId": "job_7",
"type": "delivery"
}
],
"distance": 19570
},
{
"location": {
"lat": 52.58136440229602,
"lng": 13.423236627987324
},
"time": {
"arrival": "2022-06-22T09:22:38Z",
"departure": "2022-06-22T09:30:58Z"
},
"load": [
12
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
],
"distance": 32492
},
{
"location": {
"lat": 52.57604629377083,
"lng": 13.488619313215825
},
"time": {
"arrival": "2022-06-22T09:44:52Z",
"departure": "2022-06-22T09:53:12Z"
},
"load": [
9
],
"activities": [
{
"jobId": "job_6",
"type": "delivery"
}
],
"distance": 39517
},
{
"location": {
"lat": 52.55137844164478,
"lng": 13.509316000155945
},
"time": {
"arrival": "2022-06-22T10:03:29Z",
"departure": "2022-06-22T10:11:49Z"
},
"load": [
6
],
"activities": [
{
"jobId": "job_10",
"type": "delivery"
}
],
"distance": 47315
},
{
"location": {
"lat": 52.50926602381726,
"lng": 13.481018586655171
},
"time": {
"arrival": "2022-06-22T10:26:27Z",
"departure": "2022-06-22T10:34:47Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_9",
"type": "delivery"
}
],
"distance": 52436
},
{
"location": {
"lat": 52.469144533572845,
"lng": 13.497412369472364
},
"time": {
"arrival": "2022-06-22T10:47:18Z",
"departure": "2022-06-22T10:55:38Z"
},
"load": [
6
],
"activities": [
{
"jobId": "job_5",
"type": "pickup"
}
],
"distance": 59058
},
{
"location": {
"lat": 52.44927857909315,
"lng": 13.36502844360698
},
"time": {
"arrival": "2022-06-22T11:15:37Z",
"departure": "2022-06-22T11:23:57Z"
},
"load": [
9
],
"activities": [
{
"jobId": "job_3",
"type": "pickup"
}
],
"distance": 69971
},
{
"location": {
"lat": 52.48998701990294,
"lng": 13.286076137075746
},
"time": {
"arrival": "2022-06-22T11:40:07Z",
"departure": "2022-06-22T11:48:27Z"
},
"load": [
12
],
"activities": [
{
"jobId": "job_4",
"type": "pickup"
}
],
"distance": 74011
},
{
"location": {
"lat": 52.53315878386378,
"lng": 13.352999270430129
},
"time": {
"arrival": "2022-06-22T12:04:48Z",
"departure": "2022-06-22T12:13:08Z"
},
"load": [
15
],
"activities": [
{
"jobId": "job_2",
"type": "pickup"
}
],
"distance": 89611
},
{
"location": {
"lat": 52.53560051953246,
"lng": 13.351359003414167
},
"time": {
"arrival": "2022-06-22T12:15:13Z",
"departure": "2022-06-22T12:15:13Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 90358
}
],
"statistic": {
"cost": 205.85899999999998,
"distance": 91928,
"duration": 15133,
"times": {
"driving": 10133,
"serving": 5000,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}
複数の車両の課題
ジョブタスクの順序が異なるジョブを実行するための複数の車両がある例を考えてみましょう。 以下の問題では、 10 件のジョブを実行する車両が 2 台、そのうち 6個のジョブが
order
1 件、 4 個のジョブがorder
2 件あります。 車両は、異なるシフト時間および 1 つのデポから作動します。
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": "car_2",
"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": "car",
"name": "car_2"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.58136440229602,
"lng": 13.423236627987324
},
"duration": 500
}
],
"demand": [
3
],
"order":1
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.53315878386378,
"lng": 13.352999270430127
},
"duration": 500
}
],
"demand": [
3
],
"order":1
}
]
}
},
{
"id": "job_3",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.44927857909315,
"lng": 13.365028443606981
},
"duration": 500
}
],
"demand": [
3
],
"order":1
}
]
}
},
{
"id": "job_4",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.48998701990294,
"lng": 13.286076137075746
},
"duration": 500
}
],
"demand": [
3
],
"order":1
}
]
}
},
{
"id": "job_5",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.469144533572845,
"lng": 13.497412369472363
},
"duration": 500
}
],
"demand": [
3
],
"order":1
}
]
}
},
{
"id": "job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.57604629377083,
"lng": 13.488619313215823
},
"duration": 500
}
],
"demand": [
3
],
"order":1
}
]
}
},
{
"id": "job_7",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.73186486317331,
"lng": 13.59405790954721
},
"duration": 500
}
],
"demand": [
3
],
"order":2
}
]
}
},
{
"id": "job_8",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.91900693527653,
"lng": 13.92574157985448
},
"duration": 500
}
],
"demand": [
3
],
"order":2
}
]
}
},
{
"id": "job_9",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.90926602381726,
"lng": 13.781018586655173
},
"duration": 500
}
],
"demand": [
3
],
"order":2
}
]
}
},
{
"id": "job_10",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.55137844164478,
"lng": 13.509316000155943
},
"duration": 500
}
],
"demand": [
3
],
"order":2
}
]
}
}
]
}
}
Solution
以下の解決策からわかるように、1台の車両が最初に job_2
、job_1
、および order
1でjob_6
を提供し、その後2台が,
order
2で job_9
、job_8
、job_7
、job_10
を提供します。残りの作業 - order
の2つを含む(job_5
、 job_3
、job_4
) は、別の車両によって提供されるように最適化されます。
{
"statistic": {
"cost": 697.76,
"distance": 241984,
"duration": 26211,
"times": {
"driving": 21211,
"serving": 5000,
"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-27T06:03:00Z"
},
"load": [
9
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.90926602381726,
"lng": 13.781018586655174
},
"time": {
"arrival": "2021-08-27T06:56:53Z",
"departure": "2021-08-27T07:05:13Z"
},
"load": [
6
],
"activities": [
{
"jobId": "job_9",
"type": "delivery"
}
],
"distance": 11909
},
{
"location": {
"lat": 52.91900693527653,
"lng": 13.92574157985448
},
"time": {
"arrival": "2021-08-27T07:26:14Z",
"departure": "2021-08-27T07:34:34Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_8",
"type": "delivery"
}
],
"distance": 24698
},
{
"location": {
"lat": 52.73186486317331,
"lng": 13.59405790954721
},
"time": {
"arrival": "2021-08-27T08:19:56Z",
"departure": "2021-08-27T08:28:16Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_7",
"type": "delivery"
}
],
"distance": 35735
},
{
"location": {
"lat": 52.529953,
"lng": 13.314877
},
"time": {
"arrival": "2021-08-27T09:20:22Z",
"departure": "2021-08-27T09:20:22Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 43438
}
],
"statistic": {
"cost": 441.36400000000003,
"distance": 163393,
"duration": 11842,
"times": {
"driving": 10342,
"serving": 1500,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 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": [
6
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.469144533572845,
"lng": 13.497412369472364
},
"time": {
"arrival": "2021-08-27T14:35:54Z",
"departure": "2021-08-27T14:44:14Z"
},
"load": [
9
],
"activities": [
{
"jobId": "job_5",
"type": "pickup"
}
],
"distance": 3350
},
{
"location": {
"lat": 52.44927857909315,
"lng": 13.36502844360698
},
"time": {
"arrival": "2021-08-27T15:07:52Z",
"departure": "2021-08-27T15:16:12Z"
},
"load": [
12
],
"activities": [
{
"jobId": "job_3",
"type": "pickup"
}
],
"distance": 12036
},
{
"location": {
"lat": 52.48998701990294,
"lng": 13.286076137075746
},
"time": {
"arrival": "2021-08-27T15:36:17Z",
"departure": "2021-08-27T15:44:37Z"
},
"load": [
15
],
"activities": [
{
"jobId": "job_4",
"type": "pickup"
}
],
"distance": 18658
},
{
"location": {
"lat": 52.53315878386378,
"lng": 13.352999270430129
},
"time": {
"arrival": "2021-08-27T16:04:46Z",
"departure": "2021-08-27T16:13:06Z"
},
"load": [
18
],
"activities": [
{
"jobId": "job_2",
"type": "pickup"
}
],
"distance": 73933
},
{
"location": {
"lat": 52.58136440229602,
"lng": 13.423236627987324
},
"time": {
"arrival": "2021-08-27T16:37:27Z",
"departure": "2021-08-27T16:45:47Z"
},
"load": [
21
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
],
"distance": 91183
},
{
"location": {
"lat": 52.57604629377083,
"lng": 13.488619313215825
},
"time": {
"arrival": "2021-08-27T17:03:41Z",
"departure": "2021-08-27T17:12:01Z"
},
"load": [
18
],
"activities": [
{
"jobId": "job_6",
"type": "delivery"
}
],
"distance": 128474
},
{
"location": {
"lat": 52.55137844164478,
"lng": 13.509316000155945
},
"time": {
"arrival": "2021-08-27T17:25:49Z",
"departure": "2021-08-27T17:34:09Z"
},
"load": [
15
],
"activities": [
{
"jobId": "job_10",
"type": "delivery"
}
],
"distance": 157410
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T18:02:29Z",
"departure": "2021-08-27T18:02:29Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 168272
}
],
"statistic": {
"cost": 256.39599999999996,
"distance": 78591,
"duration": 14369,
"times": {
"driving": 10869,
"serving": 3500,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}
この場合、ジョブタスクの順序が最適化されたソリューションに大きく影響することに注意してください。問題は同じですが、特定の注文が設定されていない場合、ツアーは完全に異なる方法で作成されます - job_1
、 job_9
、 job_8
、job_7
、 job_6
、 job_10
、 job_5
、job_3
(車両 1 の場合)、job_2
および job_4
(車両 2 の場合)。
[ ジョブタスクの順序 ] および [ 時間帯 ]
ジョブタスクの順序はソフトな制約 であるため、skills、territories、demand、time windowsなど、ツアープランでは難しいと見なされる他のジョブの制約を使用するために、省略される場合があります。 時間帯のあるジョブのジョブタスク順を使用して問題の例を作成し、その動作を確認してみましょう。
以下の問題では、 10 件のジョブを別の時間帯で処理しています。 ジョブの中には、 1 日の前半、 2 日目、 日中の間に処理されるものがあります。 これらの制約は非常にシンプルに見え、この場合のツアーは、車両のシフトが 08:47 から 19:47 になっているため、すべての作業の時間帯を含むことを考慮して非常に簡単に作成されます。 しかしさらに、ここでは一部のジョブに対してorder
1 を宣言し、他のジョブに対しては順序 2 を宣言する順序制約があります。したがって、ここでそれらがどのように相関するかを確認できます。
制約の概要は次のようになります。
-
job_1_02
とjob_2_02
のorder
2の時間帯は午前 9 時から午後 13 時 10 分です -
job_3_02
-order
2の時間帯は、9:00 ~ 18:10です -
job_4_02
および job_5_02
-order
2の時間帯は 14.00 ~ 18:10 です -
job_6_01
- order
1の時間帯は、 9:00〜18:10です -
job_7_01
および job_8_01
-order
1の時間帯は 14:00 ~ 18:10です -
job_9_01
および job_10_01
-order
1の時間帯は、9:00 ~ 13:10分です
Problems
{
"fleet": {
"types": [
{
"id": "b2147500aa87",
"profile": "car_9b09eea674ae",
"costs": {
"fixed": 7.0,
"distance": 0.001,
"time": 0.005
},
"shifts": [
{
"start": {
"time": "2022-06-22T08:47:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2022-06-22T19:47:00Z",
"location": {
"lat": 52.65532138588243,
"lng": 13.422448025024245
}
}
}
],
"capacity": [
3800
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_9b09eea674ae"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1_O2",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2022-06-22T09:00:00Z",
"2022-06-22T13:10:00Z"
]
],
"location": {
"lat": 52.4781979393528,
"lng": 13.454404067996537
},
"duration": 600
}
],
"demand": [
1
],
"order":2
}
]
}
},
{
"id": "job_2_O2",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2022-06-22T09:00:00Z",
"2022-06-22T13:10:00Z"
]
],
"location": {
"lat": 52.5058605159953,
"lng": 13.448619930375902
},
"duration": 500
}
],
"demand": [
1
],
"order":2
}
]
}
},
{
"id": "job_3_O2",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2022-06-22T09:00:00Z",
"2022-06-22T18:10:00Z"
]
],
"location": {
"lat": 52.556422006689935,
"lng": 13.342132449499255
},
"duration": 500
}
],
"demand": [
1
],
"order":2
}
]
}
},
{
"id": "job_4_O2",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2022-06-22T14:00:00Z",
"2022-06-22T18:10:00Z"
]
],
"location": {
"lat": 52.6073501578623,
"lng": 13.466163540647994
},
"duration": 500
}
],
"demand": [
1
],
"order":2
}
]
}
},
{
"id": "job_5_O2",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2022-06-22T14:00:00Z",
"2022-06-22T18:10:00Z"
]
],
"location": {
"lat": 52.48146637768908,
"lng": 13.299952916343699
},
"duration": 500
}
],
"demand": [
1
],
"order":2
}
]
}
},
{
"id": "job_6_O1",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2022-06-22T09:00:00Z",
"2022-06-22T18:10:00Z"
]
],
"location": {
"lat": 52.45479850835988,
"lng": 13.511041608889517
},
"duration": 500
}
],
"demand": [
1
],
"order":1
}
]
}
},
{
"id": "job_7_O1",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2022-06-22T14:00:00Z",
"2022-06-22T18:10:00Z"
]
],
"location": {
"lat": 52.4572791183728,
"lng": 13.409100745681675
},
"duration": 500
}
],
"demand": [
1
],
"order":1
}
]
}
},
{
"id": "job_8_O1",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2022-06-22T14:00:00Z",
"2022-06-22T18:10:00Z"
]
],
"location": {
"lat": 52.56938393159874,
"lng": 13.45524111564537
},
"duration": 500
}
],
"demand": [
1
],
"order":1
}
]
}
},
{
"id": "job_9_O1",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2022-06-22T09:00:00Z",
"2022-06-22T13:10:00Z"
]
],
"location": { "lat": 52.555895660008986,
"lng": 13.308740445937364
},
"duration": 500
}
],
"demand": [
1
],
"order":1
}
]
}
},
{
"id": "job_10_O1",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2022-06-22T09:00:00Z",
"2022-06-22T13:10:00Z"
]
],
"location": {
"lat": 52.47292620856057,
"lng": 13.420509939038608
},
"duration": 500
}
],
"demand": [
1
],
"order":1
}
]
}
}
]
}
}
Solution
ソリューションを分析すると、車両はそれぞれの時間枠でジョブとして job_9_O1
、job_10_O1
、および job_9_O1
を最初に提供し、order
1 を実行したことがわかります。その後 job_1_O2
、job_2_O2
、job_5_O2
、job_3_O2
、job_4_O2
およびorder
2 がそれぞれの時間帯で処理されました。 そして結局、job_7_O1
とjob_8_O1
は、時間枠(これは厳しい制約です)の都合上、他のorder
の仕事と一緒に対応することができなかったため、ツアーには含まれませんでした。これらのジョブをツアーに含めるには、時間帯を延長するか、またはジョブタスクの順序を変更する必要があります。
{
"statistic": {
"cost": 191.54700000000003,
"distance": 105287,
"duration": 15852,
"times": {
"driving": 10800,
"serving": 4100,
"waiting": 952,
"break": 0
}
},
"tours": [
{
"vehicleId": "b2147500aa87_1",
"typeId": "b2147500aa87",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2022-06-22T08:47:00Z",
"departure": "2022-06-22T11:10:12Z"
},
"load": [
8
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.555895660008986,
"lng": 13.308740445937364
},
"time": {
"arrival": "2022-06-22T11:28:22Z",
"departure": "2022-06-22T11:36:42Z"
},
"load": [
7
],
"activities": [
{
"jobId": "job_9_O1",
"type": "delivery"
}
],
"distance": 8124
},
{
"location": {
"lat": 52.47292620856057,
"lng": 13.420509939038608
},
"time": {
"arrival": "2022-06-22T12:02:49Z",
"departure": "2022-06-22T12:11:09Z"
},
"load": [
6
],
"activities": [
{
"jobId": "job_10_O1",
"type": "delivery"
}
],
"distance": 29625
},
{
"location": {
"lat": 52.45479850835988,
"lng": 13.511041608889515
},
"time": {
"arrival": "2022-06-22T12:29:11Z",
"departure": "2022-06-22T12:37:31Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_6_O1",
"type": "delivery"
}
],
"distance": 37913
},
{
"location": {
"lat": 52.4781979393528,
"lng": 13.454404067996537
},
"time": {
"arrival": "2022-06-22T12:47:32Z",
"departure": "2022-06-22T12:57:32Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_1_O2",
"type": "delivery"
}
],
"distance": 46535
},
{
"location": {
"lat": 52.5058605159953,
"lng": 13.448619930375902
},
"time": {
"arrival": "2022-06-22T13:10:00Z",
"departure": "2022-06-22T13:18:20Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_2_O2",
"type": "delivery"
}
],
"distance": 51559
},
{
"location": {
"lat": 52.48146637768908,
"lng": 13.2999529163437
},
"time": {
"arrival": "2022-06-22T13:44:08Z",
"departure": "2022-06-22T14:08:20Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_5_O2",
"type": "delivery"
}
],
"distance": 65624
},
{
"location": {
"lat": 52.556422006689935,
"lng": 13.342132449499257
},
"time": {
"arrival": "2022-06-22T14:26:49Z",
"departure": "2022-06-22T14:35:09Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_3_O2",
"type": "delivery"
}
],
"distance": 78671
},
{
"location": {
"lat": 52.6073501578623,
"lng": 13.466163540647994
},
"time": {
"arrival": "2022-06-22T15:04:40Z",
"departure": "2022-06-22T15:13:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_4_O2",
"type": "delivery"
}
],
"distance": 92173
},
{
"location": {
"lat": 52.65532138588243,
"lng": 13.422448025024243
},
"time": {
"arrival": "2022-06-22T15:34:24Z",
"departure": "2022-06-22T15:34:24Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 103362
}
],
"statistic": {
"cost": 191.54700000000003,
"distance": 105287,
"duration": 15852,
"times": {
"driving": 10800,
"serving": 4100,
"waiting": 952,
"break": 0
}
},
"shiftIndex": 0
}
],
"unassigned": [
{
"jobId": "job_7_O1",
"reasons": [
{
"code": "TIME_WINDOW_CONSTRAINT",
"description": "cannot be visited within time window",
"details": [
{
"vehicleId": "b2147500aa87_1",
"shiftIndex": 0
}
]
}
]
},
{
"jobId": "job_8_O1",
"reasons": [
{
"code": "TIME_WINDOW_CONSTRAINT",
"description": "cannot be visited within time window",
"details": [
{
"vehicleId": "b2147500aa87_1",
"shiftIndex": 0
}
]
}
]
}
]
}
リレーションによるジョブタスクの順序
状況によっては、特定の順序のジョブがある場合、ツアーの開始時または終了時に一部のジョブを実行する必要がある場合など、問題をモデル化する必要がある場合があります。この場合、順序関係の予約アクティビティIDdeparture
とarrival
を業務タスクの順序制約と組み合わせて使用することができます
以下では、 2 台の車両で 2 名の作業が可能で、 4 名の作業でそれぞれ 1 名の作業が必要になります。 1 つのジョブは、 order
2 で、残りの 2つのジョブが order
1. です
job_1
- order
2 job_2
- order
1 job_3
- order
1 job_4
- order
1
ジョブの順序と需要と能力の相関関係によれば、order
2 の仕事はいずれかのツアーで最後に提供されます。しかし、何らかの理由 で、job_2
とorder
の1はツアーの最後のサービスを提供するジョブになります。
ジョブにどの order
の値を指定しても、特定のジョブをツアーの最後に実行する必要がある場合は、最後に arrival
の予約されたアクティビティ ID を追加することにより、この制約を順序関係で設定する必要があります。 relations
と比較 order
して厳しい制約があるため、到着に指定されたジョブがツアーの最後のジョブとして処理されます。
このような制約の問題は、次のようになります。
Problems
{
"fleet": {
"types": [
{
"id": "Vehicle_1",
"profile": "car_c145d34adba6",
"costs": {
"fixed": 13.0,
"distance": 0.001,
"time": 0.008
},
"shifts": [
{
"start": {
"time": "2022-06-23T08:10:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2022-06-23T22:10:00Z",
"location": {
"lat": 52.44411159204712,
"lng": 13.328809259875186
}
},
"breaks": [
{
"duration": 1800,
"times": [
[
"2022-06-23T12:10:00Z",
"2022-06-23T13:10:00Z"
]
]
}
]
}
],
"capacity": [
2
],
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car_c145d34adba6"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.43350418357267,
"lng": 13.45451594339357
},
"duration": 500
}
],
"demand": [
1
],
"order": 2
}
]
}
},
{
"id": "job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.604439965100795,
"lng": 13.31543988319147
},
"duration": 500
}
],
"demand": [
1
],
"order": 1
}
]
}
},
{
"id": "job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.57066638953007,
"lng": 13.428175528293371
},
"duration": 500
}
],
"demand": [
1
],
"order": 1
}
]
}
},
{
"id": "job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.611818948643425,
"lng": 13.430786777678113
},
"duration": 500
}
],
"demand": [
1
],
"order": 1
}
]
}
}
],
"relations": [
{
"type": "sequence",
"jobs": [
"arrival",
"job_2"
],
"vehicleId": "Vehicle_1_1"
}
]
}
}
Solution
ソリューションからわかるように、各車両は特定の順序で 2 つの作業を行います。 シーケンスの関係から予想さ れたとおり、ツアーではVehicle_1
がjob_2
を最後に処理します。
{
"statistic": {
"cost": 198.434,
"distance": 85898,
"duration": 10817,
"times": {
"driving": 8817,
"serving": 2000,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "Vehicle_1_1",
"typeId": "Vehicle_1",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2022-06-23T08:10:00Z",
"departure": "2022-06-23T08:10:00Z"
},
"load": [
2
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.611818948643425,
"lng": 13.430786777678112
},
"time": {
"arrival": "2022-06-23T08:32:38Z",
"departure": "2022-06-23T08:40:58Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
],
"distance": 13429
},
{
"location": {
"lat": 52.604439965100795,
"lng": 13.31543988319147
},
"time": {
"arrival": "2022-06-23T09:01:54Z",
"departure": "2022-06-23T09:10:14Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_2",
"type": "delivery"
}
],
"distance": 23914
},
{
"location": {
"lat": 52.44411159204712,
"lng": 13.328809259875186
},
"time": {
"arrival": "2022-06-23T09:39:36Z",
"departure": "2022-06-23T09:39:36Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 48784
}
],
"statistic": {
"cost": 104.931,
"distance": 48923,
"duration": 5376,
"times": {
"driving": 4376,
"serving": 1000,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
},
{
"vehicleId": "Vehicle_1_2",
"typeId": "Vehicle_1",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2022-06-23T08:10:00Z",
"departure": "2022-06-23T08:10:00Z"
},
"load": [
2
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.57066638953007,
"lng": 13.428175528293371
},
"time": {
"arrival": "2022-06-23T08:24:35Z",
"departure": "2022-06-23T08:32:55Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
],
"distance": 7075
},
{
"location": {
"lat": 52.43350418357267,
"lng": 13.45451594339357
},
"time": {
"arrival": "2022-06-23T09:10:47Z",
"departure": "2022-06-23T09:19:07Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_1",
"type": "delivery"
}
],
"distance": 26603
},
{
"location": {
"lat": 52.44411159204712,
"lng": 13.328809259875186
},
"time": {
"arrival": "2022-06-23T09:40:41Z",
"departure": "2022-06-23T09:40:41Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 37124
}
],
"statistic": {
"cost": 93.503,
"distance": 36975,
"duration": 5441,
"times": {
"driving": 4441,
"serving": 1000,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}