Dimensioni

Il risolutore di percorsi utilizza un oggetto chiamato dimensione per tenere traccia delle quantità che si accumulano lungo il percorso di un veicolo, ad esempio il tempo di percorrenza o, se il veicolo sta ritirando e consegnando, il peso totale che sta portando. Se un problema di routing riguarda una quantità simile, nei vincoli o nella funzione oggettiva, devi definire una dimensione per specificarla.

Questa sezione spiega come definire e utilizzare le dimensioni.

Esempi di dimensioni

Ecco un paio di esempi di dimensioni tratte dalle sezioni precedenti.

  • L'esempio VRPTW crea una dimensione per monitorare il tempo di percorrenza cumulativo di ogni veicolo. Il risolutore utilizza la dimensione per applicare il vincolo che un veicolo può visitare solo una posizione all'interno dell'intervallo di tempo della località.

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

Gli esempi riportati di seguito definiscono una dimensione per il VRPTW utilizzando il metodo 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 contiene i seguenti input:

  • callback_index: l'indice del callback che restituisce la quantità. L'indice, che è il riferimento interno del risolutore al callback, viene creato con metodi come RegisterTransitCallback o RegisterUnitaryTransitCallback.
  • slack_max: valore massimo per lo slack, una variabile utilizzata per rappresentare i tempi di attesa nelle località. Per ulteriori dettagli, consulta la sezione Variabili slack di seguito. Se il problema non comporta l'attesa, di solito puoi impostare slack_max su 0.
  • capacity: valore massimo per la quantità totale accumulata lungo ogni percorso. Utilizzare capacity per creare vincoli come quelli nel CVRP. Se il problema non ha un vincolo simile, puoi impostare capacity su un valore sufficientemente elevato da non imporre limitazioni alle route, ad esempio la somma di tutte le voci 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, è necessario impostare True. Tuttavia, per la situazione VRPTW o i problemi con i vincoli delle risorse, alcuni veicoli potrebbero dover iniziare dopo l'ora 0 a causa di vincoli della finestra temporale, quindi devi impostare fix_start_cumulative_to_zero su False per questi problemi.
  • dimension_name: stringa per il nome della dimensione, ad esempio 'Distance', che puoi utilizzare per accedere alle variabili altrove nel programma.

Il programma CVRP crea un tipo di dimensione leggermente diverso utilizzando il metodo AddDimensionWithVehicleCapacity. Questo metodo accetta un array di capacità, con una voce per ogni veicolo. AddDimension crea invece un singolo valore per capacity, pertanto si presume che tutti i veicoli abbiano la stessa capacità.

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

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

Variabili di Slack

Di seguito è riportato un esempio che illustra le variabili di gioco per un tempo di viaggio. Supponiamo che un veicolo passi dalla località i alla località j in un solo passaggio lungo il percorso e che:

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

Il veicolo non può uscire dalla posizione i immediatamente dopo l'arrivo, altrimenti il suo tempo cumulativo è 175. Il veicolo deve invece attendere 25 minuti nella località di destinazione prima di partire, in altre parole, il tempo di percorrenza nella posizione i è di 25.

Devi consentire il gioco in un VRPTW perché i veicoli potrebbero dover attendere prima di visitare un luogo, a causa dei vincoli del periodo di tempo. In un problema come questo, imposta slack_max sul tempo massimo che vuoi consentire ai veicoli di attendere in un luogo prima di passare a quella successiva. Indipendentemente dal tempo di attesa, imposta slack_max su un numero molto alto.

Per il CVRP, invece, la modifica del carico cumulato da i a j equivale sempre alla domanda di i, quindi non si verifica alcun ritardo. Per problemi di questo tipo, puoi impostare slack_max su 0.

Vediamo quindi la definizione formale di Slack. Internamente, una dimensione archivia due tipi di variabili correlate alle quantità che si accumulano lungo i percorsi:

  • Variabili del trasporto pubblico: l'aumento o la diminuzione della quantità in ogni fase di un percorso. Se i -> j è un passaggio in un percorso, la variabile di transito è l'elemento i, j della matrice di trasporto pubblico (per una richiamata di trasporto pubblico) o semplicemente il valore di callback nella località i (se il callback dipende da una sola località).
  • Variabili cumulative: la quantità totale accumulata in ogni località. Puoi accedere alla variabile cumulativa nella località i da dimension_name.CumulVar(i). Per un esempio, consulta i vincoli per le finestre temporali nell'esempio VRPTW.

Presumendo che un veicolo passi dalla località i alla località j in un solo passaggio, lo slack è correlato alle seguenti variabili: 

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

Per ulteriori dettagli sulle dimensioni, consulta RoutingDimension nella sezione di riferimento.