ジョブに優先順位を付ける
車両ルート検索問題を効果的に解決するには、関連するジョブの優先順位を考慮することが必要なことが多くあります。たとえば、必須のジョブと必須ではないジョブが混在している問題が考えられますが、その中には特定のツアー内で完了しなければならないものもあれば、延期できるものもあります。このような場合、priority設定を使用して緊急性が高いジョブをできるだけ多く完了することに集中して、フリートの使用率を最適化する必要があります。
複雑な車両ルート検索問題では、ジョブの完了に影響する制約がジョブの優先順位だけではない場合があります。アルゴリズムでは適用可能な制約をすべて考慮し、優先順位の高いタスクを完了する必要性と、すべての割り当てをこなすことができない場合にスキップされるジョブまたは必須ではないジョブを最小限に抑える要件とのバランスをとります。
注
優先順位はツアー内のジョブの直接の順序を決定するものではありません。ルートの中でジョブの順序が変化する場合があります。そのため、優先順位の高いジョブはルート内のどこにでも配置される可能性があり、必ずしも優先順位の低いジョブよりも前にあるとは限りません。
ジョブの優先順位付けについて理解する
優先順位レベルは次のように定義されます。「優先順位が高い」ものとして指定されているジョブには優先順位レベルとして1が割り当てられる一方、優先順位がないか「優先順位が通常」のものとして指定されているジョブには5が割り当てられます。優先順位が指定されていないジョブは通常のジョブ (優先順位レベル5) と同様に処理されます。
注
- すべてのジョブで3つ以上の異なる優先順位レベル使を用できるのは現在のところベータ機能です。
- ベータ機能は開発の最終段階にあり、重大なバグは存在しませんが、カバレッジ、品質、パフォーマンス、またはテストカバレッジがまだ最終形ではない可能性があります。この機能のデータモデルおよび問題定義は、以前のバージョンから安定しており変更されていません。本番環境での完全な利用に向けて機能が完成に近づく中で、動作の細かな調整が行われる可能性があることを理解した上で、ベータ機能をアプリケーションで使用できます。
次のスニペットは、HERE Tour Planning APIの問題JSON内のジョブの優先順位レベルを定義する方法を示しています。
{
"id": "job_A",
"priority": 1, // job's priority level
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5054,
"lng": 13.4206
},
"duration": 540
}
],
"demand": [
1
]
}
]
}
}詳細については、「APIリファレンス」を参照してください。
サンプルユースケース：重要なジョブの優先順位付け
積載量が5の車両が1台あり、6件の集荷ジョブを完了する必要があるシナリオを考えてみましょう。3件のジョブには優先順位が割り当てられておらず、残りの3件には優先順位レベルが1に設定されているとします。
他のすべての制約が満たされている場合は、休憩に入る前にツアーで3件の必須ジョブを完了する必要があります。さらに、車両の積載量は全体的なジョブ需要よりも少ないため、一部の必須ではないジョブが完了しません。
次のリストは、サンプル問題に含まれるジョブとその優先順位設定を要約したものです。
Vehicle capacity-5job_1- 優先順位なしjob_2- 優先順位なしjob_3- 優先順位なしjob_4- 優先順位1位job_5- 優先順位1位job_6- 優先順位1位
問題
次のセクションでは、サンプルユースケースで定義されている問題の完全なJSONファイルを示しています。
Click to expand/collapse the sample JSON
{
"fleet": {
"types": [
{
"id": "7f5209042664",
"profile": "car_1",
"costs": {
"fixed": 5,
"distance": 0.007,
"time": 0.05
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T16:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
5
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.585527238853984,
"lng": 13.364236346248592
},
"duration": 840
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.47946109276297,
"lng": 13.298179193858115
},
"duration": 1140
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.60291926054419,
"lng": 13.440503699397226
},
"duration": 780
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_4",
"priority": 1,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.505480479124714,
"lng": 13.42064470670394
},
"duration": 540
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_5",
"priority": 1,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.56627920665773,
"lng": 13.338970191939882
},
"duration": 720
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_6",
"priority": 1,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.50945064762406,
"lng": 13.385190908809543
},
"duration": 840
}
],
"demand": [
1
]
}
]
}
}
]
}
}ソリューション
次のセクションには、最終的なソリューションの完全なJSONファイルが含まれており、優先順位設定がツアーの最適化にどのように影響するかを示しています。
Click to expand/collapse the sample JSON
{
"statistic": {
"cost": 655.363,
"distance": 36909,
"duration": 7840,
"times": {
"driving": 4120,
"serving": 3720,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "7f5209042664_1",
"typeId": "7f5209042664",
"stops": [
{
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"start": "2021-08-27T08:03:00Z",
"end": "2021-08-27T08:03:00Z"
}
}
],
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"distance": 0
},
{
"time": {
"arrival": "2021-08-27T08:13:13Z",
"departure": "2021-08-27T08:25:13Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_5",
"type": "pickup",
"location": {
"lat": 52.56627920665773,
"lng": 13.338970191939882
},
"time": {
"start": "2021-08-27T08:13:13Z",
"end": "2021-08-27T08:25:13Z"
}
}
],
"location": {
"lat": 52.56627920665773,
"lng": 13.338970191939882
},
"distance": 5898
},
{
"time": {
"arrival": "2021-08-27T08:31:41Z",
"departure": "2021-08-27T08:45:41Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"location": {
"lat": 52.585527238853984,
"lng": 13.364236346248592
},
"time": {
"start": "2021-08-27T08:31:41Z",
"end": "2021-08-27T08:45:41Z"
}
}
],
"location": {
"lat": 52.585527238853984,
"lng": 13.364236346248592
},
"distance": 9378
},
{
"time": {
"arrival": "2021-08-27T08:59:04Z",
"departure": "2021-08-27T09:12:04Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_3",
"type": "pickup",
"location": {
"lat": 52.60291926054419,
"lng": 13.440503699397226
},
"time": {
"start": "2021-08-27T08:59:04Z",
"end": "2021-08-27T09:12:04Z"
}
}
],
"location": {
"lat": 52.60291926054419,
"lng": 13.440503699397226
},
"distance": 16553
},
{
"time": {
"arrival": "2021-08-27T09:34:34Z",
"departure": "2021-08-27T09:43:34Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_4",
"type": "pickup",
"location": {
"lat": 52.505480479124714,
"lng": 13.42064470670394
},
"time": {
"start": "2021-08-27T09:34:34Z",
"end": "2021-08-27T09:43:34Z"
}
}
],
"location": {
"lat": 52.505480479124714,
"lng": 13.42064470670394
},
"distance": 29150
},
{
"time": {
"arrival": "2021-08-27T09:51:16Z",
"departure": "2021-08-27T10:05:16Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_6",
"type": "pickup",
"location": {
"lat": 52.50945064762406,
"lng": 13.385190908809545
},
"time": {
"start": "2021-08-27T09:51:16Z",
"end": "2021-08-27T10:05:16Z"
}
}
],
"location": {
"lat": 52.50945064762406,
"lng": 13.385190908809545
},
"distance": 32600
},
{
"time": {
"arrival": "2021-08-27T10:13:40Z",
"departure": "2021-08-27T10:13:40Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"start": "2021-08-27T10:13:40Z",
"end": "2021-08-27T10:13:40Z"
}
}
],
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"distance": 36909
}
],
"statistic": {
"cost": 655.363,
"distance": 36909,
"duration": 7840,
"times": {
"driving": 4120,
"serving": 3720,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
],
"unassigned": [
{
"jobId": "job_2",
"reasons": [
{
"code": "CAPACITY_CONSTRAINT",
"description": "cannot be assigned due to capacity of vehicle"
}
]
}
]
}前のソリューションを視覚化したものについては、次の図を参照してください。
ソリューションで示されているように、ジョブは次の順序で完了します。
job_5job_1job_3job_4job_6
このソリューションは、ツアーを計画するときに優先ジョブが最初に完了するとは限らないことを示しています。代わりに、最適なルートを決定するときに、場所やジョブタイプなどの他の制約と一緒に考慮されます。優先順位が高いジョブ (job_4とjob_6) は実行順序の観点からは優先されませんが、ツアーを計画する際には優先順位が考慮されます。その結果、これらのジョブはツアー計画に含まれます。
このサンプルシナリオでは、車両の積載量の制約によりjob_2が完了しませんでした。job_2に高い優先順位が指定されていなかったことを考慮すると、この結果は予想と一致しています。
サンプルユースケース#2：複数の優先順位レベルの導入
必須ジョブの数と元の優先順位設定を維持しながら、以前割り当てられていなかったjob_2をツアーに組み込むには、最初の2つの優先順位レベルに加えて追加の優先順位レベルを導入します。例：
job_1：優先順位なしjob_2：優先順位2位job_3：優先順位なしjob_4：優先順位1位job_5：優先順位1位job_6：優先順位1位
このシナリオでは、優先順位job_2がレベル2に引き上げられています。そのため、アルゴリズムでは、優先順位が最も高いジョブの後に、このジョブをツアーに含めることを優先します。
job_1とjob_3は優先順位が指定されないままになります。このように優先順位が指定されていないと、アルゴリズムの意思決定プロセスに影響を及ぼしかねず、車両の積載量が5の場合にはこれらのジョブの1つが割り当てられない可能性があります。
問題
次のセクションでは、更新された問題JSONファイルについて説明します。
Click to expand/collapse the sample JSON
{
"fleet": {
"types": [
{
"id": "7f5209042664",
"profile": "car_1",
"costs": {
"fixed": 5,
"distance": 0.007,
"time": 0.05
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T16:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
5
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.585527238853984,
"lng": 13.364236346248592
},
"duration": 840
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_2",
"priority": 2,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.47946109276297,
"lng": 13.298179193858115
},
"duration": 1140
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.60291926054419,
"lng": 13.440503699397226
},
"duration": 780
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_4",
"priority": 1,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.505480479124714,
"lng": 13.42064470670394
},
"duration": 540
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_5",
"priority": 1,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.56627920665773,
"lng": 13.338970191939882
},
"duration": 720
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_6",
"priority": 1,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.50945064762406,
"lng": 13.385190908809543
},
"duration": 840
}
],
"demand": [
1
]
}
]
}
}
]
}
}ソリューション
次のセクションには、最終的なソリューションの完全なJSONファイルが含まれており、新しい優先順位レベルの追加がツアーの最適化にどのように影響したかを示しています。
Click to expand/collapse the sample JSON
{
"statistic": {
"cost": 701.9540000000001,
"distance": 40822,
"duration": 8224,
"times": {
"driving": 4144,
"serving": 4080,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "7f5209042664_1",
"typeId": "7f5209042664",
"stops": [
{
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"start": "2021-08-27T08:03:00Z",
"end": "2021-08-27T08:03:00Z"
}
}
],
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"distance": 0
},
{
"time": {
"arrival": "2021-08-27T08:15:44Z",
"departure": "2021-08-27T08:29:44Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"location": {
"lat": 52.585527238853984,
"lng": 13.364236346248592
},
"time": {
"start": "2021-08-27T08:15:44Z",
"end": "2021-08-27T08:29:44Z"
}
}
],
"location": {
"lat": 52.585527238853984,
"lng": 13.364236346248592
},
"distance": 6989
},
{
"time": {
"arrival": "2021-08-27T08:35:45Z",
"departure": "2021-08-27T08:47:45Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_5",
"type": "pickup",
"location": {
"lat": 52.56627920665773,
"lng": 13.338970191939882
},
"time": {
"start": "2021-08-27T08:35:45Z",
"end": "2021-08-27T08:47:45Z"
}
}
],
"location": {
"lat": 52.56627920665773,
"lng": 13.338970191939882
},
"distance": 10546
},
{
"time": {
"arrival": "2021-08-27T09:02:33Z",
"departure": "2021-08-27T09:21:33Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_2",
"type": "pickup",
"location": {
"lat": 52.47946109276297,
"lng": 13.298179193858116
},
"time": {
"start": "2021-08-27T09:02:33Z",
"end": "2021-08-27T09:21:33Z"
}
}
],
"location": {
"lat": 52.47946109276297,
"lng": 13.298179193858116
},
"distance": 23632
},
{
"time": {
"arrival": "2021-08-27T09:37:53Z",
"departure": "2021-08-27T09:51:53Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_6",
"type": "pickup",
"location": {
"lat": 52.50945064762406,
"lng": 13.385190908809545
},
"time": {
"start": "2021-08-27T09:37:53Z",
"end": "2021-08-27T09:51:53Z"
}
}
],
"location": {
"lat": 52.50945064762406,
"lng": 13.385190908809545
},
"distance": 32276
},
{
"time": {
"arrival": "2021-08-27T09:59:11Z",
"departure": "2021-08-27T10:08:11Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_4",
"type": "pickup",
"location": {
"lat": 52.505480479124714,
"lng": 13.42064470670394
},
"time": {
"start": "2021-08-27T09:59:11Z",
"end": "2021-08-27T10:08:11Z"
}
}
],
"location": {
"lat": 52.505480479124714,
"lng": 13.42064470670394
},
"distance": 35543
},
{
"time": {
"arrival": "2021-08-27T10:20:04Z",
"departure": "2021-08-27T10:20:04Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"start": "2021-08-27T10:20:04Z",
"end": "2021-08-27T10:20:04Z"
}
}
],
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"distance": 40822
}
],
"statistic": {
"cost": 701.9540000000001,
"distance": 40822,
"duration": 8224,
"times": {
"driving": 4144,
"serving": 4080,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
],
"unassigned": [
{
"jobId": "job_3",
"reasons": [
{
"code": "CAPACITY_CONSTRAINT",
"description": "cannot be assigned due to capacity of vehicle"
}
]
}
]
}前のソリューションを視覚化したものについては、次の図を参照してください。
これまでと同様に、車両の積載量制約はどのジョブが完了するかを決定する際の役割を果たしました。優先順位レベルが割り当てられたJob_2はツアー計画に含まれていましたが、優先順位のないjob_3は積載量制限のため完了しませんでした。
次のステップ
詳細については、以下を参照してください。
- Submit a Vehicle Routing Problem to solve it synchronously (車両ルート検索問題を送信して同期的に解決する)
- Submit a Vehicle Routing Problem to solve it asynchronously (車両ルート検索問題を送信して非同期的に解決する)
26 日前の更新