Real-Time Vehicle Routing: Solution Concepts, Algorithms and Parallel Computing Strategies - Ghiani, Guerriero, Laporte, Musmanno

I problemi di instradamento (VRP - Vehicle Routing Problems) sono una tematica di rilievo nella gestione logistica sia nel settore privato che pubblico. Essi consistono nel determinare le rotte ottimali per i veicoli, data una serie di vincoli. I vincoli più comuni impongono che il carico trasportato da un singolo veicolo non sia superiore alla sua capacità totale, che la durata totale della rotta non ecceda un dato limite e che vengano rispettate le finestre temporali di servizio associate ad ogni nodo da visitare. I problemi di instradamento su vaste aree geografiche prevedono che ai veicoli venga assegnata un’attività alla volta; su aree ridotte, le attività sono di durata inferiore (più brevi di un turno lavorativo) e una rotta è costruita come sequenza di attività. Esistono differenti tipologie di problemi che devono essere risolti in tempo reale. Si elencano le applicazioni principali che motivano la nostra ricerca in campo VRP.

  • Gestione dinamica delle flotte. Alcune applicazioni su larga scala richiedono che i mezzi vengano impiegati per raccogliere o consegnare beni. Ottimizzare queste operazioni può condurre a un risparmio considerevole
  • Sistemi di distribuzione vendor-managed. Nei sistemi vendor-managed le compagnie di distribuzione stimano i livelli di inventario del cliente in modo tale da rifornirlo prima dell’esaurimento scorte. La domanda è quindi nota a priori ed è considerata statica. In ogni caso, siccome la domanda è incerta, alcuni clienti (in genere una percentuale ridotta) possono esaurire le loro scorte e necessitare di forniture urgenti.
  • Corrieri. I corrieri che percorrono lunghe distanze devono raccogliere i colli in uscita prima di portarli presso un terminal remoto e consolidare i carichi. Allo stesso modo i carichi provenienti dai terminal remoti devono essere distribuiti localmente. Molte richieste sono dinamiche e devono essere soddisfatte nella stessa giornata, laddove possibile.
  • Compagnie di soccorso e riparazione. Alcune compagnie forniscono servizio di soccorso e riparazione (soccorso auto in avaria, riparazione dispositivi, ecc.).
  • Sistemi a chiamata. I sistemi di strasporto a chiamata forniscono servizio a persone attraverso coppie origine-destinazione. Gli utenti possono prenotare una corsa con almeno un giorno di anticipo (caso off-line) oppure con pochi minuti di anticipo (caso real-time).
  • Servizi d’emergenza. I servizi d’emergenza comprendono la polizia, i vigili del fuoco e le ambulanze. Per definizione tutti i clienti sono dinamici. Inoltre la frequenza della domanda è bassa e perciò i veicoli attraversano frequenti periodi di fermo macchina. In questo contesto è molto importante riposizionare i veicoli fuori servizio in modo tale da ancitipare eventuali domande future ed evitare ore di punta e traffico.
  • Servizio taxi. In ogni servizio taxi la maggior parte degli utenti è dinamica. Così come nei servizi d’emergenza, la ricollocazione dei mezzi fuori servizio è molto importante.