近隣の停車地をクラスター化する
旅程計画では、地理的に近いジョブを1つの停車地にクラスタリングすると、移動時間が短縮し、燃料消費が最小限になり、より効率的な旅程を作成できます。移動時間の短縮により、より多くのジョブを遂行できるようになり、シフト中に完了できるジョブの数を増やすことができます。
郵便サービスのユースケースを考えてみましょう。各郵便配達員に適した効率的なルート計画は、時間どおりの効果的な配達に不可欠です。
各郵便配達員に対して最適化されたルート計画には、配達ポイントのクラスターが複数含まれます。各クラスターは、配達員が徒歩で配達できる程度に近い距離にある配達ポイントの近隣または小さなエリアを表します。
配達員はクラスターごとに車両を一度駐車し、駐車地点から徒歩圏内のポイントに複数の手紙やパーセルを配達します。クラスター内のすべての配達を完了すると、郵便配達員は車両に戻り、車両で次のジョブまたはクラスターの場所に移動し、旅程内のすべての配達が完了するまでこのプロセスを繰り返します。
注
これはアルファ機能 (新規またはテスト段階であり、現在開発中) です。アルファ機能は、テストおよびフィードバックの目的で提供されています。これらは大幅に変更されたり、一般に入手できなくなったりする可能性があります。
詳細については、「テスト段階の機能の詳細」を参照してください。
次の図は、HERE Tour Planning APIによって実装された近隣の停車地のクラスタリングという概念を視覚化したものです。
この図は、クラスタリングアルゴリズムが近隣のジョブをクラスターにグループ化し、停車地の総数を9から4に減らすことで、旅程をより効率的にする方法を示しています。
注
クラスター化されたジョブを含むTour Planningソリューションでは、駐車する場所に関する情報は提供されません。代わりに、そのエリアに駐車地点が見つかった場合に、効率的にまとめて遂行できるジョブを特定します。
近隣の停車地のクラスタリングを理解する
HERE Tour Planning APIでは、shift設定の一部として提供されるstopConfiguration設定オブジェクトを使用して、最適化アルゴリズムが停車地をクラスターにまとめる方法を決定できます。
{
"stopConfiguration": {
"profile": "pedestrian",
"limits": {
"maxIntraStopDistance": 150
}
}
}前の例の内容：
profile：1つの停車地でのアクティビティ間の移動時間や距離を推定するために使用するルート検索プロファイルです。これは必須フィールドであり、問題のfleet構成のprofiles配列で宣言されているプロファイル名と一致する必要があります。徒歩で目的地を回るシナリオでは、pedestrianプロファイルを使用してください。車両のメインの運転プロファイルは停車地での移動を正確に計算できないため、使用しないでください。limits.maxIntraStopDistance：1つの停車地で許可される最大歩行距離 (メートル単位) です。最適化アルゴリズムは、stopConfiguration.profileで指定したプロファイルに対応するルーティイングマトリックスを使用して、この距離を計算します。
注
stopConfig機能は廃止されました。代わりにstopConfigurationを使用してください。
ヒント
fleet.types[].limitsにmaxIntraStopDistanceを設定することで、1台の車両が停車するすべての停車地において、徒歩で移動する距離の累積合計に上限を設定できます。これは、このチュートリアルで説明されている1つの停車地での最大移動距離に加えて適用される追加の制約です。詳細については、「APIリファレンス」を参照してください。
stopConfiguration機能を理解する
stopConfigurationを指定すると、最適化アルゴリズムは指定されたprofileを使用して、各停車地のアクティビティ間、および駐車場所に戻るまでの実際の時間と距離を計算します。さまざまな移動手段を想定したプロファイルから選択できますが、最も一般的かつ実用的な選択肢はpedestrianプロファイルです。
徒歩での移動は通常、車での移動よりも遅いため、最適化アルゴリズムが、複数の場所に都度駐車するよりも、クラスタリング (1か所に駐車して徒歩で回る) を常に優先するとは限りません。最適化アルゴリズムにクラスター化された停車地の生成を促すには、シフトへのstopBaseDurationの設定、場所に応じた駐車時間の使用、またはminimizeDistance目的関数の使用など、アルゴリズムがクラスタリングを選択しやすくなるインセンティブを与えることを検討してください。
詳細については、「APIリファレンス」を参照してください。
注
これは開発中のテスト段階の機能です。この機能を有効にするには、問題仕様で
clusterNearbyをexperimentalFeatures配列に追加します。詳細については、「テスト段階の機能の詳細」を参照してください。
停車地での移動距離とアクティビティの順序付け
クラスター化された停車地を含む各ソリューションには、クラスター化された各停車地での移動距離を定量化するintraStopDistance値が含まれます。HERE Tour Planning APIは、stopConfiguration.profileで指定されたプロファイルのルーティイングマトリックスを使用して、すべてのクラスター化された停車地についてintraStopDistanceを自動的に計算します。さらに、最適化アルゴリズムは、各旅程およびソリューション全体の統計情報のtimesオブジェクトに、クラスター化された停車地でのアクティビティ間の実際の移動時間を反映したintraStopの合計を出力します。
これらのメトリックは、車両の走行距離を減らすことと、クラスター化された配送に必要な徒歩移動の負担とのトレードオフを理解するのに役立ちます。
**最適化されたアクティビティシーケンス：**各クラスター内のアクティビティの順序はランダムではなく、来た時と同じ道を引き返すのを避けることでintraStopDistanceを最小化するように最適化されています。最適化アルゴリズムは、各クラスター内の配送ポイント間で最も効率的なルートを決定し、車両に戻るまでの経路が確実に最短となるようにします。
注
最適化アルゴリズムにおいて、
intraStopDistanceの最適化は最も優先順位が低くなっています。時間枠などの他の制約を歩行距離の最適化よりも優先すると、これらの制約を満たすために必要な場合には、最適ではない歩行順序になる可能性があります。
問題：近隣の停車地をクラスタリングして配達の効率を上げる
前述の郵便サービスのユースケースをHERE Tour Planning APIで使用するには、問題のJSONの例を考えてみましょう。この問題では、次の設定が重要になります。
-
shift設定のstopConfigurationと、profiles配列内のpedestrianプロファイル{ "stopConfiguration": { "profile": "pedestrian", "limits": { "maxIntraStopDistance": 250 } } }この
stopConfiguration.profile設定により、最適化アルゴリズムは歩行者pedestrianプロファイルを使用して、停車地におけるアクティビティ間の徒歩の所要時間と距離を計算します。また、maxIntraStopDistanceに250メートルを指定することで、1つの停車地で許可される最大歩行距離の合計を250メートルまでに制限します。 -
objectives配列。デフォルトでは、最適化アルゴリズムは総所要時間を最小化します。また、通常、徒歩は車での移動よりもはるかに遅いため、クラスタリングが選択されにくくなる場合があります。最適化アルゴリズムにクラスター化された停車地の生成をさらに促すには、クラスタリングのメリットを活かせる目的関数 (たとえば次のスニペットに示す"minimizeDistance"など) を追加すると効果的です。"objectives": [ { "type": "minimizeUnassigned" }, { "type": "minimizeDistance" } ]
次のセクションには、問題のJSON全体が含まれています。
注
clusterNearbyをexperimentalFeatures配列に必ず含めてください。
Click to expand/collapse the sample JSON
{
"configuration": {
"experimentalFeatures": [
"clusterNearby"
]
},
"fleet": {
"types": [
{
"id": "small",
"profile": "car",
"costs": {
"fixed": 20,
"distance": 0,
"time": 0.005
},
"shifts": [
{
"start": {
"time": "2023-05-28T08:00:00Z",
"location": {
"lat": 52.50935,
"lng": 13.41997
}
},
"end": {
"time": "2023-05-28T16:00:00Z",
"location": {
"lat": 52.50935,
"lng": 13.41997
}
},
"stopConfiguration": {
"profile": "pedestrian",
"limits": {
"maxIntraStopDistance": 250
}
}
}
],
"capacity": [
100
],
"amount": 10
}
],
"profiles": [
{
"name": "car",
"type": "car"
},
{
"name": "pedestrian",
"type": "pedestrian"
}
]
},
"plan": {
"jobs": [
{
"id": "Job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 52.5615,
"lng": 13.4973
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 52.506,
"lng": 13.5094
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 52.5617,
"lng": 13.497
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 52.56136,
"lng": 13.49701
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_5",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 52.5618,
"lng": 13.4986
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 52.5332,
"lng": 13.5197
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_7",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 52.5207,
"lng": 13.5186
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_8",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 52.5062,
"lng": 13.5094
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_9",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 52.5063,
"lng": 13.5093
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_10",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 52.56156,
"lng": 13.49674
}
}
],
"demand": [
1
]
}
]
}
}
]
},
"objectives": [
{
"type": "minimizeUnassigned"
},
{
"type": "minimizeDistance"
}
]
}ソリューションの解釈
最適化アルゴリズムは、近接する停車地から2つのクラスターを特定しました。以降のセクションでは分かりやすくするため、それぞれをクラスター「A」(北側のクラスター)、クラスター「B」(南側のクラスター) と表記します。旅程の可視化については、次の図をご覧ください。
次のセクションでは、ソリューション全体を示します。
Click to expand/collapse the sample JSON
{
"statistic": {
"cost": 50.19,
"distance": 26333,
"duration": 6038,
"times": {
"driving": 2857,
"serving": 3000,
"waiting": 0,
"stopping": 0,
"break": 0,
"intraStop": 181
},
"intraStopDistance": 164
},
"tours": [
{
"vehicleId": "small_1",
"typeId": "small",
"stops": [
{
"time": {
"arrival": "2023-05-28T08:00:00Z",
"departure": "2023-05-28T08:00:00Z"
},
"load": [
10
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 52.50935,
"lng": 13.41997
},
"time": {
"start": "2023-05-28T08:00:00Z",
"end": "2023-05-28T08:00:00Z",
"arrival": "2023-05-28T08:00:00Z"
}
}
],
"location": {
"lat": 52.50935,
"lng": 13.41997
},
"distance": 0
},
{
"time": {
"arrival": "2023-05-28T08:19:06Z",
"departure": "2023-05-28T08:40:06Z"
},
"load": [
6
],
"activities": [
{
"jobId": "Job_4",
"type": "delivery",
"location": {
"lat": 52.56136,
"lng": 13.49701
},
"time": {
"start": "2023-05-28T08:19:06Z",
"end": "2023-05-28T08:24:06Z",
"arrival": "2023-05-28T08:19:06Z"
}
},
{
"jobId": "Job_10",
"type": "delivery",
"location": {
"lat": 52.56156,
"lng": 13.49674
},
"time": {
"start": "2023-05-28T08:24:11Z",
"end": "2023-05-28T08:29:11Z",
"arrival": "2023-05-28T08:24:11Z"
}
},
{
"jobId": "Job_3",
"type": "delivery",
"location": {
"lat": 52.5617,
"lng": 13.497
},
"time": {
"start": "2023-05-28T08:29:34Z",
"end": "2023-05-28T08:34:34Z",
"arrival": "2023-05-28T08:29:34Z"
}
},
{
"jobId": "Job_1",
"type": "delivery",
"location": {
"lat": 52.5615,
"lng": 13.4973
},
"time": {
"start": "2023-05-28T08:34:41Z",
"end": "2023-05-28T08:39:41Z",
"arrival": "2023-05-28T08:34:41Z"
}
}
],
"location": {
"lat": 52.56136,
"lng": 13.49701
},
"distance": 9894,
"intraStopDistance": 60
},
{
"time": {
"arrival": "2023-05-28T08:40:53Z",
"departure": "2023-05-28T08:45:53Z"
},
"load": [
5
],
"activities": [
{
"jobId": "Job_5",
"type": "delivery",
"location": {
"lat": 52.5618,
"lng": 13.4986
},
"time": {
"start": "2023-05-28T08:40:53Z",
"end": "2023-05-28T08:45:53Z",
"arrival": "2023-05-28T08:40:53Z"
}
}
],
"location": {
"lat": 52.5618,
"lng": 13.4986
},
"distance": 10015
},
{
"time": {
"arrival": "2023-05-28T08:52:38Z",
"departure": "2023-05-28T08:57:38Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_6",
"type": "delivery",
"location": {
"lat": 52.5332,
"lng": 13.5197
},
"time": {
"start": "2023-05-28T08:52:38Z",
"end": "2023-05-28T08:57:38Z",
"arrival": "2023-05-28T08:52:38Z"
}
}
],
"location": {
"lat": 52.5332,
"lng": 13.5197
},
"distance": 13817
},
{
"time": {
"arrival": "2023-05-28T09:00:23Z",
"departure": "2023-05-28T09:05:23Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Job_7",
"type": "delivery",
"location": {
"lat": 52.5207,
"lng": 13.5186
},
"time": {
"start": "2023-05-28T09:00:23Z",
"end": "2023-05-28T09:05:23Z",
"arrival": "2023-05-28T09:00:23Z"
}
}
],
"location": {
"lat": 52.5207,
"lng": 13.5186
},
"distance": 15355
},
{
"time": {
"arrival": "2023-05-28T09:09:30Z",
"departure": "2023-05-28T09:26:31Z"
},
"load": [
0
],
"activities": [
{
"jobId": "Job_2",
"type": "delivery",
"location": {
"lat": 52.506,
"lng": 13.5094
},
"time": {
"start": "2023-05-28T09:09:30Z",
"end": "2023-05-28T09:14:30Z",
"arrival": "2023-05-28T09:09:30Z"
}
},
{
"jobId": "Job_9",
"type": "delivery",
"location": {
"lat": 52.5063,
"lng": 13.5093
},
"time": {
"start": "2023-05-28T09:15:30Z",
"end": "2023-05-28T09:20:30Z",
"arrival": "2023-05-28T09:15:30Z"
}
},
{
"jobId": "Job_8",
"type": "delivery",
"location": {
"lat": 52.5062,
"lng": 13.5094
},
"time": {
"start": "2023-05-28T09:20:40Z",
"end": "2023-05-28T09:25:40Z",
"arrival": "2023-05-28T09:20:40Z"
}
}
],
"location": {
"lat": 52.506,
"lng": 13.5094
},
"distance": 17835,
"intraStopDistance": 104
},
{
"time": {
"arrival": "2023-05-28T09:40:38Z",
"departure": "2023-05-28T09:40:38Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 52.50935,
"lng": 13.41997
},
"time": {
"start": "2023-05-28T09:40:38Z",
"end": "2023-05-28T09:40:38Z",
"arrival": "2023-05-28T09:40:38Z"
}
}
],
"location": {
"lat": 52.50935,
"lng": 13.41997
},
"distance": 26333
}
],
"statistic": {
"cost": 50.19,
"distance": 26333,
"duration": 6038,
"times": {
"driving": 2857,
"serving": 3000,
"waiting": 0,
"stopping": 0,
"break": 0,
"intraStop": 181
},
"intraStopDistance": 164
},
"shiftIndex": 0
}
]
}ソリューションでは、クラスター化された各停車地にintraStopDistanceプロパティが含まれます。このプロパティは、該当するクラスター内の停車地で、車両から各目的地を回って移動した総距離に、車両へ戻る復路の距離を加算した値を表します。pedestrianプロファイルを使用している場合、具体的には、この距離は徒歩の移動距離を示します。
車両に戻るまでの移動を含めた、クラスター化された各停車地で目的地を回る距離の合計は、サンプルシナリオで説明されているように、郵便配達ルートの効率性を把握するための貴重なインサイトとなります。各クラスターの詳細は次のとおりです。
- クラスターA：
intraStopDistance: 60メートル - 郵便配達員は、このクラスター内の4つの配達場所の間を合計約60メートル歩き、さらに車両に戻ります。 - クラスターB：
intraStopDistance: 104メートル - 郵便配達員は、このクラスター内の3つの配達場所の間を合計約104メートル歩き、さらに車両に戻ります。 - 停車地での総移動距離 (ソリューションの統計)：
164メートル - 旅程全体のすべてのクラスター化された停車地での合計歩行距離。 - クラスター化されたすべての停車地におけるアクティビティ間の徒歩移動時間 (ソリューションの統計)：
times.intraStop: 180秒。
以下のセクションでは、2つのクラスターについてより詳しく説明します。
クラスター「A」
北側のクラスターは、stopConfigurationオブジェクトで指定されているクラスタリングの基準を満たす4つのジョブで構成されています。
Job_5 (停車地2) の場合、そのジョブはmaxIntraStopDistanceの基準を満たさないため、クラスターに含めることができません。Job_5をクラスターに含めると、maxIntraStopDistanceの上限である250メートルを超えて歩く必要が生じるためです。
最適化アルゴリズムにクラスターの停車地2が含まれるようにするには、maxIntraStopDistanceの上限値を250から、Job_5への往復徒歩距離をカバーできる値まで引き上げてください。
クラスター「B」
南側のクラスター (B) の場合、クラスタリングを導入したことで、クラスタリングを使用しなかった場合のソリューションと比較して、得られるソリューションに大きな違いが生じています。この場合、クラスタリングにより一方通行の道路を迂回する必要がなくなります。
| クラスタリングなし | クラスタリングあり |
|---|---|
 |  |
停車地9と10は一方通行の道路沿いの角を曲がったところにあるため、クラスタリングのないソリューションでは、車両がこれらの停車地にサービスを提供するには一方通行の道路に沿って迂回する必要があります。ただし、最適化アルゴリズムがこれらの停車地をクラスタリングすると、車両は5と示されている停車地に駐車します。その後、郵便配達員は角を曲がったところにある停車地に徒歩で移動し、車両に戻り、より短いルートで配達を続けることができるため、燃料と時間の両方を節約できます。
結論
このチュートリアルでは、HERE Tour Planning APIにclusterNearbyフィーチャーを組み込んでそのメリットを活用する方法について説明しました。問題の例では、このフィーチャーを紹介し、その利点を示しました。
stopConfiguration.limits.maxIntraStopDistanceを使用して、ビジネスニーズに合わせてクラスターサイズを調整し、最適化されたルート計画を作成できます。stopConfigurationを使用して、各停車地におけるアクティビティ間の実際の徒歩所要時間と距離を計算することにより、最適化アルゴリズムによる予測精度が向上します。- クラスタリングにより、特に一方通行の道路を含むシナリオで、迂回を減らし、燃料を節約し、移動時間を短縮できます。
次のステップ
先月の更新