Modelli per l’ottimizzazione dell’instradamento dei veicoli in un caso reale

Dopo aver costruito il modello matematico per il problema preso in esame si possono avere diversi approcci per risolverlo e ottenere la soluzione ottima del problema. Si può pensare di risolvere il problema con dei Metodi esatti, ma generalmente i problemi di instradamento in sistemi di raccolta o distribuzione presentano dimensioni molto elevate e queste rendono improponibile la risoluzione con algoritmi di tipo esatto. Si può avere una risoluzione attraverso la Programmazione matematica, cioè risolvere una formulazione rilassata del problema, non ottenendo però così un risultato ottimo dovendo fissare un termine di penalità. Entrambi i metodi possono essere implementati con un calcolatore. Gli approcci più interessanti e attualmente più studiati sono le Procedure Euristiche, in grado di fornire soluzioni di buona qualità in tempi di calcolo contenuti. Una possibile classificazione delle procedure euristiche è la seguente:

- Euristiche classiche : sviluppate a partire dagli anni ’60, hanno una struttura generalmente
semplice, tempi di calcolo contenuti, agevole implementazione e adattamento ai diversi vincoli operativi. Fanno parte di questa categoria gli algoritmi di tipo “raggruppa prima, instrada dopo” e “instrada prima, raggruppa dopo”, la procedura dei risparmi (di Clarke & Wright) e algoritmi di ricerca locale.

- Metaeuristiche : sviluppate a partire dagli anni ’90, sono più complesse, con tempi di elaborazione maggiori e delicate operazioni di taratura. Procedure di questo tipo sono quelle di ricerca Tabù.

Interessante dal punto di vista della tecnica utilizzata sono i seguenti due algoritmi:

Algoritmi “Raggruppa prima, Instrada dopo”
Questo tipo di algoritmi risolve l’NRP in due fasi distinte: nella prima si assegna ad ogni veicolo v=1,..,NV un sottoinsieme dei nodi di servizio Nv ⊂ N, nella seconda fase invece si risolve il problema per ogni veicolo sul sottografo relativo ai nodi di Nv, costruendo la rotta ottimale del veicolo. La definizione dei sottoinsiemi dei veicoli può essere effettuata manualmente oppure con algoritmi più complessi e che non sempre forniscono risultati migliori.

Algoritmi “Instrada prima, Raggruppa dopo”

Anche questi algoritmi risolvono il problema in due fasi simmetricamente a quelli precedenti. Nella prima fase infatti si risolve il problema relativo a tutti i nodi costruendo un unico ciclo che comprenda tutti i nodi, rilassando i vincoli operativi; nella seconda fase invece si decompone il ciclo in v ≤ NV rotte ammissibili dal problema, ciascuna associata ad un veicolo e avente origine e termine nel nodo deposito e in grado di visitare un sottoinsieme di clienti. La decomposizione della rotta anche qui può avvenire manualmente o con una procedura (proposta da Beasily) ma che, come quelli precedenti, non sembra fornire risultati migliori.
Utili per lo sviluppo di questi algoritmi ma anche nella risoluzione del problema con altri metodi sono dei principi per un buon routing e scheduling