Dimensioni

Il risolutore di routing utilizza un oggetto chiamato dimensione per tenere traccia quantità che si accumulano lungo il percorso di un veicolo, ad esempio il tempo di percorrenza o se il veicolo effettua Ritira e consegne, il peso totale che trasporta di Google. Se un problema di routing riguarda una determinata quantità, nei vincoli o funzione obiettivo, devi definire una dimensione per specificarla.

Questa sezione spiega come definire e utilizzare le dimensioni.

Esempi di dimensioni

Di seguito sono riportati alcuni esempi di dimensioni tratte dalle sezioni precedenti.

  • L'esempio VRPTW crea una dimensione da monitorare il tempo di percorrenza cumulativo di ciascun veicolo. Il risolutore usa la dimensione per applicare il vincolo che un veicolo può visitare solo una località finestra temporale.

  • L'esempio di CVRP crea una dimensione per il parametro le richieste (ad es. pesi o volumi dei pacchi da ritirare), quali il carico cumulativo che il veicolo trasporta lungo il percorso. Il risolutore utilizza la dimensione per applicare il vincolo che il carico di un veicolo non può superare la sua capacità.

I seguenti esempi definiscono una dimensione per il VRPTW utilizzando il parametro AddDimension .

Python

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

C++

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

Java

routing.addDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

C#

routing.AddDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

Il metodo AddDimension ha i seguenti input:

  • callback_index: l'indice per il callback che restituisce la quantità. La , che è il riferimento interno del risolutore al callback, viene creato come RegisterTransitCallback o RegisterUnitaryTransitCallback.
  • slack_max: il valore massimo per slack, una variabile utilizzata per rappresentare l'attesa orari nelle sedi. Consulta le variabili di Slack di seguito per i dettagli. Se il problema non prevede tempi di attesa, in genere puoi impostare slack_max a 0.
  • capacity: la quantità totale accumulata lungo ogni percorso. Utilizza capacity per creare vincoli come quelli nella CVRP: Se il tuo problema non presenta puoi impostare capacity su un valore sufficientemente grande da non imporre restrizioni ai percorsi, ad esempio la somma di tutte della matrice o dell'array utilizzate per definire il callback.
  • fix_start_cumulative_to_zero: valore booleano. Se true, il valore cumulativo della quantità inizia da 0. Nella maggior parte dei casi, dovrebbe essere impostato su True. Tuttavia, per VRPTW o per problemi con limiti delle risorse, alcuni veicoli potrebbe dover iniziare dopo il valore 0 a causa dei vincoli della finestra temporale, quindi imposta fix_start_cumulative_to_zero su False per questi problemi.
  • dimension_name: stringa per il nome della dimensione, ad esempio 'Distance', che puoi usare per accedere alle variabili in un altro punto del programma.

Il programma CVRP crea un tipo di dimensione leggermente diverso utilizzando AddDimensionWithVehicleCapacity . Questo metodo prevede una serie di capacità, con una voce per ogni veicolo. (Al contrario, AddDimension assume un singolo valore per capacity, quindi tutte si presume che i veicoli abbiano la stessa capacità.)

Consulta la RoutingModel pagina di riferimento per altri metodi che creano dimensioni.

La sezione Salva le finestre temporali della soluzione in un elenco o in un array presenta funzioni che salvano i dati cumulativi in una dimensione in un elenco o in una matrice.

Variabili Slack

Ecco un esempio che illustra le variabili slack per un problema che tempi di percorrenza. Supponiamo che un veicolo passa dalla posizione i alla posizione j in una fase del percorso e che:

  • Il tempo di percorrenza cumulativo del veicolo alle i è di 100 minuti.
  • Il tempo di percorrenza cumulativo del veicolo in j è di 200 minuti.
  • Il tempo di percorrenza da i a j è di 75 minuti.

Il veicolo non può uscire dalla posizione i subito all'arrivo o dalla sua posizione cumulativa nella posizione j è pari a 175. Il veicolo deve attendere 25 minuti alle ore posizione i prima della partenza; in altre parole, l'intervallo nella posizione i è 25.

Devi consentire l'uso del VRPTW in quanto i veicoli potrebbero dover attendere prima visitare un luogo a causa dei limiti di tempo. In un problema come questo, imposta slack_max per il tempo massimo che vuoi concedere ai veicoli di attendere un luogo prima di passare al luogo successivo. Se non importa quanto a lungo attendono, imposta slack_max su un numero molto elevato.

Per il CVRP, invece, la variazione del carico accumulato da i a Il valore di j equivale sempre alla domanda di i, quindi non esiste un rallentamento. Per problemi quali In questo caso, puoi impostare slack_max su 0.

Daremo quindi la definizione formale di slack. Internamente, una dimensione memorizza due tipi di variabili relative alle quantità che si accumulano lungo i percorsi:

  • Variabili di trasporto pubblico: l'aumento o la diminuzione della quantità in ogni fase della un percorso. Se i -> j è un passaggio in un percorso, la variabile di trasporto pubblico è i, j della matrice di transito (per una richiamata del trasporto pubblico) o semplicemente il valore di callback nella posizione i (se il callback dipende da una sola località).
  • Variabili cumulative: la quantità totale accumulata in ciascuna località. Tu può accedere alla variabile cumulativa nella posizione i dimension_name.CumulVar(i). Per un esempio, vedi limiti della finestra temporale nell'esempio di VRPTW.

Supponendo che un veicolo vada dalla località i a quella j in un solo passaggio, il slack è correlato a queste variabili come segue: 

slack(i) = cumul(j) - cumul(i) - transit(i, j)

Per ulteriori dettagli sulle dimensioni, consulta RoutingDimension nella sezione dei riferimenti.