A top-down approach for the Dynamic Vehicle Routing Problem

A causa della sua complessità e delle sue innumerevoli applicazioni pratiche, il problema di routing di veicoli (VRP) è uno dei più importanti e studiati problemi di ottimizzazione combinatoria. La tesi si pone l'obiettivo di proporre e analizzare un algoritmo per la risoluzione di un problema di routing di veicoli dinamico (DVRP), in cui gli ordini arrivano in maniera dinamica con l'evolvere del tempo. In particolare, lo studio è motivato da un'applicazione pratica relativa ad una grossa azienda fornitrice di mobili, che necessita di un strategia per stabilire quali clienti contattare e quindi servire in un certo giorno, e quali rimandare ai giorni successivi. L'algoritmo proposto sfrutta un approccio top-down per definire il pool di clienti da servire. Nello specifico, a partire dall'intera coda di clienti vengono selezionati quelli meno promettenti attraverso l'utilizzo di una metrica basata sul criterio dell'extra miglia.