このガイドでは、Azure Maps と NVIDIA cuOpt を使用して、旅程の最適化サービスを作成する方法について説明します。 このサービスは、NVIDIA cuOpt ルート最適化エンジンを利用して複数の目的地にわたるルートを最適化し、複数のエージェントと混合フリートの旅程を構築するプロセスを自動化します。
これは 2 段階のプロセスで行われ、移動時間のコスト マトリックスと、問題を最適化して結果を生成するためのソルバーを必要とします。 コスト マトリックスは、問題におけるあらゆる 2 地点間の移動コストを表します。これには、移動時間のコストとその他の移動コストが含まれます。
この記事では、次の方法について説明します。
- Azure Marketplace で NVIDIA cuOpt の使用を開始する。
- Azure Maps Route Matrix API を使用して移動コストを計算する。
- cuOpt API 呼び出しに問題をマッピングする方法。
- cuOpt 応答を使用する方法。
- ルート検索のために Azure Maps Route Directions API を呼び出す。
手早く開始するには、複数旅程の最適化コード サンプルを参照してください。
前提条件
- Azure Maps アカウント
- サブスクリプション キー、またはその他の形式の Azure Maps での認証
サービスのサポート
このサービスでは、以下の機能と制約をサポートできます。
| ルート最適化機能 | サポート対象? |
|---|---|
| トラックと自動車 | はい |
| 複数旅程 | はい |
| 複数のドライバー | はい |
| 複数の日 | はい |
| フリートの混在 | はい |
| 車両の運行時間枠 | はい |
| 時間制限 | はい |
| 優先順位 | はい |
| エージェントの休憩 | はい |
| ピックアップ配送 | はい |
| 車両あたりのコスト | はい |
| 車両の最小および最大数 | はい |
サポートされている機能の全リストについては、cuOpt のサポート対象機能をご覧ください。
Azure Marketplace で NVIDIA cuOpt の使用を開始する
NVIDIA cuOpt は、GPU 高速ロジスティクス ソルバーと最適化機能を使用して、幅広い制約のある複雑な車両ルーティングの問題を計算します。 詳細については、cuOpt でサポートされる機能一覧をご覧ください。
cuOpt は NVIDIA AI Enterprise に含まれています。 利用開始するには、Azure Marketplace をご覧ください。
移動コストを計算する
スケジュールの最適化には、cuOpt ソルバーに渡される移動メトリック (時間コストや距離コストなど) の正方形のマトリックスが必要です。 コスト マトリックスは、問題セット内のすべての場所のペア間の移動コストを表し、効率的なルート計画と最適化を可能にします。
Azure Maps Route Matrix API は、各出発地からすべての目的地までの時間や距離などの移動メトリックを計算します。 これらの起点と宛先は、コスト マトリックスの列ヘッダーと行ヘッダーを形成します。各セルは、特定の出発地と宛先のペア間のルーティング コストを表します。
たとえば、レストランには、4 つの場所に食べ物を配達する必要がある 2 人のドライバーがいます。 このシナリオを解決するには、Route Matrix API を使用して、関連するすべてのポイント間の移動時間を計算します。 この例では、ドライバーの両方がレストランで開始および終了することを前提としています。 開始または終了の場所がデポと異なる場合は、それらの場所をコスト マトリックスに明示的に含める必要があります。
出発地の数 = 目的地の数 = 1 (レストラン、 デポとも呼ばれます) + 4 (配送先) = 5
マトリックスのサイズ = 5 つの出発点 x 5 つの目的地 = 25
注
Azure Maps Route Matrix では、非同期要求用に最大 50,000 個のマトリックス セル、同期要求用に 2,500 個のマトリックス セルをサポートできます。これは、それぞれ 223 x 223 と 50 x 50 の正方形のマトリックスに近似します。 これを使用して、デポや配送を含む最大 223 の場所の旅程を計画できます。
Route Matrix の POST 要求:
https://atlas.microsoft.com/route/matrix?api-version=2025-01-01&routeType=shortest&subscription-key={Your-Azure-Maps-Subscription-key}
{
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"geometry": {
"type": "MultiPoint",
"coordinates": [
[4.85106, 52.36006], //restaurant or depot
[4.85056, 52.36187], //delivery location 1
[4.85003, 52.36241], //delivery location 2
[4.42937, 52.50931], //delivery location 3
[4.42940, 52.50843] //delivery location 4
]
},
"properties": {
"pointType": "origins"
}
},
{
"type": "Feature",
"geometry": {
"type": "MultiPoint",
"coordinates": [
[4.85106, 52.36006], //restaurant or depot
[4.85056, 52.36187], //delivery location 1
[4.85003, 52.36241], //delivery location 2
[4.42937, 52.50931], //delivery location 3
[4.42940, 52.50843] //delivery location 4
]
},
"properties": {
"pointType": "destinations"
}
}
]
}
Route Matrix の応答は、各行が出発地を、列が目的地を表す 5 x 5 の多次元配列を返します。 各 2 地点間の時間コストを取得するには、フィールド travelTimeInSeconds を使用します。 時間の単位は、ソリューション全体で一貫している必要があります。 前処理ステージが完了すると、注文、デポ、フリート情報、コスト マトリックスが送信され、API 呼び出しを介して cuOpt Server にインポートされます。
次の JSON サンプルは、サンプルのコスト マトリックスに対する HTTP 応答の本文で返される内容を示しています。
cost_matrix_data = [
[ 0, 10, 8, 6, 10],
[10, 0, 12, 8, 6],
[ 8, 16, 0, 8, 4],
[ 2, 8, 6, 0, 8],
[ 6, 6, 10, 12, 0],
]
注
ある場所から同じ場所に移動するコストは通常 0 であり、場所 A から場所 B に移動するコストは、必ずしも場所 B から場所 A に移動するコストと等しいとは限りません。
問題を cuOpt API 呼び出しにマッピングする
このセクションでは、cuOpt 呼び出しの要求データを作成する方法について説明します。 その他の例については、cuOpt のベスト プラクティスをご覧ください。
コスト マトリックスを設定する
Azure Maps の Route Matrix API の応答を解析し、地点間の移動時間を取得してコスト マトリックスを作成します。 次の例では、"0" は特定の車両の種類を表すキーを表します。
"data": {" cost_matrix_data ": {
"data": {
"0": [
[0, 5, 4, 3, 5],
[5, 0, 6, 4, 3],
[4, 8, 0, 4, 2],
[1, 4, 3, 0, 4],
[3, 3, 5, 6, 0]
]
}}}
車両の種類に応じて、任意で複数のコスト マトリックスを指定できます。 車両の中には、より速く移動できるものもある一方、特定のエリアを移動する際にコストがかさむ可能性があるものもあります。 車両の種類ごとに 1 つずつ、複数のコスト マトリックスを使用すると、これをモデル化できます。 次の例には 2 つのマトリックスがあり、"0" は最初の車両を表し、"1" は 2 台目の車両を表し、トラックを表します。 フリートにある車両のプロファイルが類似している場合、コスト マトリックスを指定する必要があるのは 1 回だけです。
"data": {" cost_matrix_data ": {
"data": {
"0": [
[0, 5, 4, 3, 5],
[5, 0, 6, 4, 3],
[4, 8, 0, 4, 2],
[1, 4, 3, 0, 4],
[3, 3, 5, 6, 0]
],
"1": [
[0, 4, 2, 3, 3],
[2, 0, 6, 5, 3],
[3, 8, 0, 3, 2],
[1, 5, 3, 0, 4],
[3, 4, 5, 7, 0]
],
}}}
フリート データを設定する
車両データには、車両の数、それらの出発地と到着地、車両の容量など、車両の説明を記述できます。これらの情報は、制約内でタスクを実行するために利用できる車両を決定するためにソルバーによって使用されます。
{
"fleet_data": {
"vehicle_locations": [
[0,1], [0,1]
],
"capacities": [[2,3]],
"vehicle_time_windows": [
[0, 80],
[1, 40]
],
"vehicle_break_time_windows":[
[
[20, 25],
[20, 25]
]
],
"vehicle_break_durations": [[1, 1, 1, 1, 1]]
}
}
- 車両の場所: 上記の例では、フリート データによると 2 台の車両があり、各車両に 1 つの配列があります。 両方の車両が場所 0 から出発し、場所 1 で移動を終了します。 環境のコスト マトリックスの説明のコンテキストでは、これらの車両の場所は、コスト マトリックスの行 (または列) インデックスに対応しています。
- 容量: 容量配列は車両の容量を示します。最初の車両の容量は 2、2 番目の車両の容量は 3 です。 容量は、荷物の重量、サービス スキル、各車両による輸送量など、さまざまなものを表す可能性があります。 次のセクションでは、タスクの場所ごとに需要ディメンションを必要とするタスク JSON を作成します。需要ディメンションの数は、フリート データ内の容量ディメンションの数に対応します。 たとえば、トラックが商品を配送する場合、容量は、各車両が運ぶことができる合計重量になり、需要は各注文の重量になります。 必ず、両方に同じ単位 (ポンドやキログラムなど) を使用します。
- 車両の時間枠: 時間枠は、タスクを実行する車両の運行時間を指定します。 これは、エージェントのシフトの開始時刻と終了時刻である可能性があります。 生データには、ユニバーサル タイム スタンプ (UTC) の日付/時刻形式、または文字列形式を含めることができ、これは浮動小数点値に変換する必要があります。 (例: 午前 9 時 - 午後 6 時を、午前 12 時から始まる 24 時間の分単位に換算すると、[540, 1080] になります)。 cuOpt ソルバーに渡されるすべての時間/コストの単位は、同じ単位である必要があります。
- 車両の休憩: 車両の休憩時間と長さも指定できます。 これは、エージェントの昼休み、または必要に応じて他の休憩を表します。 休憩時間の形式は、車両の時間枠の形式と同じです。 cuOpt ソルバーに渡されるすべての時間/コストの単位は、同じ単位である必要があります。
タスク データを設定する
タスクでは、制約内で達成する必要がある目標を定義します。 ラスト マイル配送のコンテキストでは、配送場所、各場所における需要量、各場所の配送可能時間と滞留時間が含まれます。
"task_data": {
"task_locations": [1, 2, 3, 4],
"demand": [[3, 4, 4, 3]],
"task_time_windows": [[8, 17], [8, 17], [8, 17], [17, 20]],
"service_times": [0, 0, 0, 0]
}
- タスクの場所: 上記の例では、task_locations は 1、2、3、4 の位置にある配送先を示しています。 これらの場所は、コスト マトリックスの行 (または列) インデックスに対応します。
- 需要: 需要配列は、各場所における需要量を示します。最初の場所の需要は 3、2 番目と 3 番目の場所では 4、最後の場所では 3 となっています。 需要ディメンションの数は、各車両の容量ディメンションの数に対応している必要があります。
- タスクの時間枠: 時間枠の制約は、タスクをいつ完了する必要があるかを指定します。 各タスクに開始および終了の時間枠が割り当てられ、タスクはその時間内に完了する必要があります。 生データには、ユニバーサル タイム スタンプ (UTC) の日付/時刻形式、または文字列形式を含めることができ、これは浮動小数点値に変換する必要があります。 (例: 午前 9 時 - 午後 6 時を、午前 12 時から始まる 24 時間の分単位に換算すると、[540, 1080] になります)。 cuOpt ソルバーに渡されるすべての時間/コストの単位は、同じ単位である必要があります。
- サービス時間: タスクを完了するために必要な時間を表します。 service_times 配列は、各タスクの場所における時間を指定します。 cuOpt ソルバーに渡されるすべての時間/コストの単位は、同じ単位である必要があります。
ソルバー構成を設定する (省略可能)
必要に応じて、ソルバーの構成で解決までの最大時間を設定することもできます。 これはユース ケースによって異なり、制限時間を長く設定した方が良い結果が得られます。
"solver_config": {
"time_limit": 1
}
注
注文の優先順位や車両コストなど、問題によって追加の制約がある場合があります。cuOpt でサポートされている機能をご覧ください。 その他の機能は、例で説明している機能と同様に前処理されます。
cuOpt 応答を利用する方法
cuOpt ソルバーは、各車両の最適化された停止位置と旅程を返します。 Azure Maps Route Directions API を呼び出してルートを取得する前に、応答を解析し、各場所を座標ポイントに変換してください。 これらの最適化されたルートには、各エージェントのルート経路と運転案内が含まれます。
要求データの例
{
"requestBody": {
"data": {"cost_matrix_data": {"data": {"1": [[0, 5, 4, 3, 5], [5, 0, 6, 4, 3], [4, 8, 0, 4, 2], [1, 4, 3, 0, 4], [3, 3, 5, 6, 0]]}},
"fleet_data": {
"vehicle_locations": [[0, 0], [0, 0]],
"vehicle_ids": ["Car-A", "Car-B"],
"vehicle_types": [1, 1],
"capacities": [[75, 75]],
"vehicle_time_windows": [[8, 18], [8, 17]],
"vehicle_break_time_windows": [[[12, 14], [12, 14]]],
"vehicle_break_durations": [[0, 0]]
},
"task_data": {
"task_locations": [1, 2, 3, 4],
"demand": [[30, 40, 40, 30]],
"task_time_windows": [[8, 17], [8, 17], [8, 17], [17, 15]],
"service_times": [0, 0, 0, 0]
},
"solver_config": {
"time_limit": 1
}},
"client_version": ""
}
}
サンプル応答
"reqId": "4bdc2610-d821-48dc-b53f-57698015bb2e",
"status": "fulfilled",
"percentComplete": 100,
"response": {
"response": {
"solver_response": {
"status": 0,
"num_vehicles": 2,
"solution_cost": 19.0,
"vehicle_data": {
"Car-A": {
"task_id": [
"Depot",
"Break",
"0",
"2",
"Depot"
],
"arrival_stamp": [
8.0,
13.0,
13.0,
17.0,
18.0
],
"route": [
0,
1,
1,
3,
0
],
"type": [
"Depot",
"Break",
"Delivery",
"Delivery",
"Depot"
]
},
"Car-B": {
"task_id": [
"Depot",
"Break",
"1",
"3",
"Depot"
],
"arrival_stamp": [
8.0,
12.0,
12.0,
14.0,
17.0
],
"route": [
0,
2,
2,
4,
0
],
"type": [
"Depot",
"Break",
"Delivery",
"Delivery",
"Depot"
]
}
},
"msg": ""
}
}
}
}
ルート検索のために Azure Maps Route Directions API を呼び出す
cuOpt 応答内の場所が対応する座標にマップされた後、cuOpt サービスを Azure Maps Route Directions API および Web SDK と共に使用して、割り当てられた旅程と最適化されたルートをマップに表示する Web アプリを作成できます。 割り当てられた停止位置に基づいて個々の車両のルート経路を色分けし、Azure Maps の基本データに表示することができます。
