Creare un servizio di ottimizzazione per itinerari multipli

Questa guida illustra come usare Mappe di Azure e NVIDIA cuOpt per creare un servizio di ottimizzazione dell'itinerario. Questo servizio automatizza il processo di creazione di itinerari per più agenti e flotta miste, usando il motore di ottimizzazione delle route NVIDIA cuOpt per ottimizzare le rotte tra più destinazioni.

Si tratta di un processo in due passaggi che richiede una matrice di costi per il tempo di viaggio e un risolutore per ottimizzare il problema e generare un risultato. Una matrice di costi rappresenta il costo del viaggio tra ogni due set di posizioni nel problema, che include il costo del tempo di viaggio e altri costi di viaggio.

In questo articolo viene descritto come:

• Introduzione a NVIDIA cuOpt in Azure Marketplace.
• Usa l'API Matrice del Percorso di Azure Maps per ottenere il costo di viaggio.
• Come eseguire il mapping del problema alle chiamate API cuOpt.
• Come usare la risposta cuOpt.
• Chiamare l'API Azure Maps Route Directions per il routing.

Per iniziare velocemente, fai riferimento all'esempio di codice Ottimizzazione Multi Itinerario.

Prerequisiti

• Un account di Mappe di Azure
• Una chiave di sottoscrizione o un altro tipo di autenticazione con Mappe di Azure

Supporto del servizio

Questo servizio può supportare le funzionalità e i vincoli seguenti.

Per l'elenco completo delle funzionalità supportate, vedere cuOpt Supported Features (Funzionalità supportate da cuOpt).

Introduzione a NVIDIA cuOpt in Azure Marketplace

NVIDIA cuOpt usa il risolutore logistico accelerato della GPU e ottimizzazioni per calcolare problemi complessi di routing dei veicoli con un'ampia gamma di vincoli. Per altre informazioni, vedere l'elenco delle funzionalità supportate da cuOpt.

cuOpt è incluso in NVIDIA AI Enterprise. Per iniziare, visitare Azure Marketplace .

Ottenere il costo di viaggio

L'ottimizzazione dell'itinerario richiede una matrice quadrata di una metrica di viaggio, ad esempio il costo del tempo o della distanza, passato al risolutore cuOpt. Una matrice di costi rappresenta il costo di viaggio tra ogni coppia di località nel set di problemi, consentendo una pianificazione e un'ottimizzazione efficienti delle route.

L'API Route Matrix di Azure Maps calcola le metriche di viaggio, come il tempo e la distanza, da ogni partenza a ogni destinazione. Queste origini e destinazioni formano le intestazioni di colonna e di riga di una matrice di costi, in cui ogni cella rappresenta il costo di routing tra una coppia di origine-destinazione specifica.

Ad esempio, un ristorante ha due conducenti che devono consegnare cibo a quattro posizioni. Per risolvere questo scenario, usare l'API Matrice di route per calcolare i tempi di viaggio tra tutti i punti rilevanti. In questo esempio si presuppone che entrambi i driver inizino e terminano al ristorante. Se le posizioni iniziali o finali differiscono dal deposito, tali posizioni devono essere incluse in modo esplicito nella matrice dei costi.

Numero di origini = Numero di destinazioni = 1 (ristorante, detto anche deposito) + 4 (posizioni di consegna) = 5

Dimensione matrice = 5 origini x 5 destinazioni = 25

La richiesta POST della matrice di percorso:

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

La risposta Matrice di route restituisce una matrice 5x5 multidimensionale in cui ogni riga rappresenta le origini e le colonne rappresentano le destinazioni. Usare il campo travelTimeInSeconds per ottenere il costo del tempo per ogni coppia di località. L'unità di tempo deve essere coerente nella soluzione. Al termine della fase di pre-elaborazione, l'ordine, il deposito, le informazioni sulla flotta e la matrice dei costi vengono inviati e importati nel server cuOpt tramite chiamate API.

L'esempio JSON seguente mostra cosa viene restituito nel corpo della risposta HTTP dell'esempio di matrice di costi:

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

Mappare il problema alle chiamate API di cuOpt

Questa sezione descrive come compilare i dati delle richieste per le chiamate cuOpt. Per altri esempi, vedere procedure consigliate per cuOpt.

1. Imposta matrice costi
2. Imposta dati della flotta
3. Imposta dati attività
4. Impostare la configurazione del risolutore (facoltativo)

Imposta matrice di costi

Analizzare la risposta dell'API Matrice di percorso di Azure Maps per ottenere il tempo di viaggio tra i luoghi e costruire la matrice dei costi. Nell'esempio seguente "0" rappresenta la chiave che rappresenta un tipo di veicolo specifico.

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

Facoltativamente, è possibile fornire più matrici di costi a seconda dei tipi di veicoli. Alcuni veicoli possono viaggiare più velocemente, mentre altri potrebbero comportare più costi durante il viaggio attraverso determinate aree. Questo modello può essere modellato usando più matrici di costo uno per ogni tipo di veicolo. Nell'esempio seguente sono presenti due matrici, "0" rappresenta il primo veicolo, che potrebbe essere un'auto e "1" rappresenta il secondo veicolo, che potrebbe essere un camion. Si noti che se la flotta ha veicoli con profili simili, è necessario specificare la matrice dei costi una sola volta.

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

Imposta i dati della flotta

I dati della flotta possono descrivere la descrizione della flotta, ad esempio il numero di veicoli, la posizione iniziale/finale e la capacità del veicolo utilizzata dal risolutore per determinare quali veicoli sono disponibili per svolgere l'attività entro i vincoli.

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

• Posizioni dei veicoli: nell'esempio precedente, i dati della flotta indicano due veicoli, una matrice per ogni veicolo. Entrambi i veicoli partono dalla posizione 0 e terminano alla posizione 1. Nel contesto di una descrizione della matrice di costi dell'ambiente, queste posizioni dei veicoli corrispondono agli indici di riga (o colonna) nella matrice dei costi.
• Capacità: la matrice di capacità indica la capacità del veicolo; il primo veicolo ha una capacità di due e due secondi veicoli ha una capacità di tre. La capacità potrebbe rappresentare varie cose, ad esempio peso del pacchetto, competenze di servizio e i relativi importi trasportati da ogni veicolo. Nella sezione successiva si creerà un codice JSON dell'attività che richiederà una dimensione della domanda per ogni posizione dell'attività e il numero di dimensioni della domanda corrisponderà al numero di dimensioni della capacità nei dati della flotta. Ad esempio, se un camion sta consegnando merci, la capacità sarebbe il peso totale di ogni veicolo e la domanda sarebbe il peso di ogni ordine. Assicurarsi che la stessa unità sia usata per entrambi (ad esempio chili o chilogrammi).
• Intervalli di tempo del veicolo: le finestre temporali specificano l'ora operativa del veicolo per completare le attività. Potrebbe trattarsi dell'ora di inizio e di fine del turno dell'agente. I dati non elaborati possono includere formato data/ora UTC (Universal TimeStamp) o formato stringa che deve essere convertito in valore mobile. (Ad esempio: 9:00 - 18:00 convertiti in minuti in un periodo di 24 ore a partire dalle 12:00, sarebbe [540, 1080]). Tutte le unità di tempo/costo fornite al risolutore cuOpt devono trovarsi nella stessa unità.
• Interruzioni del veicolo: è anche possibile specificare finestre di interruzione del veicolo e durata. Questo potrebbe rappresentare la pausa pranzo dell'agente o altre interruzioni in base alle esigenze. Il formato della finestra di interruzione corrisponde al formato dell'intervallo di tempo del veicolo. Tutte le unità di tempo/costo fornite al risolutore cuOpt devono trovarsi nella stessa unità.

Impostare i dati delle attività

Le attività definiscono l'obiettivo che deve essere soddisfatto entro i vincoli. Nel contesto della consegna dell'ultimo miglio, questo potrebbe includere le posizioni di consegna, la quantità della domanda in ogni località, la finestra di consegna e il tempo di attesa per ogni località.

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

• Posizione attività: nell'esempio precedente task_locations indicare l'ubicazione di consegna situato nelle posizioni 1, 2, 3 e 4. Queste posizioni corrispondono agli indici di riga (o colonna) nella matrice dei costi.
• Domanda: l'array della domanda indica la quantità della domanda in ogni posizione. La prima posizione ha una domanda di 3, la seconda e la terza di 4 e l'ultima di 3. Il conteggio delle dimensioni della domanda deve corrispondere al numero di dimensioni di capacità per ogni veicolo.
• Intervallo di tempo attività: i vincoli di intervallo di tempo specificano quando deve essere completata un'attività. A ogni attività viene assegnato un intervallo di tempo di inizio e di fine e l'attività deve essere completata in tale intervallo. I dati non elaborati possono includere formato data/ora UTC (Universal TimeStamp) o formato stringa che deve essere convertito in valore mobile. (Ad esempio: 9:00 - 18:00 convertiti in minuti in un periodo di 24 ore a partire dalle 12:00, sarebbe [540, 1080]). Tutte le unità di tempo/costo fornite al risolutore cuOpt devono trovarsi nella stessa unità.
• Tempi di servizio: rappresenta la durata necessaria per completare le attività. L'array service_times specifica la durata di ogni posizione dell'attività. Tutte le unità di tempo/costo fornite al risolutore cuOpt devono trovarsi nella stessa unità.

Impostare la configurazione del risolutore (facoltativo)

Facoltativamente, è possibile specificare la configurazione del risolutore per allocare un tempo massimo per trovare una soluzione. Questo dipende dal caso d'uso e l'impostazione di un limite di tempo superiore restituisce risultati migliori.

        "solver_config": {
         "time_limit": 1
        }

Come usare la risposta cuOpt

Il risolutore cuOpt restituisce la fermata ottimizzata per ogni veicolo e l'itinerario di viaggio. Analizzare la risposta e convertire ogni posizione in un punto di coordinata prima di chiamare l'API di indicazioni di itinerario di Azure Maps per ottenere i percorsi. Questi percorsi ottimizzati includono il percorso e le indicazioni stradali per ogni agente.

Dati della richiesta di esempio

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

Risposta di esempio

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

Chiamare l'API per le indicazioni stradali di Azure Maps per il routing

Dopo il mapping delle posizioni nella risposta cuOpt alle coordinate corrispondenti, il servizio cuOpt può essere usato con l'API Indicazioni stradali di Mappe di Azure e l'SDK Web per creare un'app Web che visualizza gli itinerari assegnati e i percorsi ottimizzati sulla mappa. È possibile colorare il percorso per i singoli veicoli in base alle fermate assegnate e visualizzarlo sui dati di base Mappe di Azure.

Passaggi successivi