コストに合わせて旅程を最適化する
効率的な物流と輸送管理は最適化されたルートに大きく依存しています。HERE Tour Planning APIはcostオブジェクト内にカプセル化されたいくつかの主要なパラメーターに基づいてルートを微調整できるようにする堅牢なソリューションです。
problem仕様のコンテキストでは、costはソリューションの計算中に車両に関連する費用を表すモデルを指します。割り当てられていないジョブの数を最小限に抑えたり、距離、時間、固定コストの制約に基づいてルートを最適化したり、ルートに最も効率的なルートを提示したりといった要素が含まれます。
このチュートリアルでは1台の車両について時間と距離のトレードオフを検討するいくつかの実用的なシナリオを掘り下げます。その後、追加要素として固定コストを導入し、フリートマネジメントについて進めます。
時間または距離を優先する場合のルート最適化
次のサンプルシナリオには1台の車両が複数のジョブ場所を移動するケースが含まれています。目的はtimeやdistanceパラメーターを優先すると、ルート選択、総走行距離、ルートの所要時間にいかに大きな影響を与える可能性があるかを明確にすることです。
短いルート所要時間を優先するには、timeパラメーターに高いコストを割り当てます。逆に、短いルート距離に重点を置くのであれば、distanceパラメーターに関連付けられたコストを増やす方が適している可能性があります。この柔軟性により、さまざまな値を試して独自の要件に合った最適なバランスを見つけることができます。
ヒント
carの場合、profileオブジェクトは2つのメインモード (fastとshort) に基づいてルートの優先順位を指定できるようにして、所要時間または距離のいずれかを優先する代替手段を提供します。この場合、システムはより短時間のルートまたはより短距離のルートを優先するよう設定されます。これにより、スピードを重視したり、総距離を最小限に抑えたりする柔軟性を実現します。
次のサンプル問題を出発点として考えてみましょう。
Click to expand/collapse the sample JSON
{
"fleet": {
"types": [
{
"id": "Vehicle_1",
"profile": "car",
"costs": {
"fixed": 2,
"distance": 0.0001,
"time": 0.0001
},
"shifts": [
{
"start": {
"time": "2021-10-23T08:00:00Z",
"location": {
"lat": 51.059188,
"lng": 13.540317
}
},
"end": {
"time": "2021-10-23T21:00:00Z",
"location": {
"lat": 51.059188,
"lng": 13.540317
}
}
}
],
"capacity": [
10
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car"
}
]
},
"plan": {
"jobs": [
{
"id": "Job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 51.05238,
"lng": 13.74114
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_2",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 51.06099,
"lng": 13.75245
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_3",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 51.08511,
"lng": 13.76875
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_4",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 51.1323847,
"lng": 13.7779515
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_5",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 51.11716,
"lng": 13.73054
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 51.12308,
"lng": 13.76406
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_7",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_8",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_9",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_10",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 51.06866,
"lng": 13.77273
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
}
]
}
}前のJSONサンプルで概説した問題の簡単な要約を以下に示します。
- 運行管理設定：
- 車両タイプとプロファイル：単一の運行管理 (
Vehicle_1) は1台の車両で構成されています。その積載容量は10であり、carとしての運用が定義されています。 - コスト：
- 車両の初期固定コストは
2に設定されています。 - 初期時間コストおよび距離コストは
0.0001に設定されています。
- 車両の初期固定コストは
- シフト：運行管理の運用は
08:00から21:00です。 - 車両プロファイル：人間が読める名前の付いた
carとして識別されます。
- 車両タイプとプロファイル：単一の運行管理 (
- ジョブプラン：
- ジョブ：プランには10件のジョブが定義されており、それぞれに固有のIDが割り当てられています。
- タスク：各ジョブは場所、期間、需要を含む集荷タスクまたは配達タスクで構成されます。
シナリオ1：短いルート所要時間を優先する
時間効率の優先順位付けの影響を強調するために、次の例に示すようにtimeパラメーター値を0.0005に増やして、JSONリクエスト本文のcostsセクションを調整できます。
"costs":
{
"fixed": 2,
"distance": 0.0001,
"time": 0.0005
}前の例で示したように設定を調整した後、APIは次のsolutionを返します。
Click to expand/collapse the sample JSON
{
"statistic": {
"cost": 18.1365,
"distance": 64125,
"duration": 19448,
"times": {
"driving": 4448,
"serving": 15000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "Vehicle_1_1",
"typeId": "Vehicle_1",
"stops": [
{
"time": {
"arrival": "2021-10-23T08:00:00Z",
"departure": "2021-10-23T08:00:00Z"
},
"load": [
5
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"time": {
"start": "2021-10-23T08:00:00Z",
"end": "2021-10-23T08:00:00Z"
}
}
],
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"distance": 0
},
{
"time": {
"arrival": "2021-10-23T08:15:42Z",
"departure": "2021-10-23T09:30:42Z"
},
"load": [
2
],
"activities": [
{
"jobId": "Job_7",
"type": "delivery",
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"start": "2021-10-23T08:15:42Z",
"end": "2021-10-23T08:40:42Z"
}
},
{
"jobId": "Job_9",
"type": "delivery",
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"start": "2021-10-23T08:40:42Z",
"end": "2021-10-23T09:05:42Z"
}
},
{
"jobId": "Job_8",
"type": "delivery",
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"start": "2021-10-23T09:05:42Z",
"end": "2021-10-23T09:30:42Z"
}
}
],
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"distance": 18698
},
{
"time": {
"arrival": "2021-10-23T09:41:11Z",
"departure": "2021-10-23T10:06:11Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Job_1",
"type": "pickup",
"location": {
"lat": 51.05238,
"lng": 13.74114
},
"time": {
"start": "2021-10-23T09:41:11Z",
"end": "2021-10-23T10:06:11Z"
}
}
],
"location": {
"lat": 51.05238,
"lng": 13.74114
},
"distance": 24323
},
{
"time": {
"arrival": "2021-10-23T10:11:07Z",
"departure": "2021-10-23T10:36:07Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_2",
"type": "pickup",
"location": {
"lat": 51.06099,
"lng": 13.75245
},
"time": {
"start": "2021-10-23T10:11:07Z",
"end": "2021-10-23T10:36:07Z"
}
}
],
"location": {
"lat": 51.06099,
"lng": 13.75245
},
"distance": 26693
},
{
"time": {
"arrival": "2021-10-23T10:39:08Z",
"departure": "2021-10-23T11:04:08Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Job_10",
"type": "delivery",
"location": {
"lat": 51.06866,
"lng": 13.77273
},
"time": {
"start": "2021-10-23T10:39:08Z",
"end": "2021-10-23T11:04:08Z"
}
}
],
"location": {
"lat": 51.06866,
"lng": 13.77273
},
"distance": 28558
},
{
"time": {
"arrival": "2021-10-23T11:09:38Z",
"departure": "2021-10-23T11:34:38Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_3",
"type": "pickup",
"location": {
"lat": 51.08511,
"lng": 13.76875
},
"time": {
"start": "2021-10-23T11:09:38Z",
"end": "2021-10-23T11:34:38Z"
}
}
],
"location": {
"lat": 51.08511,
"lng": 13.76875
},
"distance": 31988
},
{
"time": {
"arrival": "2021-10-23T11:44:24Z",
"departure": "2021-10-23T12:09:24Z"
},
"load": [
5
],
"activities": [
{
"jobId": "Job_4",
"type": "pickup",
"location": {
"lat": 51.1323847,
"lng": 13.7779515
},
"time": {
"start": "2021-10-23T11:44:24Z",
"end": "2021-10-23T12:09:24Z"
}
}
],
"location": {
"lat": 51.1323847,
"lng": 13.7779515
},
"distance": 38545
},
{
"time": {
"arrival": "2021-10-23T12:13:21Z",
"departure": "2021-10-23T12:38:21Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_6",
"type": "delivery",
"location": {
"lat": 51.12308,
"lng": 13.76406
},
"time": {
"start": "2021-10-23T12:13:21Z",
"end": "2021-10-23T12:38:21Z"
}
}
],
"location": {
"lat": 51.12308,
"lng": 13.76406
},
"distance": 40353
},
{
"time": {
"arrival": "2021-10-23T12:43:41Z",
"departure": "2021-10-23T13:08:41Z"
},
"load": [
5
],
"activities": [
{
"jobId": "Job_5",
"type": "pickup",
"location": {
"lat": 51.11716,
"lng": 13.73054
},
"time": {
"start": "2021-10-23T12:43:41Z",
"end": "2021-10-23T13:08:41Z"
}
}
],
"location": {
"lat": 51.11716,
"lng": 13.73054
},
"distance": 44447
},
{
"time": {
"arrival": "2021-10-23T13:24:08Z",
"departure": "2021-10-23T13:24:08Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"time": {
"start": "2021-10-23T13:24:08Z",
"end": "2021-10-23T13:24:08Z"
}
}
],
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"distance": 64125
}
],
"statistic": {
"cost": 18.1365,
"distance": 64125,
"duration": 19448,
"times": {
"driving": 4448,
"serving": 15000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}次の図は、選択したルート、ジョブの順序、距離と所要時間の値に重点を置いて、前述のソリューションのルートパラメーターを示しています。
ルートの可視化からわかるように、このソリューションではルート全体の所要時間を最小限に抑えることを優先し、次の詳細が表示されます。
- 距離：
64,13km - 所要時間：
5h 24m
シナリオ2：短いルート距離を優先する
逆に、最適化アルゴリズムがルートの最短ルートの選択を優先するように設定するには、次の例に示すようにdistance値を増やしつつtime値を0.0001のままにします。
"costs":
{
"fixed": 2,
"distance": 0.0005,
"time": 0.0001
}送信された問題のcostセクションを調整してルート距離を最小限に抑えることを優先すると、APIが次のソリューションを返します。
Click to expand/collapse the sample JSON
{
"statistic": {
"cost": 35.5286,
"distance": 63109,
"duration": 19741,
"times": {
"driving": 4741,
"serving": 15000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "Vehicle_1_1",
"typeId": "Vehicle_1",
"stops": [
{
"time": {
"arrival": "2021-10-23T08:00:00Z",
"departure": "2021-10-23T08:00:00Z"
},
"load": [
5
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"time": {
"start": "2021-10-23T08:00:00Z",
"end": "2021-10-23T08:00:00Z"
}
}
],
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"distance": 0
},
{
"time": {
"arrival": "2021-10-23T08:15:42Z",
"departure": "2021-10-23T09:30:42Z"
},
"load": [
2
],
"activities": [
{
"jobId": "Job_7",
"type": "delivery",
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"start": "2021-10-23T08:15:42Z",
"end": "2021-10-23T08:40:42Z"
}
},
{
"jobId": "Job_8",
"type": "delivery",
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"start": "2021-10-23T08:40:42Z",
"end": "2021-10-23T09:05:42Z"
}
},
{
"jobId": "Job_9",
"type": "delivery",
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"start": "2021-10-23T09:05:42Z",
"end": "2021-10-23T09:30:42Z"
}
}
],
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"distance": 18698
},
{
"time": {
"arrival": "2021-10-23T09:36:49Z",
"departure": "2021-10-23T10:01:49Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Job_5",
"type": "pickup",
"location": {
"lat": 51.11716,
"lng": 13.73054
},
"time": {
"start": "2021-10-23T09:36:49Z",
"end": "2021-10-23T10:01:49Z"
}
}
],
"location": {
"lat": 51.11716,
"lng": 13.73054
},
"distance": 23888
},
{
"time": {
"arrival": "2021-10-23T10:09:20Z",
"departure": "2021-10-23T10:34:20Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_4",
"type": "pickup",
"location": {
"lat": 51.1323847,
"lng": 13.7779515
},
"time": {
"start": "2021-10-23T10:09:20Z",
"end": "2021-10-23T10:34:20Z"
}
}
],
"location": {
"lat": 51.1323847,
"lng": 13.7779515
},
"distance": 29458
},
{
"time": {
"arrival": "2021-10-23T10:38:17Z",
"departure": "2021-10-23T11:03:17Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Job_6",
"type": "delivery",
"location": {
"lat": 51.12308,
"lng": 13.76406
},
"time": {
"start": "2021-10-23T10:38:17Z",
"end": "2021-10-23T11:03:17Z"
}
}
],
"location": {
"lat": 51.12308,
"lng": 13.76406
},
"distance": 31266
},
{
"time": {
"arrival": "2021-10-23T11:11:08Z",
"departure": "2021-10-23T11:36:08Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_3",
"type": "pickup",
"location": {
"lat": 51.08511,
"lng": 13.76875
},
"time": {
"start": "2021-10-23T11:11:08Z",
"end": "2021-10-23T11:36:08Z"
}
}
],
"location": {
"lat": 51.08511,
"lng": 13.76875
},
"distance": 36335
},
{
"time": {
"arrival": "2021-10-23T11:41:48Z",
"departure": "2021-10-23T12:06:48Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Job_10",
"type": "delivery",
"location": {
"lat": 51.06866,
"lng": 13.77273
},
"time": {
"start": "2021-10-23T11:41:48Z",
"end": "2021-10-23T12:06:48Z"
}
}
],
"location": {
"lat": 51.06866,
"lng": 13.77273
},
"distance": 39680
},
{
"time": {
"arrival": "2021-10-23T12:11:44Z",
"departure": "2021-10-23T12:36:44Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_2",
"type": "pickup",
"location": {
"lat": 51.06099,
"lng": 13.75245
},
"time": {
"start": "2021-10-23T12:11:44Z",
"end": "2021-10-23T12:36:44Z"
}
}
],
"location": {
"lat": 51.06099,
"lng": 13.75245
},
"distance": 41841
},
{
"time": {
"arrival": "2021-10-23T12:42:26Z",
"departure": "2021-10-23T13:07:26Z"
},
"load": [
5
],
"activities": [
{
"jobId": "Job_1",
"type": "pickup",
"location": {
"lat": 51.05238,
"lng": 13.74114
},
"time": {
"start": "2021-10-23T12:42:26Z",
"end": "2021-10-23T13:07:26Z"
}
}
],
"location": {
"lat": 51.05238,
"lng": 13.74114
},
"distance": 44137
},
{
"time": {
"arrival": "2021-10-23T13:29:01Z",
"departure": "2021-10-23T13:29:01Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"time": {
"start": "2021-10-23T13:29:01Z",
"end": "2021-10-23T13:29:01Z"
}
}
],
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"distance": 63109
}
],
"statistic": {
"cost": 35.5286,
"distance": 63109,
"duration": 19741,
"times": {
"driving": 4741,
"serving": 15000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}次の図は、前の例からルート距離を最小限に抑えることを強調したソリューションを示しています。また、ルート所要時間を最小限に抑えることに焦点を当てたソリューションのルート詳細を示しています。
ルートの可視化からわかるように、このソリューションではルート距離を最小限に抑えることを優先し、次の詳細が表示されます。
- 距離：
63,11km - 所要時間：
5h 29m
これらのサンプル問題では距離と所要時間の最適化を選択した結果、ルートや合計所要時間が変わりました。
- 時間に最適化されたルートでは距離が若干長くなったものの、完了までの時間は短くなりました。
- 逆に、距離に最適化されたルートでは全体的な距離は短くなったものの、特定のジョブの順序により、所要時間が若干長くなりました。
- ソリューション内のジョブの順序は、選択した最適化シナリオに応じて変わりました。たとえば、距離の点で短いルートは、交通状況や特定の制約のために長い時間を要することがあります。逆もまた同様です。
変動する固定コストに合わせてルートを最適化する
固定コストはルート検索の最適化で使用できるもう1つのパラメーターです。固定コストは特定のタスクまたはジョブ用に車両を配備することに関連する変動しないコストを表します。これらのコストには車両のメンテナンス、ドライバーの賃金、走行距離や走行時間に左右されないその他の固定運用コストなどの費用が含まれます。
最適化アルゴリズムは、固定コストが異なる複数の車両を検知した場合に、timeやdistanceなどの他のコストパラメーターが同じ値であれば、固定コストの低い車両を優先する傾向にあります。この動作はルート選択ソリューションの全体的なコストを最小限に抑えることを目的とする最適化の問題の目的関数による影響を受けます。
この動作を示すために、前述の例の問題に次の変更を加えます。
costオブジェクト内のtimeとdistanceの値を等しくします (0.0001など)。CheapVehicle_1という別の運行管理を追加しました。Vehicle_1の設定と同じですが、fixedパラメーターのみが異なります。このパラメーターを1にして、関連するVehicle_1の値よりも小さくしました。
参考として次のJSONを参照してください。
{
"fleet": {
"types": [
{
"id": "Vehicle_1",
"profile": "car",
"costs": {
"fixed": 2,
"distance": 0.0001,
"time": 0.0001
},
"shifts": [
{
"start": {
"time": "2021-10-23T08:00:00Z",
"location": {
"lat": 51.059188,
"lng": 13.540317
}
},
"end": {
"time": "2021-10-23T21:00:00Z",
"location": {
"lat": 51.059188,
"lng": 13.540317
}
}
}
],
"capacity": [
10
],
"amount": 1
},
{
"id": "CheapVehicle_1",
"profile": "car",
"costs": {
"fixed": 1,
"distance": 0.0001,
"time": 0.0001
},
"shifts": [
{
"start": {
"time": "2021-10-23T08:00:00Z",
"location": {
"lat": 51.059188,
"lng": 13.540317
}
},
"end": {
"time": "2021-10-23T21:00:00Z",
"location": {
"lat": 51.059188,
"lng": 13.540317
}
}
}
],
"capacity": [
10
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car"
}
]
},
"plan": {
"jobs": [ ... ] // Jobs remain the same
}
}この問題を送信すると、HERE Tour Planning APIは次のソリューションを返します。
{
"statistic": {
"cost": 9.285,
"distance": 63109,
"duration": 19741,
"times": {
"driving": 4741,
"serving": 15000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "CheapVehicle_1_1",
"typeId": "CheapVehicle_1",
"stops": [ ... ], // Stops removed for simplicity
"statistic": {
"cost": 9.285,
"distance": 63109,
"duration": 19741,
"times": {
"driving": 4741,
"serving": 15000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}このシナリオでは両方の運行管理のtimeとdistanceの値は同一であるため、最適化アルゴリズムはVehicle_1よりもCheapVehicle_1を優先します。後者の方が固定コストを低く抑えられるためです。この決定はルート選択ソリューションの総コストを最小限に抑えるというアルゴリズムの目的に合致しています。以上のことから、運行管理の最適化における固定コストの重要な影響がわかります。固定コストが効率性と費用対効果のバランスをとる形で車両の選択と利用に影響を与えるためです。
注
HERE Tour Planning APIは車両の固定コストだけでなく、ルートの総コストを最小限に抑えることを目指しています。ある車両の固定コストは高いものの、ルートの総コストは低くなる場合 (時間や距離に最適化した結果など)、その車両が選択される可能性があります。 たとえば、前のサンプル問題では次のように設定していました。
Vehicle_1についてはtime値を0.0005に増やします。CheapVehicle_1についてはdistance値を0.0005に増やします。このような最適化の結果、APIではルートに対し、
CheapVehicle_1よりもVehicle_1("fixed": 2) が選択されます。CheapVehicle_1の固定コストが低い ("fixed": 1) 状況であってもです。
結論
- HERE Tour Planning APIは物流と輸送管理のための堅牢なソリューションを提供し、企業が多様なパラメーターに基づいてルートを最適化できるようにします。
- コストパラメーターはルート選択ソリューションの総コストに全体的に貢献し、車両の選択に影響を与えることで、運行管理の最適化において重要な役割を果たします。各コストパラメーターは最適化フローに独自の影響を与えます。このため、さまざまなコストパラメーターが最適化プロセスに影響を与えるさまざまな方法を考慮することが重要です。
次のステップ
詳細については、以下を参照してください。
- Submit a Vehicle Routing Problem to solve it synchronously (車両ルート検索問題を送信して同期的に解決する)
- Submit a Vehicle Routing Problem to solve it asynchronously (車両ルート検索問題を送信して非同期的に解決する)
26 日前の更新