Warm-start, ricerca locale e vicinati: come il nostro motore riottimizza continuamente i percorsi

Pubblicato il 22 Giugno 2026 • Tempo di lettura: 8 min read

Nei problemi di ottimizzazione dei percorsi, produrre una prima soluzione rappresenta raramente la sfida principale. La vera difficoltà emerge quando la pianificazione deve evolvere in risposta a eventi operativi quali l’aggiunta di una nuova attività, un ritardo, un annullamento, una modifica della richiesta di un cliente, la riassegnazione di un veicolo o ancora la saturazione locale di un percorso.

In questo contesto, il motore non lavora più su un problema iniziale. Deve adattare un sistema già costruito, già soggetto a vincoli e spesso già parzialmente ottimizzato, preservandone il più possibile la qualità complessiva. È proprio questa capacità di far evolvere in modo efficiente una pianificazione esistente a distinguere i problemi di ottimizzazione dinamica dagli approcci teorici più tradizionali.

Questo articolo si concentra volutamente sui meccanismi di riottimizzazione utilizzati nei motori di ottimizzazione dinamica dei percorsi: warm-start, ricerca locale, vicinati ed euristiche di esplorazione. Per una panoramica più ampia delle problematiche legate all’ottimizzazione dei percorsi nella logistica dell’ultimo miglio, puoi consultare anche il nostro articolo completo dedicato all’ottimizzazione dei percorsi.

Nelle attività operative reali, un motore efficiente non può ripartire da zero a ogni evento. Gli algoritmi di ottimizzazione devono essere in grado di riottimizzare localmente una pianificazione in continua evoluzione, senza destabilizzare inutilmente i percorsi esistenti.

In AntsRoute, questa problematica è al centro dell’architettura del motore di ottimizzazione.

In questo articolo scoprirai:

• Perché ripartire da zero è raramente una buona strategia in tempo reale
• Il ruolo del warm-start nei percorsi dinamici
• Perché un inserimento deve essere valutato in una prospettiva globale
• Come funziona la ricerca locale
• Perché non tutti gli vicinati meritano lo stesso livello di esplorazione
• First-improvement e best-improvement: due strategie di ottimizzazione
• Perché i metodi esatti raggiungono rapidamente i propri limiti

Perché ripartire da zero è raramente una buona strategia

In teoria, ricostruire interamente la pianificazione dopo ogni modifica potrebbe sembrare l’approccio migliore. In pratica, tuttavia, questa strategia diventa rapidamente impraticabile a causa dell’esplosione del numero di soluzioni da esplorare, dei tempi di calcolo che comporta e dell’instabilità che genera nelle attività operative sul campo.

Come spiega Ammar Oulamara, responsabile Ricerca e Sviluppo di AntsRoute:

“Un motore che opera in tempo reale non può ricostruire integralmente i percorsi a ogni nuovo evento. Il costo di calcolo e l’instabilità che ne deriverebbe sarebbero troppo elevati.”

È proprio per questo motivo che i motori moderni utilizzano approcci di warm-start.

Il warm-start: partire da una soluzione già ottimizzata

Il principio del warm-start consiste nell’utilizzare la pianificazione corrente come punto di partenza per l’ottimizzazione. Anziché ricercare una soluzione completamente nuova, il motore cerca di migliorare localmente una soluzione già coerente, limitando al tempo stesso le degradazioni che potrebbero compromettere l’equilibrio complessivo del sistema.

Questo approccio presenta diversi vantaggi significativi:

• drastica riduzione dello spazio di ricerca;
• mantenimento di una buona stabilità operativa;
• tempi di risposta compatibili con il tempo reale;
• e una limitazione delle riorganizzazioni non necessarie.

Come sottolinea Ammar Oulamara:

“Il warm-start consente al motore di concentrare la propria potenza di calcolo sulle aree realmente interessate da una modifica della pianificazione.”

Questa logica modifica profondamente il modo in cui il problema viene esplorato.

Un inserimento non viene mai valutato in modo isolato

Quando viene inserita una nuova attività τ, il motore non si limita a valutarne il costo marginale immediato. Questo inserimento può infatti avere ripercussioni sull’intera pianificazione, modificando:

• i vincoli temporali;
• i margini di sicurezza;
• l’equilibrio tra i percorsi;
• le future capacità di riorganizzazione;
• la compattezza geografica della pianificazione.

Il motore deve quindi esplorare non solo l’inserimento in sé, ma anche le riorganizzazioni locali che esso può rendere possibili in una fase successiva. È proprio questa capacità di migliorare una soluzione esistente a costituire il ruolo dei meccanismi di ricerca locale.

La ricerca locale: esplorare il vicinato di una soluzione

Nei problemi di ottimizzazione dei percorsi, è impossibile esplorare in modo esaustivo tutte le soluzioni possibili. I motori moderni lavorano quindi principalmente attraverso l’esplorazione degli vicinati.
Il principio è semplice:

• partire da una soluzione esistente;
• applicare localmente determinate trasformazioni;
• quindi verificare se la nuova soluzione migliora la pianificazione.

In AntsRoute, l’algoritmo di ricerca locale si basa su diversi operatori che consentono di esplorare efficacemente questi vicinati.

Relocate: spostare un’attività in una posizione migliore

L’operatore relocate è uno dei meccanismi più fondamentali della ricerca locale. Consiste nel rimuovere un’attività da un percorso per reinserirla in un’altra posizione, all’interno dello stesso percorso oppure in un percorso diverso.
Questa operazione consente in particolare di:

• recuperare margini temporali;
• riequilibrare i carichi;
• o ridurre alcuni effetti di propagazione.

Nei sistemi dinamici, relocate svolge spesso un ruolo centrale nelle riottimizzazioni rapide, poiché consente di migliorare localmente una pianificazione con un costo di calcolo relativamente contenuto.

Or-opt: spostare sequenze di attività

In alcuni casi, spostare una singola attività non è sufficiente per ripristinare un buon equilibrio della pianificazione. Il motore utilizza quindi operatori di tipo Or-opt, che consistono nello spostare una sequenza di 1, 2 o 3 attività consecutive verso un’altra posizione del percorso o della pianificazione.

Questo approccio è particolarmente utile quando:

• più attività presentano una forte coerenza geografica;
• oppure quando una riorganizzazione locale richiede di preservare determinate continuità del percorso.

Come spiega Ammar Oulamara:

“Spostare un gruppo coerente di attività può talvolta ristabilire l’equilibrio della pianificazione in modo molto più efficace rispetto a una serie di modifiche isolate.”

2-opt e 3-opt: ristrutturare la geografia dei percorsi

Gli operatori 2-opt e 3-opt perseguono un obiettivo diverso. Consistono nell’invertire determinate sottosequenze di un percorso al fine di migliorarne la struttura geografica.

Questi meccanismi consentono in particolare di:

• eliminare gli incroci;
• migliorare la compattezza geografica;
• o ridurre le deviazioni non necessarie.

Risultano particolarmente efficaci quando:

• i percorsi diventano frammentati;
• oppure quando una successione di inserimenti ne compromette progressivamente la struttura spaziale.

Anche nei sistemi fortemente vincolati dal fattore tempo, la qualità geografica dei percorsi rimane un elemento essenziale della robustezza operativa.

Cross-exchange: riequilibrare più percorsi simultaneamente

Nei sistemi soggetti a forti vincoli, alcuni inserimenti non possono essere assorbiti mediante semplici aggiustamenti locali. Il motore deve quindi riorganizzare simultaneamente più percorsi mediante operatori di cross-exchange, che consistono nello scambio di interi segmenti tra percorsi al fine di ripristinare un migliore equilibrio complessivo.

Questi meccanismi diventano particolarmente utili quando:

• alcune risorse critiche si avvicinano alla saturazione;
• più percorsi diventano fragili dal punto di vista temporale;
• le possibilità di riorganizzazione locale si riducono progressivamente.

Il motore non ragiona quindi più soltanto a livello di un singolo percorso, ma dell’intera pianificazione, al fine di individuare i riequilibri più pertinenti.

Non tutti gli vicinati meritano lo stesso costo di calcolo

Esplorare in profondità ogni possibile inserimento sarebbe eccessivamente oneroso dal punto di vista del calcolo. Il motore deve quindi stabilire delle priorità e concentrare la propria potenza di calcolo sulle soluzioni più promettenti. In AntsRoute, questa esplorazione si basa su una gerarchia di intorni che consente di adattare progressivamente la profondità della ricerca in funzione della qualità degli inserimenti valutati.

Vicinato di grado 1

Il primo livello di vincinato si basa esclusivamente su semplici modifiche locali effettuate all’interno dello stesso percorso. L’obiettivo è filtrare rapidamente gli inserimenti manifestamente sfavorevoli, limitando al tempo stesso il costo di calcolo.

Vicinato di grado 2

A questo livello, il motore consente scambi tra percorsi e operazioni di riequilibrio più ampie. Questa esplorazione permette di valutare le conseguenze globali di determinati inserimenti e di individuare miglioramenti che non sarebbero visibili a livello di un singolo percorso.

Vicinato di grado 3

Il terzo livello di vicinato consente riorganizzazioni molto più profonde, che possono includere ristrutturazioni multi-giorno o modifiche significative della pianificazione. Queste esplorazioni, caratterizzate da un costo di calcolo più elevato, sono riservate agli inserimenti più promettenti o alle situazioni particolarmente vincolate.

Questa gerarchia di vicinati consente di allocare in modo efficiente la potenza di calcolo, adattando la profondità della ricerca alla qualità delle soluzioni individuate.

First-improvement e Best-improvement

Uno degli aspetti più importanti della ricerca locale riguarda la strategia utilizzata per esplorare il vicinato di una soluzione. Generalmente vengono adottati due approcci principali: first-improvemente best-improvement.

First-improvement

Con la strategia first-improvement, il motore accetta il primo miglioramento individuato durante l’esplorazione. Questo approccio offre diversi vantaggi:

• convergenza rapida;
• basso costo di calcolo;
• buona efficacia nelle prime fasi dell’esplorazione.

Best-improvement

Al contrario, la strategia best-improvement consiste nell’esplorare l’intero vicinato prima di selezionare la soluzione che offre il maggior miglioramento. Generalmente consente di:

• ottenere una soluzione di qualità superiore;
• esplorare più a fondo le possibilità di ottimizzazione.

Di contro, il suo costo di calcolo è sensibilmente più elevato.
Come spiega Ammar Oulamara:

“La scelta tra first-improvement e best-improvement dipende in larga misura dalla densità della pianificazione e dal budget di calcolo disponibile.”

In AntsRoute, il motore alterna dinamicamente queste due strategie in funzione della qualità delle soluzioni osservate, del livello di convergenza raggiunto e del grado di saturazione della pianificazione.

Perché i metodi esatti raggiungono rapidamente i propri limiti

I problemi di ottimizzazione dinamica dei percorsi appartengono a una classe di problemi combinatori particolarmente complessi. Man mano che i vincoli si moltiplicano, i percorsi diventano più densi e gli eventi in tempo reale si fanno più frequenti, la dimensione dello spazio di ricerca aumenta considerevolmente. I metodi esatti diventano quindi rapidamente incompatibili con le esigenze operative, sia in termini di tempi di calcolo sia di reattività.

Come ricorda Ammar Oulamara:

“Il motore non ricerca la soluzione teoricamente perfetta. Cerca la migliore soluzione utilizzabile entro un tempo di calcolo compatibile con le esigenze operative.”

È proprio per questo motivo che i motori moderni si basano su una combinazione di euristiche, meccanismi di warm-start, operatori di ricerca locale e strategie di esplorazione adattative, al fine di produrre rapidamente soluzioni robuste e realmente efficaci dal punto di vista operativo.

Conclusione

Nei moderni sistemi di ottimizzazione dei percorsi, la difficoltà non consiste soltanto nel costruire una pianificazione iniziale. La vera sfida è riuscire a farla evolvere continuamente senza comprometterne la robustezza, la stabilità o la qualità operativa.

Il warm-start, gli operatori di ricerca locale e l’esplorazione di vicinati multipli consentono proprio di rispondere a questa esigenza. Nella logistica dell’ultimo miglio, un percorso non è mai completamente definitivo: deve poter adattarsi costantemente ai cambiamenti sul campo, mantenendo al contempo un elevato livello di prestazioni operative.