Skapa optimeringstjänst för flera resplaner

Den här guiden beskriver hur du använder Azure Maps och NVIDIA cuOpt för att skapa en tjänst för resvägsoptimering. Den här tjänsten automatiserar processen med att skapa resplaner för flera agenter och blandade flottor och använder NVIDIA cuOpt-routningsoptimeringsmotorn för att optimera rutter över flera destinationer.

Det här är en tvåstegsprocess som kräver en kostnadsmatris för restiden och en lösning för att optimera problemet och generera ett resultat. En kostnadsmatris representerar kostnaden för att resa mellan två uppsättningar platser i problemet, vilket inkluderar restidskostnaden och andra resekostnader.

I den här artikeln beskrivs hur du:

• Kom igång med NVIDIA cuOpt på Azure Marketplace.
• Använd API:et för Routningsmatris för Azure Maps för att hämta resekostnaden.
• Så här mappar du problemet till cuOpt API-anrop.
• Så här använder du cuOpt-svaret.
• Anropa Azure Maps Route Directions API för routning.

Se kodexemplet för optimering av flera resplaner för en snabbstart.

Förutsättningar

• Ett Azure Maps-konto
• En prenumerationsnyckel eller annan form av autentisering med Azure Maps

Tjänstsupport

Den här tjänsten har stöd för följande funktioner och begränsningar.

För en fullständig lista över stödda funktioner, se cuOpt Supported Features.

Kom igång med NVIDIA cuOpt på Azure Marketplace

NVIDIA cuOpt använder GPU-accelererad logistiklösare och optimeringar för att beräkna komplexa problem med fordonsroutning med en mängd olika begränsningar. Mer information finns i Listan över cuOpt-funktioner som stöds.

cuOpt ingår i NVIDIA AI Enterprise. Gå till Azure Marketplace för att komma igång.

Hämta resekostnaden

Resvägsoptimering kräver en kvadratmatris för ett resemått, till exempel tids- eller avståndskostnad, som skickas till cuOpt-lösaren. En kostnadsmatris representerar resekostnaden mellan varje par platser i problemuppsättningen, vilket möjliggör effektiv vägplanering och optimering.

Api:et för Azure Maps Route Matrix beräknar resemått, till exempel tid och avstånd, från varje ursprung till varje mål. Dessa ursprung och mål utgör kolumn- och radrubrikerna i en kostnadsmatris, där varje cell representerar routningskostnaden mellan ett specifikt origin-destination-par.

Till exempel har en restaurang två förare som behöver leverera mat till fyra platser. Lös det här scenariot genom att använda ROUTNINGSMATRIS-API:et för att beräkna restider mellan alla relevanta punkter. Det här exemplet förutsätter att både förare startar och slutar på restaurangen. Om start- eller slutplatserna skiljer sig från depån måste dessa platser uttryckligen inkluderas i kostnadsmatrisen.

Antal ursprung = Antal destinationer = 1 (restaurang, även kallad depå) + 4 (leveransplatser) = 5

Matrisstorlek = 5 ursprung x 5 mål = 25

POST-begäran för routningsmatris:

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-svaret returnerar en 5x5 flerdimensionell matris där varje rad representerar ursprunget och kolumnerna representerar målen. Använd fältet travelTimeInSeconds för att hämta tidskostnaden för varje platspar. Tidsenheten ska vara konsekvent i hela lösningen. När förbearbetningssteget är klart skickas beställningen, depån, vagnparksinformationen och kostnadsmatrisen över och importeras till cuOpt Server via API-anrop.

Följande JSON-exempel visar vad som returneras i brödtexten i HTTP-svaret i kostnadsmatrisexemplet:

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

Mappa problemet till cuOpt API-anrop

I det här avsnittet beskrivs hur du skapar begärandedata för cuOpt-anrop. Fler exempel finns i cuOpt-metodtips.

1. Ange kostnadsmatris
2. Ange fleet-data
3. Ange aktivitetsdata
4. Ange Solver Config (valfritt)

Ange kostnadsmatris

Parsa svaret för Azure Maps Route Matrix API för att hämta restiden mellan platser för att konstruera kostnadsmatrisen. I följande exempel representerar "0" nyckeln som representerar en viss fordonstyp.

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

Flera kostnadsmatriser kan eventuellt tillhandahållas beroende på fordonstyper. Vissa fordon kan färdas snabbare medan andra kan medföra mer kostnader när de färdas genom vissa områden. Detta kan modelleras med fler kostnadsmatriser en för varje fordonstyp. Nästa exempel har två matriser, "0" representerar det första fordonet, som kan vara en bil och "1" representerar det andra fordonet, som kan vara en lastbil. Observera att om din flotta har fordon med liknande profiler behöver du bara ange kostnadsmatrisen en gång.

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

Ställ in fordonsflottadata

Vagnparksdata kan beskriva vagnparksbeskrivningen, till exempel antalet fordon, deras start-/slutplats och fordonskapacitet som används av lösaren för att avgöra vilka fordon som är tillgängliga för att utföra uppgiften inom ramen för begränsningarna.

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

• Fordonsplatser: I exemplet ovan anger vagnparksdata två fordon, en matris för varje fordon. Båda fordonen börjar på plats 0 och avslutar resan på plats 1. I samband med en kostnadsmatrisbeskrivning av miljön motsvarar dessa fordonsplatser radindex (eller kolumn) i kostnadsmatrisen.
• Kapaciteter: Kapacitetsmatrisen anger fordonets kapacitet; det första fordonet har en kapacitet på två och ett andra fordon har en kapacitet på tre. Kapaciteten kan representera olika saker, till exempel paketvikt, servicekunskaper och deras transportbelopp för varje fordon. I nästa avsnitt skapar du en aktivitets-JSON som kräver en efterfrågedimension för varje aktivitetsplats och antalet efterfrågedimensioner motsvarar antalet kapacitetsdimensioner i vagnparksdata. Till exempel, om en lastbil levererar varor, skulle kapaciteten vara hur mycket vikt totalt varje fordon kan bära, och efterfrågan skulle vara vikten på varje beställning. Kontrollera att samma enhet används för båda (till exempel pund eller kilo).
• Fordonets tidsfönster: Tidsfönster anger fordonets drifttid för att slutföra uppgifterna. Det kan vara agentens start- och sluttid för skift. Rådata kan innehålla utc-format (Universal Time Stamp) datum/tid eller strängformat som måste konverteras till flytande värde. (Exempel: 09:00–18:00 konverteras till minuter under en 24-timmarsperiod som börjar vid midnatt, skulle vara [540, 1080]). Alla tidsenheter och kostnadsenheter som tillhandahålls till programmet cuOpt bör vara i samma enhet.
• Fordonsuppehåll: Fordonsuppehållsfönster och varaktighet kan också anges. Detta kan representera agentens lunchrast eller andra pauser efter behov. Formatet för avbrottsfönstret är samma som formatet för fordonets tidsfönster. Alla tidsenheter och kostnadsenheter som tillhandahålls till programmet cuOpt bör vara i samma enhet.

Ange aktivitetsdata

Uppgifter definierar det mål som måste uppfyllas inom begränsningarna. I samband med den sista milens leverans kan detta omfatta leveransplatser, efterfrågan på varje plats, leveransfönster och uppehållstid för varje plats.

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

• Uppgiftsplats: I exemplet ovan anger task_locations leveransplatsen som finns på positionerna 1, 2, 3 och 4. Dessa platser motsvarar radindex (eller kolumn) i kostnadsmatrisen.
• Efterfrågan: Efterfrågematrisen anger efterfrågan på varje plats. Den första platsen har en efterfrågan på 3, den andra och den tredje platsen har 4 och den sista platsen har 3. Antalet efterfrågedimensioner bör motsvara antalet kapacitetsdimensioner för varje fordon.
• Tidsfönster för aktivitet: Tidsfönsterbegränsningar anger när en aktivitet ska slutföras. Varje aktivitet tilldelas ett start- och sluttidsfönster, och uppgiften måste slutföras inom den. Rådata kan innehålla utc-format (Universal Time Stamp) datum/tid eller strängformat som måste konverteras till flytande värde. (Exempel: 09:00–18:00 konverteras till minuter under en 24-timmarsperiod som börjar vid midnatt, skulle vara [540, 1080]). Alla tidsenheter och kostnadsenheter som tillhandahålls till programmet cuOpt bör vara i samma enhet.
• Tjänsttider: Detta representerar den varaktighet som krävs för att slutföra uppgifterna. Matrisen service_times anger varaktigheten för varje aktivitetsplats. Alla tidsenheter och kostnadsenheter som tillhandahålls till programmet cuOpt bör vara i samma enhet.

Ange solverkonfiguration (valfritt)

Du kan också ange lösningskonfiguration för att tilldela en maximal tid för att hitta en lösning. Detta beror på användningsfallet, och om du anger en högre tidsgräns returneras bättre resultat.

        "solver_config": {
         "time_limit": 1
        }

Så här använder du cuOpt-svaret

CuOpt-lösaren returnerar det optimerade stoppet för varje fordon och resplanen. Parsa svaret och konvertera varje plats till en koordinatpunkt innan du anropar AZURE Maps Route Directions API för att hämta vägarna. Dessa optimerade rutter omfattar ruttens väg och köranvisningar för varje agent.

Exempel på begärandedata

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

Exempelsvar

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

Anropa Azure Maps Route Directions API för routning

När platserna i cuOpt-svaret har mappats till motsvarande koordinater kan cuOpt-tjänsten användas med Azure Maps Route Directions API och Web SDK för att skapa en webbapp som visar tilldelade resvägar och optimerade vägar på kartan. Du kan färgkoda vägsökvägen för enskilda fordon baserat på de tilldelade stoppen och visa den på Azure Maps-basdata.

Nästa steg