近隣の停車地をクラスター化する
旅程計画では、地理的に近いジョブを1つの停車地にクラスタリングすると、移動時間が短縮し、燃料消費が最小限になり、より効率的なルートを作成できます。移動時間の短縮により、より多くのジョブを遂行できるようになり、シフト中に完了できるジョブの数を増やすことができます。
郵便サービスのユースケースを考えてみましょう。各郵便配達員に適した効率的なルート計画は、時間どおりの効果的な配達に不可欠です。
各郵便配達員に対して最適化されたルート計画には、配達ポイントのクラスターが複数含まれます。各クラスターは、配達員が徒歩で配達できる程度に近い距離にある配達ポイントの近隣または小さなエリアを表します。
配達員はクラスターごとに車両を一度駐車し、駐車地点から徒歩圏内のポイントに複数の手紙やパーセルを配達します。クラスター内のすべての配達を完了すると、郵便配達員は車両に戻り、車両で次のジョブまたはクラスターの場所に移動し、旅程内のすべての配達が完了するまでこのプロセスを繰り返します。
注
これはアルファ機能 (新規またはテスト段階であり、現在開発中) です。アルファ機能は、テストおよびフィードバックの目的で提供されています。これらは大幅に変更されたり、一般に入手できなくなったりする可能性があります。
詳細については、「テスト段階の機能の詳細」を参照してください。
次の図は、HERE Tour Planning APIによって実装された近隣の停車地のクラスタリングという概念を視覚化したものです。
この図は、クラスタリングアルゴリズムが近隣のジョブをクラスターにグループ化し、停車地の総数を9から4に減らすことで、ツアーをより効率的にする方法を示しています。
注
クラスター化されたジョブを含むTour Planningソリューションでは、駐車する場所に関する情報は提供されません。代わりに、そのエリアに駐車地点が見つかった場合に、効率的にまとめて遂行できるジョブを特定します。
近隣の停車地のクラスタリングを理解する
HERE Tour Planning APIでは、shift設定の一部として提供されるstopConfig設定オブジェクトを使用して、最適化アルゴリズムが停車地をクラスターにまとめる方法を決定できます。
{
"stopConfig": {
"type": "dbscan",
"maxDistanceToNeighbor": 50,
"maxDiameter": 200
}
}前の例の内容：
type": "dbscan"：DBSCAN (Density-based Spatial Clustering of Applications with Noise) クラスタリングアルゴリズムを使用して、クラスターに加えるメンバーを定義します。maxDistanceToNeighbor：あるジョブと、クラスター内で最も近い隣接ジョブ間の最大距離 (メートル単位) を定義します。あるジョブが別のジョブからこの距離内にある場合、アルゴリズムはこれらのジョブを同じクラスターの一部と見なすことができます。このパラメーターに使用できる値の範囲は0～75です。maxDiameter：クラスター内にある任意の2つのジョブ間の最大許容距離 (メートル単位)。これにより、個々のジョブが互いに十分に近い場合でも、クラスターの直径が大きくなりすぎないようにします。このパラメーターに使用できる値の範囲は0～1000です。
詳細については、「APIリファレンス」を参照してください。
注
これは開発中のテスト段階の機能です。この機能を有効にするには、問題仕様で
clusterNearbyをexperimentalFeatures配列に追加します。詳細については、「テスト段階の機能の詳細」を参照してください。
問題：近隣の停車地をクラスタリングして配達の効率を上げる
前述の郵便サービスのユースケースをHERE Tour Planning APIで使用するには、次の問題のJSONをたたき台として検討していきます。
Click to expand/collapse the sample JSON
{
"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
}
}
}
],
"capacity": [
100
],
"amount": 10
}
],
"profiles": [
{
"type": "car",
"name": "car"
}
]
},
"plan": {
"jobs": [
{
"id": "Job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5615,
"lng": 13.4973
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5617,
"lng": 13.497
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.562,
"lng": 13.4975
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.56151,
"lng": 13.49791
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_5",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5618,
"lng": 13.4986
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5332,
"lng": 13.5197
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_7",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5207,
"lng": 13.5186
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_8",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5062,
"lng": 13.5094
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_9",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5063,
"lng": 13.5093
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
}
,
{
"id": "Job_10",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.506,
"lng": 13.5094
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
}
]
}
}前述の問題のソリューションは、次の主要なパラメーターを持つツアーを生成します。
- 停車地の数：
10 - 総所要時間：
2 h 28 m - 総走行距離：
26.56 km
次の図では、地理的に近いジョブがあるエリアが強調表示されており、クラスタリングによってさらに最適化する機会が提供されます。
このソリューションを近隣の停車地のクラスタリングを含むソリューションと比較するには、shift設定に次のstopConfigオブジェクトを追加します。
{
"stopConfig": {
"type": "dbscan",
"maxDistanceToNeighbor": 75,
"maxDiameter": 100
}
}この設定により、各停車地が、最も近い近隣の停車地から75メートル以内、クラスタリング可能な範囲内の最も遠い近隣の停車地から100メートル以内にある場合に、最適化アルゴリズムが各停車地をクラスタリングします。
注
clusterNearbyをexperimentalFeatures配列に必ず含めてください。
次のJSONは、クラスタリングするために更新された上の問題を示しています。
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
}
},
"stopConfig": {
"type": "dbscan",
"maxDistanceToNeighbor": 75,
"maxDiameter": 100
}
}
],
"capacity": [
100
],
"amount": 10
}
],
"profiles": [
{
"type": "car",
"name": "car"
}
]
},
"plan": {
"jobs": [
{
"id": "Job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5615,
"lng": 13.4973
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5617,
"lng": 13.497
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.562,
"lng": 13.4975
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5613,
"lng": 13.4978
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_5",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5618,
"lng": 13.4986
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5332,
"lng": 13.5197
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_7",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5207,
"lng": 13.5186
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_8",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5062,
"lng": 13.5094
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_9",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5063,
"lng": 13.5093
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
}
,
{
"id": "Job_10",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.506,
"lng": 13.5094
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
}
]
}
}ソリューション
clusterNearby機能を適用すると、ソリューションは次のパラメーターを持つツアーを生成します。
- 停車地の数：
7 - 総所要時間：
2 h 27 m 34 s - 総走行距離：
26.33 km - Intra-stop distance：
1.52 km- クラスター化された停車地内のアクティビティ間の総歩行距離
これらのパラメーター値は、クラスタリングの導入によって停車地の数が減少しただけでなく、ツアーの総合的な所要時間と距離の両方が減少したことを示しています。intraStopDistanceメトリックはクラスタリングのシナリオにおいて特に重要です。これは、郵便配達員がクラスター化されたすべての停車地内でアクティビティ間を移動する合計歩行距離と、各停車地で車両に戻る距離を定量化するからです。
次の図は、更新されたソリューションを図示したものです。
次のJSONは、完全なソリューションを示しています。
Click to expand/collapse the sample JSON
{
"statistic": {
"cost": 64.27000000000001,
"distance": 26333,
"duration": 8854,
"times": {
"driving": 2854,
"serving": 6000,
"waiting": 0,
"stopping": 0,
"break": 0,
"intraStop": 0
},
"intraStopDistance": 1515
},
"tours": [
{
"vehicleId": "small_9",
"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:41Z",
"departure": "2023-05-28T08:59:41Z"
},
"load": [
6
],
"activities": [
{
"jobId": "Job_4",
"type": "delivery",
"location": {
"lat": 52.5613,
"lng": 13.4978
},
"time": {
"start": "2023-05-28T08:19:41Z",
"end": "2023-05-28T08:29:41Z",
"arrival": "2023-05-28T08:19:41Z"
}
},
{
"jobId": "Job_3",
"type": "delivery",
"location": {
"lat": 52.562,
"lng": 13.4975
},
"time": {
"start": "2023-05-28T08:29:41Z",
"end": "2023-05-28T08:39:41Z",
"arrival": "2023-05-28T08:29:41Z"
}
},
{
"jobId": "Job_2",
"type": "delivery",
"location": {
"lat": 52.5617,
"lng": 13.497
},
"time": {
"start": "2023-05-28T08:39:41Z",
"end": "2023-05-28T08:49:41Z",
"arrival": "2023-05-28T08:39:41Z"
}
},
{
"jobId": "Job_1",
"type": "delivery",
"location": {
"lat": 52.5615,
"lng": 13.4973
},
"time": {
"start": "2023-05-28T08:49:41Z",
"end": "2023-05-28T08:59:41Z",
"arrival": "2023-05-28T08:49:41Z"
}
}
],
"location": {
"lat": 52.5613,
"lng": 13.4978
},
"distance": 9943,
"intraStopDistance": 1086
},
{
"time": {
"arrival": "2023-05-28T08:59:52Z",
"departure": "2023-05-28T09:09:52Z"
},
"load": [
5
],
"activities": [
{
"jobId": "Job_5",
"type": "delivery",
"location": {
"lat": 52.5618,
"lng": 13.4986
},
"time": {
"start": "2023-05-28T08:59:52Z",
"end": "2023-05-28T09:09:52Z",
"arrival": "2023-05-28T08:59:52Z"
}
}
],
"location": {
"lat": 52.5618,
"lng": 13.4986
},
"distance": 10015
},
{
"time": {
"arrival": "2023-05-28T09:16:37Z",
"departure": "2023-05-28T09:26:37Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_6",
"type": "delivery",
"location": {
"lat": 52.5332,
"lng": 13.5197
},
"time": {
"start": "2023-05-28T09:16:37Z",
"end": "2023-05-28T09:26:37Z",
"arrival": "2023-05-28T09:16:37Z"
}
}
],
"location": {
"lat": 52.5332,
"lng": 13.5197
},
"distance": 13817
},
{
"time": {
"arrival": "2023-05-28T09:29:22Z",
"departure": "2023-05-28T09:39:22Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Job_7",
"type": "delivery",
"location": {
"lat": 52.5207,
"lng": 13.5186
},
"time": {
"start": "2023-05-28T09:29:22Z",
"end": "2023-05-28T09:39:22Z",
"arrival": "2023-05-28T09:29:22Z"
}
}
],
"location": {
"lat": 52.5207,
"lng": 13.5186
},
"distance": 15355
},
{
"time": {
"arrival": "2023-05-28T09:43:27Z",
"departure": "2023-05-28T10:13:27Z"
},
"load": [
0
],
"activities": [
{
"jobId": "Job_10",
"type": "delivery",
"location": {
"lat": 52.506,
"lng": 13.5094
},
"time": {
"start": "2023-05-28T09:43:27Z",
"end": "2023-05-28T09:53:27Z",
"arrival": "2023-05-28T09:43:27Z"
}
},
{
"jobId": "Job_9",
"type": "delivery",
"location": {
"lat": 52.5063,
"lng": 13.5093
},
"time": {
"start": "2023-05-28T09:53:27Z",
"end": "2023-05-28T10:03:27Z",
"arrival": "2023-05-28T09:53:27Z"
}
},
{
"jobId": "Job_8",
"type": "delivery",
"location": {
"lat": 52.5062,
"lng": 13.5094
},
"time": {
"start": "2023-05-28T10:03:27Z",
"end": "2023-05-28T10:13:27Z",
"arrival": "2023-05-28T10:03:27Z"
}
}
],
"location": {
"lat": 52.506,
"lng": 13.5094
},
"distance": 17835,
"intraStopDistance": 429
},
{
"time": {
"arrival": "2023-05-28T10:27:34Z",
"departure": "2023-05-28T10:27:34Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 52.50935,
"lng": 13.41997
},
"time": {
"start": "2023-05-28T10:27:34Z",
"end": "2023-05-28T10:27:34Z",
"arrival": "2023-05-28T10:27:34Z"
}
}
],
"location": {
"lat": 52.50935,
"lng": 13.41997
},
"distance": 26333
}
],
"statistic": {
"cost": 64.27000000000001,
"distance": 26333,
"duration": 8854,
"times": {
"driving": 2854,
"serving": 6000,
"waiting": 0,
"stopping": 0,
"break": 0,
"intraStop": 0
},
"intraStopDistance": 1515
},
"shiftIndex": 0
}
]
}ソリューションを見ると、最適化アルゴリズムは近隣の停車地で2つのクラスターを特定しています。次のセクションでは、識別しやすいようにクラスター「A」とクラスター「B」と呼びます。
クラスター「A」
北側のクラスター (前の図では文字Aでマーク) は、stopConfigオブジェクトで指定されているクラスタリングの基準を満たす4つのジョブで構成されています。
Job_5 (停車地2) の場合、そのジョブは少なくとも1つの基準を満たしていないため、クラスターに含めることができません。次の距離測定が示すように、Job_5は、その停車地と最も遠い潜在的な近隣の停車地との間のmaxDiameterの上限である100メートルを超えています。
注
maxDistanceToNeighborおよびmaxDiameterパラメーターの両方の合計距離は、走行距離のみを考慮し、停車地間の歩行距離は含みません。
最適化アルゴリズムがクラスター内に停車地2を含めるようにするには、maxDistance制限値の100を102～1000の値に増やします。
クラスター「B」
南側のクラスター (ソリューションの図では文字Bでマーク) は、クラスタリングの導入により、結果のソリューションが大幅に更新されます。
停車地9と10は一方通行の道路沿いの角を曲がったところにあるため、クラスタリングのないソリューションでは、車両がこれらの停車地にサービスを提供するには一方通行の道路に沿って迂回する必要があります。ただし、最適化アルゴリズムがこれらの停車地をクラスタリングすると、車両は5と示されている停車地に駐車します。その後、郵便配達員は角を曲がったところにある停車地に徒歩で移動し、車両に戻り、より短いルートで配達を続けることができるため、燃料と時間の両方を節約できます。
停車地間の距離とアクティビティの順序付け
このソリューションには、クラスター化された各停車地内の歩行距離を定量化するintraStopDistance値が含まれています。Tour Planning APIでは、クラスター化されたすべての停車地についてintraStopDistanceを自動的に計算します。stopProfile (または非推奨のstopConfig.profile) が指定されている場合、APIはそのプロファイルを使用して距離を計算します。それ以外の場合は、メインの車両プロファイルがデフォルトで使用されます。
- クラスターA：
intraStopDistance: 1086メートル - 郵便配達員は、このクラスター内の4つの配達場所の間を合計約1.09 km歩き、さらに車両に戻ります。 - クラスターB：
intraStopDistance: 429メートル - 郵便配達員は、このクラスター内の3つの配達場所の間を合計約429メートル歩き、さらに車両に戻ります。 - 停車地間の総距離 (ソリューションの統計)：
1515メートル - ツアー全体のすべてのクラスター化された停車地の合計歩行距離。
これらのメトリックは、車両の走行距離を短縮することと、郵便配達員がクラスター化された配達に対応するために必要な徒歩での労力との間のトレードオフを理解するのに役立ちます。
**最適化されたアクティビティシーケンス：**各クラスター内のアクティビティの順序はランダムではなく、来た時と同じ道を引き返すのを避けることでintraStopDistanceを最小化するように最適化されています。最適化アルゴリズムによって、各クラスター内の配達ポイント間の最も効率的な徒歩ルートが決定されるため、郵便配達員は車両に戻る前に可能な限り最短の経路をたどることができます。
以下のサンプル問題は、ロンドンにある近隣の5つの配達場所を、徒歩による移動を最適化したアクティビティ順序付けによって、1つの停車地に集約する方法を示しています。
Click to expand/collapse the sample JSON
{
"configuration": {
"experimentalFeatures": [
"clusterNearby"
]
},
"fleet": {
"types": [
{
"id": "small",
"profile": "car",
"costs": {
"fixed": 0.001,
"distance": 8,
"time": 0.001
},
"speedFactor": 1,
"shifts": [
{
"start": {
"location": {
"lat": 51.545799,
"lng": -0.0814077
},
"time": "2024-06-24T08:00:00+02:00"
},
"end": {
"location": {
"lat": 51.545799,
"lng": -0.0814077
},
"time": "2024-06-24T20:00:00+02:00"
},
"stopConfig": {
"type": "dbscan",
"maxDistanceToNeighbor": 80,
"maxDiameter": 150,
"profile": "pedestrian"
}
}
],
"capacity": [
300
],
"amount": 1
}
],
"profiles": [
{
"name": "car",
"type": "car"
},
{
"name": "pedestrian",
"type": "pedestrian"
}
]
},
"plan": {
"jobs": [
{
"id": "1",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 51.54595,
"lng": -0.08352
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "2",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 51.54583,
"lng": -0.08388
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "3",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 51.54556,
"lng": -0.08388
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "4",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 51.54555,
"lng": -0.0834
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "5",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 51.5459,
"lng": -0.08317
}
}
],
"demand": [
1
]
}
]
}
}
]
}
}この問題をTour Planning APIに送信すると、5つのジョブすべてが近接性 (maxDistanceToNeighborである80メートル以内、maxDiameterである150メートル以内) によって1つの停車地にまとめられます。結果として得られたソリューション (簡潔にするために最小化されています) では、歩行に合わせて最適化されたアクティビティシーケンスと総歩行距離がハイライト表示されています。
{
"statistic": {
"cost": 3585.596,
"distance": 448,
"duration": 1595,
"intraStopDistance": 184
},
"tours": [
{
"vehicleId": "small_1",
"stops": [
{
"activities": [
{"jobId": "5", "type": "delivery"},
{"jobId": "4", "type": "delivery"},
{"jobId": "3", "type": "delivery"},
{"jobId": "2", "type": "delivery"},
{"jobId": "1", "type": "delivery"}
],
"intraStopDistance": 184
}
]
}
]
}最適化されたアクティビティシーケンス (5→4→3→2→1) は、配達場所間の逆戻りを避けることで、intraStopDistanceである184メートルを最小化します。この距離には、駐車場所から最初の配達先までの徒歩移動、すべての配達先間の徒歩移動、そして駐車場所に戻るまでの徒歩移動が含まれています。
次の図は、前の例に基づいて、クラスター内の停車地を徒歩に合わせて最適化した順序付けを示しています。
注
最適化アルゴリズムにおいて、
intraStopDistanceの最適化は最も優先順位が低くなっています。時間枠などの他の制約を歩行距離の最適化よりも優先すると、これらの制約を満たすために必要な場合には、最適ではない歩行順序になる可能性があります。
結論
このチュートリアルでは、HERE Tour Planning APIにclusterNearbyフィーチャーを組み込んでそのメリットを活用する方法について説明しました。問題の例では、このフィーチャーを紹介し、その利点を示しました。
- 最適化されたルート計画でビジネスニーズに合わせてクラスターサイズを調整できる柔軟性。
- 特に一方通行の道路を含むシナリオで、迂回を減らし、燃料を節約し、移動時間を最小限に抑えるクラスタリング機能。
次のステップ
26 日前の更新