Hinweis
Für den Zugriff auf diese Seite ist eine Autorisierung erforderlich. Sie können versuchen, sich anzumelden oder das Verzeichnis zu wechseln.
Für den Zugriff auf diese Seite ist eine Autorisierung erforderlich. Sie können versuchen, das Verzeichnis zu wechseln.
In dieser Anleitung wir erklärt, wie Sie Azure Maps und NVIDIA cuOpt verwenden, um einen Routenoptimierungsdienst zu erstellen. Dieser Dienst automatisiert die Erstellung von Strecken für mehrere Agenten und gemischte Flotten und nutzt die NVIDIA cuOpt-Routenoptimierungs-Engine zur Optimierung von Routen über mehrere Ziele hinweg.
Dabei handelt es sich um einen Prozess mit zwei Schritten, der eine Kostenmatrix für die Reisezeit und einen Solver erfordert, um die Berechnung zu optimieren und ein Ergebnis zu generieren. Eine Kostenmatrix stellt die Reisekosten zwischen den beiden Standorten der Berechnung dar. Sie schließt die Kosten für die Reisezeit sowie weitere Reisekosten ein.
Dieser Artikel beschreibt, wie Sie:
- Erste Schritte mit NVIDIA cuOpt im Azure Marketplace
- Verwenden der Routenmatrix-API von Azure Maps zum Abrufen der Reisekosten
- Zuordnen der Berechnung zu cuOpt-API-Aufrufen
- Verwenden der cuOpt-Antwort
- Aufrufen der Wegbeschreibungs-API von Azure Maps zur Routenplanung
Weitere Informationen für einen Schnellstart finden Sie im Codebeispiel Optimierung für mehrere Routen.
Voraussetzungen
- Ein Azure Maps-Konto
- Ein Abonnementschlüssel oder eine andere Form der Authentifizierung bei Azure Maps
Dienstunterstützung
Dieser Dienst bietet Unterstützung für die folgenden Features und weist die folgenden Einschränkungen auf.
| Funktionen zur Routenoptimierung | Unterstützt? |
|---|---|
| Lkw und Pkw | Ja. |
| Mehrere Routen | Ja. |
| Mehrere Fahrer | Ja. |
| Mehrere Tage | Ja. |
| Gemischte Flotte | Ja. |
| Zeitfenster für Fahrzeuge | Ja. |
| Zeitlimits | Ja. |
| Priorität | Ja. |
| Mitarbeiterpausen | Ja. |
| Lieferungen mit Abholung | Ja. |
| Kosten pro Fahrzeug | Ja. |
| Mindest- und Höchstanzahl der Fahrzeuge | Ja |
Die vollständige Liste der unterstützten Funktionen finden Sie unter Features mit cuOpt-Unterstützung.
Erste Schritte mit NVIDIA cuOpt im Azure Marketplace
NVIDIA cuOpt verwendet GPU-beschleunigte Logistiksolver und Optimierungen für komplexe Berechnungen bei der Routenplanung für Fahrzeuge mit einer Vielzahl von Einschränkungen. Weitere Informationen finden Sie in der Liste der unterstützten cuOpt-Features.
cuOpt ist in NVIDIA AI Enterprise enthalten. Besuchen Sie den Azure Marketplace, um zu beginnen.
Abrufen der Reisekosten
Die Routenoptimierung erfordert die quadratische Matrix einiger Reisemetriken, die an den cuOpt-Solver übergeben wird. Diese könnte die Kosten für die Reisezeit oder Reiseentfernung umfassen. Eine Kostenmatrix ist eine quadratische Matrix, die die Kosten für das Reisen zwischen jedem Standortpaar der Berechnung darstellt.
Die Routenmatrix-API von Azure Maps berechnet die Kosten für die Zeit und Entfernung der Routenplanung vom jeweiligen Startpunkt zum jeweiligen Zielpunkt. Die Start- und Zielpunkte können als Spalten- und Zeilenüberschriften einer Tabelle betrachtet werden, und jede Zelle in der Tabelle enthält die Kosten für die Strecke zwischen dem Start- und Zielpunkt für diese Zelle.
Beispiel: Ein Restaurant hat zwei Fahrer, die Lebensmittel an vier Standorte liefern müssen. Um diesen Fall zu lösen, rufen Sie zur Berechnung die Routenmatrix-API auf, um die Reisezeiten zwischen allen Standorten abzurufen. In diesem Beispiel wird davon ausgegangen, dass das Restaurant den Start- und Zielstandort für die Fahrer darstellt. Wenn sich die Start- und Zielstandorte vom Lager unterscheiden, müssen diese in die Kostenmatrizen einbezogen werden.
Anzahl der Startpunkte = Anzahl der Zielpunkte = 1 (Restaurant, auch als Lager bezeichnet) + 4 (Lieferungen)
Matrixgröße = 5 Startpunkte × 5 Zielpunkte = 25
Hinweis
Die Routenmatrix von Azure Maps kann bis zu 700 Matrixzellen unterstützen, die einer quadratischen Matrix von 26 × 26 entsprechen. Diese können Sie verwenden, um die Route für 26 Standorte einschließlich Lager- und Lieferstandorten zu planen.
POST-Anforderung der Routenmatrix:
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"
}
}
]
}
Die Antwort der Routenmatrix gibt ein mehrdimensionales 5 × 5-Array zurück. In diesem stellt jede Zeile die Startpunkte dar, und die Spalten stellen die Ziele dar. Verwenden Sie das Feld travelTimeInSeconds, um den Zeitaufwand für jedes Standortpaar abzurufen. Die Zeiteinheit sollte in der gesamten Lösung konsistent sein. Sobald die Vorverarbeitungsphase abgeschlossen ist, werden die Bestellung, das Lager, die Flotteninformationen und die Kostenmatrix über API-Aufrufe an den cuOpt-Server gesendet und in diesen importiert.
Das folgende JSON-Beispiel veranschaulicht, was im Textkörper der HTTP-Antwort des Kostenmatrixbeispiels zurückgegeben wird:
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],
]
Hinweis
Die Kosten für die Strecke von einem Standort zum selben Standort betragen in der Regel 0, und die Kosten für die Strecke von Standort A zu Standort B entsprechen nicht zwingend den Kosten für die Strecke von Standort B zu Standort A.
Zuordnen der Berechnung zu cuOpt-API-Aufrufen
In diesem Abschnitt wird beschrieben, wie Anforderungsdaten für cuOpt-Aufrufe erstellt werden. Weitere Beispiele finden Sie unter Best Practices von cuOpt.
- Festlegen der Kostenmatrix
- Festlegen der Flottendaten
- Festlegen der Aufgabedaten
- Festlegen der Solverkonfiguration (optional)
Festlegen der Kostenmatrix
Parsen Sie die Antwort der Routenmatrix-API von Azure Maps, um die Reisezeit zwischen Standorten abzurufen und damit die Kostenmatrix zu erstellen. Im folgenden Beispiel stellt „0“ den Schlüssel für einen bestimmten Fahrzeugtyp dar.
"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]
]
}}}
Abhängig von den Fahrzeugtypen können optional mehrere Kostenmatrizen bereitgestellt werden. Einige Fahrzeuge können schneller fahren, wohingegen andere möglicherweise weitere Kosten verursachen, wenn sie durch bestimmte Gebiete fahren. Hierfür kann ein Modell mit weiteren Kostenmatrizen erstellt werden, wobei eine Kostenmatrix jeweils einen Fahrzeugtyp darstellt. Das nächste Beispiel weist zwei Matrizen auf: „0“ stellt das erste Fahrzeug dar, das ein Pkw sein könnte, und „1“ stellt ein zweites Fahrzeug dar, das ein Lkw sein könnte. Hinweis: Wenn Ihre Flotte Fahrzeuge mit ähnlichen Profilen enthält, müssen Sie die Kostenmatrix nur einmal festlegen.
"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]
],
}}}
Festlegen der Flottendaten
Flottendaten könnten unter anderem Folgendes beschreiben: die Anzahl der Fahrzeuge, ihren Start- und Zielstandort und die Fahrzeugkapazität. Diese Flottenbeschreibung wird vom Solver verwendet, um zu bestimmen, welche Fahrzeuge zum Ausführen der Aufgabe unter Berücksichtigung der Einschränkungen verfügbar sind.
{
"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]]
}
}
- Fahrzeugstandorte: Im obigen Beispiel geben die Flottendaten zwei Fahrzeuge an, wobei jedes Fahrzeug durch ein Array dargestellt wird. Beide Fahrzeuge beginnen an Standort 0 und schließen die Fahrt an Standort 1 ab. Im Kontext der Umgebungsbeschreibung einer Kostenmatrix entsprechen diese Fahrzeugstandorte Zeilen- oder Spaltenindizes in der Kostenmatrix.
- Kapazitäten: Das Kapazitätsarray gibt die Fahrzeugkapazität an. Das erste Fahrzeug verfügt über eine Kapazität von 2, und das zweite Fahrzeug verfügt über eine Kapazität von 3. Die Kapazität könnte beispielsweise Folgendes darstellen: Paketgewicht, Dienstleistungsfähigkeiten und die Mengen, die von jedem Fahrzeug transportiert werden. Im nächsten Abschnitt erstellen Sie einen Aufgaben-JSON-Code, der eine Anforderungsdimension für jeden Aufgabenstandort erfordert, und die Anzahl der Bedarfsdimensionen entspricht der Anzahl der Kapazitätsabmessungen in den Flottendaten. Wenn beispielsweise ein LKW Waren ausliefert, wäre die Kapazität das Gesamtgewicht, das jedes Fahrzeug transportieren kann, und der Bedarf das Gewicht der einzelnen Bestellungen. Stellen Sie sicher, dass für beide die gleiche Einheit verwendet wird (z. B. Pfund oder Kilogramm).
- Fahrzeugzeitfenster: Zeitfenster geben die Betriebszeit an, die das Fahrzeug benötigt, um die Aufgaben auszuführen. Das könnten die Zeiten des Schichtbeginns und -endes des Mitarbeiters sein. Rohdaten können das UTC-Datumsformat bzw. das UTC-Uhrzeitformat (Universal Time Stamp) oder das Zeichenfolgenformat einschließen, das in Gleitkommawerte konvertiert werden muss. (Beispiel: Die Konvertierung von 09:00–18:00 Uhr in Minuten für einen Zeitraum von 24 Stunden, der um 00:00 Uhr beginnt, wäre [540, 1080].) Alle Zeit- bzw. Kosteneinheiten, die dem cuOpt-Solver bereitgestellt werden, sollten in derselben Einheit angegeben werden.
- Fahrzeugpausen: Die Zeitfenster und die Dauer von Fahrzeugpausen können ebenfalls festgelegt werden. Diese könnten die Mittagspause des Mitarbeiters oder ggf. andere Pausen darstellen. Das Format des Zeitfensters für Pausen entspricht dem des Fahrzeugs. Alle Zeit- bzw. Kosteneinheiten, die dem cuOpt-Solver bereitgestellt werden, sollten in derselben Einheit angegeben werden.
Festlegen der Aufgabedaten
Aufgaben definieren das Ziel, das innerhalb der Einschränkungen erreicht werden muss. Im Kontext von Letzte-Meile-Lieferungen könnte das Folgendes einschließen: die Lieferorte, die Bedarfsmenge an jedem Standort, das Lieferfenster und die Aufenthaltszeit an jedem Standort.
"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]
}
- Aufgabenstandort: Im obigen Beispiel gibt task_locations den Lieferort an den Positionen 1, 2, 3 und 4 an. Diese Positionen entsprechen Zeilen- oder Spaltenindizes in der Kostenmatrix.
- Bedarf: Das Bedarfsarray gibt die Bedarfsmenge an jedem Standort an. Der erste Standort weist einen Bedarf von 3 auf, der zweite und dritte Standort einen Bedarf von 4 und der letzte Standort einen Bedarf von 3. Die Anzahl der Bedarfsdimensionen sollte bei jedem Fahrzeug der Anzahl der Kapazitätsdimensionen entsprechen.
- Aufgabenzeitfenster: Die Einschränkungen für Zeitfenster geben an, wann eine Aufgabe abgeschlossen werden sollte. Jeder Aufgabe wird ein Zeitfenster für den Beginn und Abschluss zugewiesen, und die Aufgabe muss innerhalb dieses Zeitfensters abgeschlossen werden. Rohdaten können das UTC-Datumsformat bzw. das UTC-Uhrzeitformat (Universal Time Stamp) oder das Zeichenfolgenformat einschließen, das in Gleitkommawerte konvertiert werden muss. (Beispiel: Die Konvertierung von 09:00–18:00 Uhr in Minuten für einen Zeitraum von 24 Stunden, der um 00:00 Uhr beginnt, wäre [540, 1080].) Alle Zeit- bzw. Kosteneinheiten, die dem cuOpt-Solver bereitgestellt werden, sollten in derselben Einheit angegeben werden.
- Dienstleistungszeiten: Hierdurch wird die Dauer dargestellt, die zum Ausführen der Aufgaben benötigt wird. Das Array service_times gibt die Zeitdauer für jeden Aufgabenstandort an. Alle Zeit- bzw. Kosteneinheiten, die dem cuOpt-Solver bereitgestellt werden, sollten in derselben Einheit angegeben werden.
Festlegen der Solverkonfiguration (optional)
Optional können Sie die Solverkonfiguration so festlegen, dass sie der Lösungsfindung eine maximale Dauer zuteilt. Das hängt vom Anwendungsfall ab, und das Festlegen eines höheren Zeitlimits führt zu besseren Ergebnissen.
"solver_config": {
"time_limit": 1
}
Hinweis
Je nach Berechnung gelten möglicherweise zusätzliche Einschränkungen wie Auftragsprioritäten oder Fahrzeugkosten. Weitere Informationen finden Sie in der Liste der unterstützten cuOpt-Features. Andere Features würden auf ähnliche Weise wie die in den Beispielen behandelten Features vorverarbeitet werden.
Verwenden der cuOpt-Antwort
Der cuOpt-Solver gibt den optimierten Halt für jedes Fahrzeug und die Reiseroute zurück. Parsen Sie die Antwort, und konvertieren Sie jeden Standort in einen Koordinatenpunkt, bevor Sie die Wegbeschreibungs-API von Azure Maps aufrufen, um die Routen abzurufen. Diese optimierten Routen schließen den Routenpfad und die Wegbeschreibungen für jeden Mitarbeiter ein.
Beispielanforderungsdaten
{
"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": ""
}
}
Beispiel für eine Antwort
"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": ""
}
}
}
}
Aufrufen der Wegbeschreibungs-API von Azure Maps zur Routenplanung
Nachdem die Standorte in der cuOpt-Antwort den entsprechenden Koordinaten zugeordnet wurden, kann der cuOpt-Dienst mit der Azure Maps Route Directions API und dem Web SDK verwendet werden, um eine Web-App zu erstellen, die die zugewiesenen Reiserouten und optimierten Routen auf der Karte anzeigt. Sie können den Routenpfad für einzelne Fahrzeuge basierend auf den zugewiesenen Halteorten farblich kennzeichnen und in den Basisdaten von Azure Maps anzeigen.
