A two-stage stochastic optimization model for synchronized two-echelon routing problems

Sintesi Tecnica: Un Modello di Ottimizzazione Stocastica a Due Stadi per Problemi di Routing Sincronizzato a Due Echelons

Definizione del Problema
Questo studio affronta la complessità dell'incertezza nella logistica urbana, concentrandosi specificamente sui sistemi di Trasporto Integrato Terra-Acqua (IWLT). Il problema centrale è il Problema di Routing di Veicoli a Due Echelons, Multi-viaggio e con Sincronizzazione dei Satelliti (2E-MVRP-SS). In questo sistema, i Veicoli Elettrici Leggeri per il Trasporto Merci (LEFV) operano sul primo echelon (strade) per raccogliere merci dai clienti e trasferirle alle imbarcazioni (secondo echelon) presso nodi satellite. Il sistema opera senza opzioni di stoccaggio presso i satelliti, richiedendo una rigorosa sincronizzazione spazio-temporale tra LEFV e imbarcazioni.

La sfida principale affrontata è la propagazione dei ritardi causati da tempi di transhipment incerti presso i satelliti. Queste incertezze, derivanti da fattori regionali come la congestione del traffico o variazioni operative, possono interrompere le operazioni sincronizzate, portando a ritardi nelle consegne ai clienti, aumento dei costi operativi e riduzione dell'affidabilità. Lo studio si rivolge specificamente a scenari di logistica inversa (ad esempio, raccolta di rifiuti, resi) dove la tempestività del servizio è critica per minimizzare i costi di inventario e il disagio dei clienti.

Metodologia
Gli autori propongono un framework di ottimizzazione stocastica a due stadi con un problema di ricorso a variabili intere miste per gestire queste incertezze.

1. Formulazione a Due Stadi:

   • Primo Stadio (Master Problem): Le decisioni riguardano i percorsi dei LEFV e l'assegnazione dei compiti di trasferimento ai satelliti prima della realizzazione dei ritardi. Questo stadio dà priorità a tempi di servizio affidabili per i ritiri. Il modello assume che i LEFV visitino il satellite più vicino come approssimazione iniziale.
   • Secondo Stadio (Ricorso/Subproblema): Una volta realizzati specifici scenari di ritardo, vengono intraprese azioni correttive. Ciò comporta la riassegnazione delle operazioni di transhipment a diversi satelliti e il re-routing delle imbarcazioni per mitigare l'impatto dei ritardi. Le programmazioni dei LEFV per il servizio ai clienti rimangono fisse per onorare gli orari promessi, mentre la logistica via acqua viene ri-ottimizzata.

2. Approccio Algoritmico:

   • Per gestire la non-convessità della funzione di costo del secondo stadio e la natura di variabili intere miste del problema, gli autori impiegano un metodo L-shaped adattato con tag combinatori di Benders.
   • L'algoritmo itera tra un master problem rilassato e subproblemi per ogni scenario.
   • I tag di ammissibilità (feasibility cuts) assicurano che le decisioni del primo stadio permettano soluzioni ammissibili nel secondo stadio.
   • I tag di ottimalità (optimality cuts) approssimano il costo atteso del secondo stadio.
   • Viene utilizzato un approccio di campionamento basato su scenari per rappresentare le incertezze regionali. I ritardi presso i satelliti sono modellati come variabili con distribuzione normale, discretizzate in un insieme finito di scenari ($N$) per garantire la trattabilità computazionale pur mantenendo la stabilità.

3. Configurazione Sperimentale:

   • Il modello è stato testato su piccole istanze di rete (10 nodi di ritiro, 4 satelliti) derivate da istanze modificate di Solomon VRPTW.
   • Sono stati confrontati due design di sistema: 2E-Flexible (le imbarcazioni agiscono come depositi mobili, sincronizzati con i LEFV) e 2E-Stationary (posizioni delle imbarcazioni fisse).
   • Le prestazioni sono state valutate rispetto a un baseline deterministico (senza ritardi) e a un approccio stocastico a due stadi.

Contributi Chiave

• Modellazione Innovativa della Sincronizzazione: Questo è il primo studio che affronta l'impatto dei ritardi dei satelliti sulla sincronizzazione dei veicoli in un sistema a due echelon con capacità di stoccaggio nulla, uno scenario che richiede un'elevata coordinazione spazio-temporale.
• Framework di Ricorso Stocastico: Il documento propone un modello di programmazione stocastica a due stadi con ricorso a variabili intere miste specificamente per il 2E-MVRP-SS. Utilizza tagli di Benders combinatori all'interno di un metodo di enumerazione per gestire la non-convessità del secondo stadio.
• Analisi Comparativa della Flessibilità: Lo studio fornisce un confronto quantitativo tra sistemi di trasporto flessibili (imbarcazioni mobili) e sistemi stazionari sotto incertezza, dimostrando il valore della flessibilità nel mitigare la propagazione dei ritardi.

Risultati

• Riduzione dei Costi: Il modello di programmazione stastica proposto ha ridotto i costi totali attesi del 37% in tutte le istanze rispetto a un approccio deterministico che assume l'assenza di ritardi.
• Stabilità degli Scenari: L'approccio di generazione degli scenari ha dimostrato stabilità; la varianza degli scenari all'interno del campione è diminuita all'aumentare del numero di scenari, stabilizzandosi intorno ai 30 scenari.
• Impatto della Topologia di Rete:
  • Per le reti di domanda Raggruppate (Clustered - C), il sistema integrato ha mantenuto l'efficienza con un aumento minimo dei costi (vicino allo 0%) sotto incertezza.
  • Per le reti Casuali (Random - R), l'approccio stocastico ha ottenuto i maggiori risparmi rispetto alle strategie deterministiche, riducendo i costi attesi fino al 43% in specifiche istanze, localizzando meglio i punti di ritiro sensibili ai ritardi.
• Prestazioni del Sistema (Flessibile vs. Stazionario):
  • Il sistema 2E-Flexible ha superato significativamente il sistema 2E-Stationary in termini di affidabilità e quota modale.
  • Sotto incertezza, il sistema stazionario ha subito un forte aumento dei tempi di percorrenza stradale e dei ritardi (ad esempio, il ritardo è aumentato a 26 unità temporali nelle istanze RC), mentre il sistema flessibile ha mantenuto bassi i ritardi (9 unità temporali) e ha mantenuto una quota modale più equilibrata tra trasporto stradale e acqueo.
  • Il sistema flessibile ha mitigato efficacemente il rischio di aumento dei costi di percorrenza stradale, dimostrando che la ricollocazione delle unità di stoccaggio (o in questo caso, dei punti di transhipment) non può eguagliare le prestazioni dei servizi di navigazione flessibili in termini di congestione e affidabilità.

Significatività e Rivendicazioni
Il documento afferma che l'incorporazione dell'incertezza nella pianificazione offline è essenziale per l'affidabilità e l'efficacia dei costi della logistica urbana multimodale, particolarmente in contesti dove la competizione per lo spazio urbano limita le opzioni di stoccaggio. Lo studio dimostra che i sistemi flessibili, dove le imbarcazioni agiscono come depositi mobili sincronizzati con i LEFV, offrono una resilienza superiore contro i ritardi di transhipment rispetto ai sistemi a posizione fissa.

Gli autori concludono che, sebbene il modello proposto sia computazionalmente intensivo, i guadagni osservati in piccole istanze suggeriscono che l'ottimizzazione stocastica può migliorare significativamente l'affidabilità del servizio e ridurre la quota modale "green" (uso della strada) nella logistica urbana. Notano che il lavoro futuro potrebbe utilizzare il framework di enumerazione e pricing proposto per sviluppare euristiche per problemi su larga scala, ma lo studio attuale si concentra sulla validazione del framework teorico e sui benefici della flessibilità su reti piccole e risolvibili.