Optimalisatieservice voor meerdere reisschema's maken

In deze handleiding wordt uitgelegd hoe u Azure Maps en NVIDIA cuOpt gebruikt om een optimalisatieservice voor routebeschrijvingen te maken. Deze service automatiseert het proces van het bouwen van itineraries voor meerdere agents en gemengde vloot, waarbij de NVIDIA cuOpt routeoptimalisatie-engine wordt gebruikt om routes op meerdere bestemmingen te optimaliseren.

Dit is een proces in twee stappen waarvoor een kostenmatrix nodig is voor de reistijd en een oplosser om het probleem te optimaliseren en een resultaat te genereren. Een kostenmatrix vertegenwoordigt de kosten van reizen tussen elke twee sets locaties in het probleem, waaronder de reistijd en andere reiskosten.

In dit artikel wordt beschreven hoe u:

• Aan de slag met NVIDIA cuOpt op Azure Marketplace.
• Gebruik de Route Matrix-API van Azure Maps om de reiskosten op te halen.
• Het probleem toewijzen aan cuOpt-API-aanroepen.
• Hoe het cuOpt-antwoord te gebruiken.
• Roep de API voor routebeschrijvingen van Azure Maps aan voor routering.

Raadpleeg het codevoorbeeld Multi Itinerary Optimization voor een snelle start.

Vereiste voorwaarden

• Een Azure Maps-account
• Een abonnementssleutel of een andere vorm van verificatie met Azure Maps

Serviceondersteuning

Deze service kan de volgende functies en beperkingen ondersteunen.

Zie cuOpt Supported Features voor de volledige lijst met ondersteunde mogelijkheden.

Aan de slag met NVIDIA cuOpt op Azure Marketplace

NVIDIA cuOpt maakt gebruik van gpu versnelde logistieke oplossers en optimalisaties om complexe problemen met voertuigroutering te berekenen met een breed scala aan beperkingen. Zie de lijst met ondersteunde functies van CuOpt voor meer informatie.

cuOpt is opgenomen in NVIDIA AI Enterprise. Ga naar Azure Marketplace om aan de slag te gaan.

De reiskosten berekenen

Optimalisatie van reisschema's vereist een vierkante matrix van een reismetriek, zoals tijd- of afstandskosten, die worden doorgegeven aan de cuOpt-oplosser. Een kostenmatrix vertegenwoordigt de reiskosten tussen elk paar locaties in de probleemset, waardoor efficiënte routeplanning en optimalisatie mogelijk zijn.

De Azure Maps Route Matrix-API berekent metrische gegevens over reizen, zoals tijd en afstand, van elke oorsprong tot elke bestemming. Deze oorsprongen en bestemmingen vormen de kolom- en rijkoppen van een kostenmatrix, waarbij elke cel de routeringskosten tussen een specifiek oorspronkelijk doelpaar vertegenwoordigt.

Een restaurant heeft bijvoorbeeld twee chauffeurs die voedsel moeten leveren aan vier locaties. Gebruik de Route Matrix-API om reistijden tussen alle relevante punten te berekenen om dit scenario op te lossen. In dit voorbeeld wordt ervan uitgegaan dat beide chauffeurs bij het restaurant beginnen en eindigen. Als de begin- of eindlocaties verschillen van het depot, moeten deze locaties expliciet worden opgenomen in de kostenmatrix.

Aantal oorsprongen = Aantal bestemmingen = 1 (restaurant, ook wel depot genoemd) + 4 (leveringslocaties) = 5

Matrixgrootte = 5 oorsprongen x 5 bestemmingen = 25

De POST-aanvraag voor de routematrix:

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

Het antwoord routematrix retourneert een multidimensionale matrix van 5x5, waarbij elke rij de oorsprongen en kolommen de bestemmingen vertegenwoordigt. Gebruik het veld travelTimeInSeconds om de tijdskosten voor elk locatiepaar op te halen. De tijdseenheid moet consistent zijn in de oplossing. Zodra de voorverwerkingsfase is voltooid, worden de order-, depot-, vlootgegevens en de kostenmatrix via API-aanroepen naar de cuOpt-server verzonden en geïmporteerd.

In het volgende JSON-voorbeeld ziet u wat wordt geretourneerd in de hoofdtekst van het HTTP-antwoord van het voorbeeld van de kostenmatrix:

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

Het probleem toewijzen aan cuOpt-API-aanroepen

In deze sectie wordt beschreven hoe u aanvraaggegevens bouwt voor cuOpt-aanroepen. Zie de aanbevolen procedures voor cuOpt voor meer voorbeelden.

1. Kostenmatrix instellen
2. Vlootgegevens instellen
3. Taakgegevens instellen
4. Configuratie van Oplosser instellen (optioneel)

Kostenmatrix instellen

Parseer de respons van de Route Matrix API van Azure Maps om de reistijd tussen locaties op te halen en daarmee de kostenmatrix samen te stellen. In het volgende voorbeeld vertegenwoordigt '0' de sleutel die een specifiek voertuigtype vertegenwoordigt.

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

Er kunnen eventueel meerdere kostenmatrices worden geleverd, afhankelijk van de typen voertuigen. Sommige voertuigen kunnen sneller reizen, terwijl andere mogelijk meer kosten maken bij het reizen door bepaalde gebieden. Dit kan worden gemodelleerd met meer kostenmatrices één voor elk voertuigtype. Het volgende voorbeeld heeft twee matrices: '0' vertegenwoordigt het eerste voertuig, dat een auto kan zijn en '1' het tweede voertuig vertegenwoordigt, dat een vrachtwagen kan zijn. Als uw vloot voertuigen met vergelijkbare profielen heeft, moet u de kostenmatrix slechts één keer opgeven.

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

Vlootgegevens instellen

Vlootgegevens kunnen de beschrijving van de vloot beschrijven, zoals het aantal voertuigen, hun begin-/eindlocatie en de voertuigcapaciteit die door de oplosser worden gebruikt om te bepalen welke voertuigen beschikbaar zijn om de taak binnen de beperkingen uit te voeren.

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

• Voertuiglocaties: In het bovenstaande voorbeeld geven vlootgegevens twee voertuigen aan, één matrix voor elk voertuig. Beide voertuigen beginnen op locatie 0 en eindreis op locatie 1. In de context van een kostenmatrixbeschrijving van de omgeving komen deze voertuiglocaties overeen met rij- (of kolom) indexen in de kostenmatrix.
• Capaciteiten: De capaciteitsmatrix geeft de voertuigcapaciteit aan; het eerste voertuig heeft een capaciteit van twee en tweede voertuig met een capaciteit van drie. Capaciteit kan verschillende dingen vertegenwoordigen, bijvoorbeeld pakketgewicht, servicevaardigheden en hun hoeveelheden die door elk voertuig worden vervoerd. In de volgende sectie maakt u een taak-JSON die een vraagdimensie vereist voor elke taaklocatie en het aantal vraagdimensie overeenkomt met het aantal capaciteitsdimensies in de vlootgegevens. Als een vrachtwagen bijvoorbeeld goederen levert, is de capaciteit hoeveel gewicht in totaal elk voertuig kan dragen en zou de vraag het gewicht van elke bestelling zijn. Zorg ervoor dat dezelfde eenheid wordt gebruikt voor beide (zoals ponden of kilogram).
• Tijdvensters van het voertuig: Tijdvensters geven de bedrijfstijd van het voertuig op om de taken te voltooien. Dit kan de begin- en eindtijd van de agent zijn. Onbewerkte gegevens kunnen de Universal Time Stamp (UTC)-datum-/tijdnotatie of het stringformaat bevatten dat moet worden geconverteerd naar een zwevendekommawaarde. (Voorbeeld: 9:00 - 18:00 uur geconverteerd naar minuten in een periode van 24 uur vanaf 12:00 uur, zou [540, 1080]) zijn). Alle tijd-/kosteneenheden die aan de cuOpt-oplosser zijn verstrekt, moeten zich in dezelfde eenheid bevinden.
• Voertuigonderbrekingen: Voertuigonderbrekingen en de duur daarvan kunnen ook worden gespecificeerd. Dit kan de lunchpauze van de agent of andere pauzes vertegenwoordigen, indien nodig. De indeling van het onderbrekingsvenster zou hetzelfde zijn als de indeling van het tijdvenster van het voertuig. Alle tijd-/kosteneenheden die aan de cuOpt-oplosser zijn verstrekt, moeten zich in dezelfde eenheid bevinden.

Taakgegevens instellen

Taken definiëren het doel dat binnen de beperkingen moet worden vervuld. In de context van de last-mile delivery kunnen dit de leveringslocaties, de hoeveelheid vraag op elke locatie, het leveringsvenster en de wachttijd voor elke locatie omvatten.

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

• Taaklocatie: In het bovenstaande voorbeeld geeft task_locations de leveringslocatie aan op posities 1, 2, 3 en 4. Deze locaties komen overeen met rijindexen (of kolommen) in de kostenmatrix.
• Vraag: De vraagmatrix geeft de vraaghoeveelheid op elke locatie aan; de eerste locatie heeft een vraag van 3, tweede en derde locatie heeft 4 en de laatste locatie heeft 3. Het aantal vraagdimensies moet overeenkomen met het aantal capaciteitsdimensies voor elk voertuig.
• Taaktijdvenster: Tijdvensterbeperkingen geven aan wanneer een taak moet worden voltooid. Aan elke taak wordt een begin- en eindtijdvenster toegewezen en moet de taak binnen die taak worden voltooid. Onbewerkte gegevens kunnen de Universal Time Stamp (UTC)-datum-/tijdnotatie of het stringformaat bevatten dat moet worden geconverteerd naar een zwevendekommawaarde. (Voorbeeld: 9:00 - 18:00 uur geconverteerd naar minuten in een periode van 24 uur vanaf 12:00 uur, zou [540, 1080]) zijn). Alle tijd-/kosteneenheden die aan de cuOpt-oplosser zijn verstrekt, moeten zich in dezelfde eenheid bevinden.
• Servicetijden: dit vertegenwoordigt de duur die nodig is om de taken te voltooien. De service_times matrix geeft de tijdsduur voor elke taaklocatie aan. Alle tijd-/kosteneenheden die aan de cuOpt-oplosser zijn verstrekt, moeten zich in dezelfde eenheid bevinden.

Configuratie van Oplosser instellen (optioneel)

U kunt eventueel oplosserconfiguratie opgeven om een maximale tijd te geven om een oplossing te vinden. Dit is afhankelijk van de use-case en het instellen van een hogere tijdslimiet retourneert betere resultaten.

        "solver_config": {
         "time_limit": 1
        }

Het cuOpt-antwoord gebruiken

De cuOpt oplosser retourneert de geoptimaliseerde stop voor elk voertuig en het reisschema. Parseert het antwoord en converteert elke locatie naar een coördinaatpunt voordat u de Routebeschrijvings-API van Azure Maps aanroept om de routes op te halen. Deze geoptimaliseerde routes omvatten het routepad en de routebeschrijving voor elke agent.

Voorbeeld van aanvraaggegevens

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

Voorbeeldantwoord

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

Routebeschrijvings-API voor Azure Maps aanroepen voor routering

Nadat de locaties in het cuOpt-antwoord zijn toegewezen aan de bijbehorende coördinaten, kan de cuOpt-service worden gebruikt met de Azure Maps Route Directions-API en web-SDK om een web-app te maken die de toegewezen routes en geoptimaliseerde routes op de kaart weergeeft. U kunt het routepad voor afzonderlijke voertuigen kleuren op basis van de toegewezen haltes en weergeven op de basisgegevens van Azure Maps.

Volgende stappen