A Metaheuristic Solution for the Capacitated Vehicle Routing Problem: Empirical Evaluation of Flexible Capacity Constraints via Ant Colony Optimisation

Sintesi Tecnica: Una Soluzione Metaeuristica per il Problema del Veicolo con Capacità Limitata (CVRP)

1. Definizione del Problema e Contesto
Lo studio affronta un problema reale di Capacitated Vehicle Routing Problem (CVRP) derivante da un'operazione di raccolta di materie prime in entrata in Colombia. La rete logistica è composta da un deposito centrale a Guadalajara de Buga (Valle del Cauca) che serve trenta centri di distribuzione situati in diverse regioni colombiane (coste, altipiani andini e zone industriali). L'operazione affronta cicli di domanda variabili (da 643 a 1.192 pacchi per ciclo) e utilizza una flotta omogenea di dieci camion Foton FRR Cummins.

Un vincolo operativo critico è la politica di capacità flessibile: sebbene la capacità nominale del veicolo sia $Q = 150$ pacchi, la politica aziendale autorizza un sovraccarico controllato del 5%, stabilendo una capacità di pianificazione effettiva di $Q_{eff} = 157,5$ pacchi. La pianificazione degli itinerari deve essere eseguita su reti stradali non euclidee derivate da OpenStreetMap (tramite OSMnx), dove le complessità topologiche (corridoi montani, strade a senso unico) creano una significativa asimmetria tra le distanze euclidee e i costi di percorrenza effettivi.

Il sistema di pianificazione attuale, "Rout Now", impiega un'architettura "cluster-first, route-second": partiziona i nodi in 10 cluster geografici utilizzando il k-means (basato su coordinate piatte) e successivamente sequenzia ogni cluster indipendentemente utilizzando il Simulated Annealing (SA). Questo approccio produce un utilizzo eterogeneo della flotta (35%–90%) e impiega sistematicamente tutti i 10 veicoli, anche quando i limiti inferiori teorici suggerirebbero che 6–8 veicoli sarebbero sufficienti.

2. Metodologia
La ricerca propone e valuta una metaeuristica di Ottimizzazione a Colonia di Formiche (ACO) progettata per operare sul grafo completo dei nodi attivi senza una precedente partizione geografica.

• Formulazione Matematica: Il problema è modellato come un Programma Lineare Intero Misto (MILP) utilizzando la formulazione di Miller–Tucker–Zemlin (MTZ) per l'eliminazione dei sottotour. Il vincolo di capacità è esplicitamente rilassato a $Q_{eff} = 157,5$ per modellare la politica di sovraccarico all'interno della logica di ottimizzazione.
• Architettura ACO:
  • Costruzione: Le formiche costruiscono percorsi multi-veicolo iterativamente. Un elemento differenziante è il meccanismo di masking dinamico: l'insieme dei nodi successivi fattibili ($F_k$) viene filtrato in tempo reale per garantire che il carico accumulato non superi $Q_{eff}$. Ciò consente all'algoritmo di "impacchettare" i nodi in modo efficiente, sfruttando il margine del 5% solo quando necessario per evitare l'apertura di un nuovo percorso.
  • Probabilità di Transizione: La probabilità di selezionare un nodo dipende dalle tracce di feromone ($\tau$) e dalla visibilità euristica ($\eta = 1/C_{ij}$). Data l'elevata varianza nei costi stradali colombiani (deviazione standard del 47% rispetto alla media), il peso euristico ($\beta = 2,0$) è stato calibrato per dominare il peso del feromone ($\alpha = 1,0$), dando priorità all'efficienza dei costi immediati.
  • Meccanismo di Aggiornamento: Si applicano le standard regole di evaporazione e deposito, rinforzando gli archi che contribuiscono a soluzioni a basso costo e alta consolidazione.
• Disegno Sperimentale:
  • Scenari: Dieci distinti scenari operativi (S-1 a S-10), rappresentanti un mese completo di cicli di pianificazione, sono stati estratti da dati reali dell'azienda.
  • Ripetizione: Ogni scenario è stato eseguito 20 volte indipendentemente con diversi seed casuali per isolare la varianza stocastica.
  • Confronto con il Baseline: I risultati dell'ACO sono stati confrontati con il baseline "Rout Now" (k-means + SA) utilizzando matrici di distanza OSMnx identiche per garantire la validità interna.
  • Validazione Statistica: Il test non parametrico di Wilcoxon signed-rank è stato applicato alle medie delle distanze totali delle 20 esecuzioni per scenario per testare la significatività statistica.

3. Risultati Chiave
L'approccio ACO ha dimostrato miglioramenti sistematici e statisticamente significativi rispetto al baseline in tutti i dieci scenari:

• Riduzione della Flotta: Nello scenario con la domanda più alta (S-3; 1.192 pacchi), l'ACO ha ridotto la flotta attiva da 10 veicoli (baseline) a 8 veicoli, corrispondendo al limite inferiore teorico ($\lceil 1192/157,5 \rceil = 8$). In tutti gli scenari, la flotta attiva è stata ridotta di circa il 20%.
• Distanza e Costo:
  • Distanza Totale: Ridotta in media del 20,05% (con un intervallo tra il 19,97% e il 20,25%). In S-3, la distanza è scesa da 11.023 km a 8.790,5 km.
  • Costo del Carburante: Risparmio stimato del 16,05% nello scenario critico (circa 941.340 COP per ciclo).
  • Tempo Operativo: Ridotto del 20,02%.
• Utilizzo della Capacità: L'ACO ha raggiunto una consolidazione quasi perfetta, portando l'utilizzo medio della capacità dal ~79,47% (baseline) al 99,50% in S-3. I percorsi nella soluzione ACO operavano tra il 96% e il 101% della capacità nominale, con percorsi specifici che sfruttavano il margine di sovraccarico del 5% per evitare la necessità di un nono veicolo.
• Significatività Statistica: Il test Wilcoxon signed-rank ha prodotto una statistica $W=0$ (tutte le differenze favorivano l'ACO) con un p-value $< 0,01$, rifiutando l'ipotesi nulla di uguaglianza delle mediane e confermando la robustezza dei miglioramenti.

4. Significato e Contributi
Il documento rivendica tre contributi scientifici primari:

1. Valutazione Empirica dei Vincoli Flessibili: Documenta come la modellazione esplicita di un vincolo di capacità flessibile ($Q_{eff}$) all'interno di una metaeuristica costruttiva permetta una consolidazione del carico coordinata che è strutturalmente impossibile per le architetture di pre-partizionamento. Lo studio dimosta che la tolleranza del 5% non è solo un margine di sicurezza, ma una leva strategica per la riduzione della flotta quando gestita dinamicamente.
2. Robustezza nella Topologia del Mondo Reale: Il lavoro fornisce prove del fatto che le metaeuristiche ispirate alla natura (specificamente l'ACO) superano le classiche euristiche "cluster-first, route-second" in reti stradali complesse e non euclidee. Lo studio evidenzia che la pre-partizione geografica (k-means) non riesce a tenere conto delle asimmetrie della rete stradale, mentre l'ACO opera sullo spazio dei costi reali.
3. Identificazione del Meccanismo Causale: Il documento identifica il "masking dinamico" dei nodi non fattibili durante la costruzione del percorso come il meccanismo causale del successo. Ciò consente all'algoritmo di eseguire un "impacchettamento efficiente" della domanda, sfruttando organicamente il margine di sovraccarico per minimizzare il numero di percorsi, una capacità assente nell'architettura del baseline basata su cluster geografici fissi.

5. Limitazioni e Lavori Futuri
Gli autori osservano che lo studio è limitato a un contesto industriale specifico senza finestre temporali (VRPTW) o vincoli sulle ore di guida. Le future direzioni di ricerca proposte includono:

• Estendere il modello al VRPTW per incorporare gli orari di ricezione.
• Affrontare l'incertezza della domanda tramite il VRP stocastico (SVRP).
• Sviluppare formulazioni multi-obiettivo (ad es. minimizzazione delle emissioni di CO₂) utilizzando algoritmi evolutivi.
• Integrare il nucleo ACO come microservizio per test A/B controllati all'interno dei sistemi logistici esistenti.