Tworzenie usługi optymalizacji obejmującej wiele tras

W tym przewodniku wyjaśniono, jak używać usług Azure Maps i NVIDIA cuOpt w celu utworzenia usługi optymalizacji trasy. Ta usługa automatyzuje proces tworzenia tras dla wielu agentów i mieszanych flot przy użyciu aparatu optymalizacji tras firmy NVIDIA w celu optymalizacji tras w wielu miejscach docelowych.

Jest to proces dwuetapowy, który wymaga macierzy kosztów dla czasu podróży i modułu rozwiązywania w celu optymalizacji problemu i wygenerowania wyniku. Macierz kosztów reprezentuje koszt podróży między każdym dwoma zestawami lokalizacji w problemie, który obejmuje koszt podróży i inne koszty podróży.

W tym artykule opisano sposób wykonywania następujących czynności:

• Rozpocznij pracę z narzędziem NVIDIA cuOpt w witrynie Azure Marketplace.
• Użyj interfejsu API macierzy tras usługi Azure Maps, aby uzyskać koszt podróży.
• Jak zamapować problem na cuOpt wywołań interfejsu API.
• Jak użyć odpowiedzi cuOpt.
• Wywołaj interfejs API wskazówek tras w usłudze Azure Maps na potrzeby routingu.

Skorzystaj z przykładu kodu Optymalizacji Wielu Tras aby szybko rozpocząć pracę.

Wymagania wstępne

• Konto usługi Azure Maps
• Klucz subskrypcji lub inna forma uwierzytelniania za pomocą usługi Azure Maps

Obsługa usługi

Ta usługa może obsługiwać następujące funkcje i ograniczenia.

Aby uzyskać pełną listę obsługiwanych funkcji, zobacz cuOpt Supported Features (Obsługiwane funkcje).

Wprowadzenie do narzędzia NVIDIA cuOpt w witrynie Azure Marketplace

NVIDIA cuOpt używa przyspieszanego przez procesor graficzny rozwiązania logistycznego i optymalizacji przy użyciu GPU do obliczania złożonych problemów z trasowaniem pojazdów z dużą liczbą ograniczeń. Aby uzyskać więcej informacji, zobacz listę obsługiwanych funkcji cuOpt.

CuOpt jest dołączony do firmy NVIDIA AI Enterprise. Odwiedź witrynę Azure Marketplace , aby rozpocząć pracę.

Uzyskaj koszt podróży

Optymalizacja trasy wymaga kwadratowej macierzy metryki podróży, takiej jak koszt czasu lub odległości, która jest przekazywana do solvera cuOpt. Macierz kosztów reprezentuje koszt podróży między każdą parą lokalizacji w zestawie problemów, umożliwiając efektywne planowanie i optymalizację tras.

Interfejs API macierzy tras usługi Azure Maps oblicza metryki podróży, takie jak czas i odległość, od każdego źródła do każdego miejsca docelowego. Te źródła i miejsca docelowe tworzą kolumny i nagłówki wierszy macierzy kosztów, w której każda komórka reprezentuje koszt routingu między określoną parą źródło-docelowa.

Na przykład restauracja ma dwóch kierowców, którzy muszą dostarczać jedzenie do czterech lokalizacji. Aby rozwiązać ten scenariusz, użyj interfejsu API macierzy tras, aby obliczyć czas podróży między wszystkimi odpowiednimi punktami. W tym przykładzie przyjęto założenie, że obaj kierowcy zaczynają i kończą trasę w restauracji. Jeśli lokalizacje początkowe lub końcowe różnią się od magazynu, te lokalizacje muszą być jawnie uwzględnione w macierzy kosztów.

Liczba źródeł = liczba miejsc docelowych = 1 (restauracja, nazywana również magazynem) + 4 (lokalizacje dostawy) = 5

Rozmiar macierzy = 5 źródeł x 5 miejsc docelowych = 25

Żądanie typu POST dla macierzy tras

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"
      }
    }
  ]
}

Odpowiedź macierzy tras zwraca tablicę wielowymiarową 5x5, w której każdy wiersz reprezentuje źródła i kolumny reprezentują miejsca docelowe. Użyj pola travelTimeInSeconds , aby uzyskać koszt czasu dla każdej pary lokalizacji. Jednostka czasu powinna być spójna w całym rozwiązaniu. Po zakończeniu etapu przetwarzania wstępnego kolejność, magazyn, informacje o flocie i macierz kosztów są wysyłane i importowane do serwera cuOpt za pośrednictwem wywołań interfejsu API.

Poniższy przykład JSON pokazuje, co jest zwracane w treści odpowiedzi HTTP przykładu macierzy kosztów:

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], 
] 

Przypisz problem do wywołań API cuOpt

W tej sekcji opisano sposób tworzenia danych żądania dla wywołań cuOpt. Aby uzyskać więcej przykładów, zobacz cuOpt best practices (Najlepsze rozwiązania).

1. Ustaw macierz kosztów
2. Ustawianie danych floty
3. Ustaw dane zadania
4. Ustawianie konfiguracji programu Solver (opcjonalnie)

Ustaw macierz kosztów

Przeanalizuj odpowiedź interfejsu API macierzy tras usługi Azure Maps, aby uzyskać czas podróży między lokalizacjami w celu utworzenia macierzy kosztów. W poniższym przykładzie "0" reprezentuje klucz reprezentujący określony typ pojazdu.

"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]
    ]
    }}}

Opcjonalnie można udostępnić wiele macierzy kosztów w zależności od typów pojazdów. Niektóre pojazdy mogą podróżować szybciej, podczas gdy inne mogą ponosić więcej kosztów podczas podróży przez niektóre obszary. Można to modelować przy użyciu większej liczby macierzy kosztów dla każdego typu pojazdu. W następnym przykładzie istnieją dwie macierze , "0" reprezentuje pierwszy pojazd, który może być samochodem, a "1" reprezentuje drugi pojazd, który może być ciężarówką. Należy pamiętać, że jeśli flota ma pojazdy z podobnymi profilami, musisz określić macierz kosztów tylko raz.

"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]
    ],
    }}}

Ustawianie danych floty

Dane floty mogą opisywać opis floty, taki jak liczba pojazdów, ich lokalizacja początkowa/końcowa oraz pojemność pojazdów używana przez narzędzie do rozwiązywania w celu określenia, które pojazdy są dostępne do wykonania zadania w ramach ograniczeń.

{
     "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]]
        }
    }

• Lokalizacje pojazdów: w powyższym przykładzie dane floty wskazują dwa pojazdy, jedną tablicę dla każdego pojazdu. Oba pojazdy zaczynają się od lokalizacji 0 i kończą podróż w lokalizacji 1. W kontekście opisu macierzy kosztów środowiska te lokalizacje pojazdów odpowiadają indeksom wierszy (lub kolumn) w macierzy kosztów.
• Pojemności: tablica pojemności wskazuje pojemność pojazdu; pierwszy pojazd ma pojemność 2, a drugi pojazd ma pojemność 3. Pojemność może reprezentować różne elementy, na przykład wagę ładunku, umiejętności serwisowe i ich ilości transportowane przez każdy pojazd. W następnej sekcji utworzysz kod JSON zadania, który będzie wymagał wymiaru zapotrzebowania dla każdej lokalizacji zadania, a liczba wymiarów zapotrzebowania będzie odpowiadać liczbie wymiarów pojemności w danych floty. Jeśli na przykład ciężarówka dostarcza towary, pojemność będzie miała łączną wagę, jaką może przewozić każdy pojazd, a zapotrzebowanie będzie miało wagę każdego zamówienia. Upewnij się, że ta sama jednostka jest używana dla obu (takich jak funty lub kilogramy).
• Okna czasu pojazdu: okna czasowe określają czas pracy pojazdu na realizację zadań. Może to być godzina rozpoczęcia i zakończenia zmiany agenta. Nieprzetworzone dane mogą zawierać znacznik czasu w formacie UTC lub format tekstowy, który należy przekształcić na wartość zmiennoprzecinkową. (Przykład: 9:00–18:00 przeliczony na minuty w okresie 24-godzinnym rozpoczynającym się o godzinie 12:00, będzie to [540, 1080]). Wszystkie jednostki czasu/kosztów dostarczone do solveru cuOpt powinny być w tej samej jednostce.
• Przerwy pojazdu: Można również określić okna przerw pojazdu i ich czas trwania. Może to reprezentować przerwę w porze lunchu agenta lub inne przerwy w razie potrzeby. Format okna czasowego przerwy będzie taki sam jak format okna czasowego pojazdu. Wszystkie jednostki czasu/kosztów dostarczone do solveru cuOpt powinny być w tej samej jednostce.

Ustawianie danych zadania

Zadania definiują cel, który musi zostać spełniony w ramach ograniczeń. W kontekście ostatniej mili dostawy może to obejmować lokalizacje dostawy, ilość popytu w każdej lokalizacji, okno dostawy i czas zamieszkania dla każdej lokalizacji.

"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]
}

• Lokalizacja zadania: w powyższym przykładzie, task_locations wskazują lokalizację dostawy, która znajduje się na pozycjach 1, 2, 3 i 4. Te lokalizacje odpowiadają indeksom wierszy (lub kolumn) w macierzy kosztów.
• Zapotrzebowanie: Tablica żądań wskazuje ilość popytu w każdej lokalizacji. Pierwsza lokalizacja ma 3, drugie i trzecie miejsce ma wartość 4, a ostatnia lokalizacja ma 3. Liczba wymiarów zapotrzebowania powinna odpowiadać liczbie wymiarów pojemności dla każdego pojazdu.
• Przedział czasu zadania: ograniczenia przedziału czasu określają, kiedy zadanie ma zostać ukończone. Każde zadanie ma przydzielone przedział czasu rozpoczęcia i zakończenia, a zadanie musi zostać ukończone w ramach tego zadania. Nieprzetworzone dane mogą zawierać znacznik czasu w formacie UTC lub format tekstowy, który należy przekształcić na wartość zmiennoprzecinkową. (Przykład: 9:00–18:00 przeliczony na minuty w okresie 24-godzinnym rozpoczynającym się o godzinie 12:00, będzie to [540, 1080]). Wszystkie jednostki czasu/kosztów dostarczone do solveru cuOpt powinny być w tej samej jednostce.
• Czasy usługi: reprezentuje czas trwania wymagany do wykonania zadań. Tablica service_times określa czas trwania dla każdej lokalizacji zadania. Wszystkie jednostki czasu/kosztów dostarczone do solveru cuOpt powinny być w tej samej jednostce.

Ustawianie konfiguracji programu Solver (opcjonalnie)

Opcjonalnie możesz określić konfigurację modułu rozwiązywania, aby przytłoczać maksymalny czas znalezienia rozwiązania. Zależy to od przypadku użycia, a ustawienie wyższego limitu czasu zwraca lepsze wyniki.

        "solver_config": {
         "time_limit": 1
        }

Jak używać odpowiedzi cuOpt

Moduł rozwiązywania cuOpt zwraca zoptymalizowany przystanek dla każdego pojazdu i trasy podróży. Przeanalizuj odpowiedź i przekonwertuj każdą lokalizację na punkt współrzędny przed wywołaniem interfejsu API Tras usługi Azure Maps, aby uzyskać trasy. Te zoptymalizowane trasy obejmują ścieżkę trasy i wskazówki dojazdu dla każdego agenta.

Przykładowe dane żądania

{
"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": ""
    }
}

Przykładowa odpowiedź

  "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": ""
      }
    }
  }
}

Wykorzystaj interfejs API wskazówek tras w usłudze Azure Maps do trasowania

Gdy lokalizacje w odpowiedzi cuOpt są mapowane na odpowiednie współrzędne, usługa cuOpt może być użyta razem z interfejsem API kierunków trasy usługi Azure Maps i zestawem Web SDK, aby utworzyć aplikację internetową, która wyświetla przypisane marszruty i zoptymalizowane szlaki na mapie. Możesz pokolorować ścieżkę trasy dla poszczególnych pojazdów na podstawie przypisanych przystanków i wyświetlić ją na danych podstawowych usługi Azure Maps.

Następne kroki