L'algoritmo non faceva ciò che serviva. Prima semplicemente ordinava dei nodi senza tenere conto degli orari dei vari nodi. Ora ne tiene conto.
è stata introdotta una funzione compact internamente all'algoritmo che serve a comprimere gli orari di una sequenza di nodi di un grafo, mantenendo però la posizione relativa dei nodi in modo da poter provare più combinazioni di sequenze di nodi generati dal 2-opt.
Più precisamente, la funzione prende in input tre argomenti:
uncompacted_route: una lista di interi che rappresenta la sequenza di nodi da comprimere;
dist_matrix: una matrice che rappresenta le distanze tra i nodi;
node_limit: un dizionario che contiene i limiti di tempo per i nodi fissi.
La funzione restituisce la sequenza di nodi compressa. Se la compressione non è possibile perché i limiti di tempo dei nodi fissi non possono essere rispettati, la funzione restituisce None.
La compressione avviene in due fasi principali:
Si calcolano i tempi di arrivo a tutti i nodi della sequenza, a partire dal primo nodo fissato. Questo viene fatto utilizzando la matrice delle distanze e i limiti di tempo dei nodi fissi.
Si comprime la sequenza di nodi, mantenendo la posizione relativa dei nodi fissi. Questo viene fatto spostando i nodi liberi nel momento in cui è possibile mantenere i limiti di tempo dei nodi fissi.
Inoltre, la funzione verifica che la sequenza di nodi compressa rispetti i limiti di tempo dei nodi fissi e che i nodi liberi non superino il loro limite massimo di visita. E se non c'è modo di risolvere i ritardi cerca di distribuire il ritardo tra i vari nodi se il ritardo è minore di 15 minuti e invece lo lascia com'è se è un ritardo grande.
In questa fase la funzione RPC esportata dal microservizio make-root-service prende in input i seguenti parametri:
dist_matrix: una matrice delle distanze tra i nodi del grafo
prec_hash: un dizionario che rappresenta le precedenze tra i nodi del grafo. Le chiavi del dizionario sono i nodi, i valori sono liste di nodi che devono essere visitati prima della chiave stessa
travel_time_matrix: una matrice che rappresenta i tempi di viaggio tra i nodi del grafo
node_limit: un dizionario che rappresenta i limiti di tempo per ogni nodo del grafo. Le chiavi del dizionario sono i nodi, i valori sono tuple che rappresentano l'orario di inizio e fine della finestra temporale in cui il nodo può essere visitato.
Nota: al momento il parametri di input travel_time_matrix non viene utilizzato
L'algoritmo non faceva ciò che serviva. Prima semplicemente ordinava dei nodi senza tenere conto degli orari dei vari nodi. Ora ne tiene conto. è stata introdotta una funzione compact internamente all'algoritmo che serve a comprimere gli orari di una sequenza di nodi di un grafo, mantenendo però la posizione relativa dei nodi in modo da poter provare più combinazioni di sequenze di nodi generati dal 2-opt. Più precisamente, la funzione prende in input tre argomenti:
La funzione restituisce la sequenza di nodi compressa. Se la compressione non è possibile perché i limiti di tempo dei nodi fissi non possono essere rispettati, la funzione restituisce None.
La compressione avviene in due fasi principali:
Inoltre, la funzione verifica che la sequenza di nodi compressa rispetti i limiti di tempo dei nodi fissi e che i nodi liberi non superino il loro limite massimo di visita. E se non c'è modo di risolvere i ritardi cerca di distribuire il ritardo tra i vari nodi se il ritardo è minore di 15 minuti e invece lo lascia com'è se è un ritardo grande.
In questa fase la funzione RPC esportata dal microservizio make-root-service prende in input i seguenti parametri:
Nota: al momento il parametri di input travel_time_matrix non viene utilizzato