Districting for routing with consistency

Vehicle routing problems have been studied for several decades. With the ultimate goal of profitability, the most common objective pursued by these problems is the minimization of costs, in the form of total travel time, total travel distance or number of vehicles employed to satisfy the demand. Recent developments in the logistics industry, however, have shown that strategies that seek only to minimize costs are inefficient compared to strategies that seek to stimulate profits by focusing on customer satisfaction. A satisfied customer will build a strong bond with his company, staying with it for a long time and generating more profits. These strategic changes have been translated into the world of operations research with the concept of consistency: consistent vehicle routing problems try to route vehicles so that each customer is always served by the same driver at the same time of day. Consistency generates long-term benefits not only for the customers themselves, but also for the driver who serves them. The latter will in fact develop a stronger personal relationship with his customers and become familiar with the area in which they live, thus being able to move faster within it. This thesis proposes a framework to solve the problem of consistent routing of vehicles. In a scenario with services to be performed over a time horizon of several days, each with its own release and due date, and a finite set iof drivers, this framework will generate a series of daily routing plans in which the concept of consistency is maintained. The problem will be dealt with in 2 phases: in the first phase, areas of competence will be created for each driver by solving a new variant of the p-median problem, the multi-period balanced p-median problem. In the second phase, a vehicle routing problem will be solved for each day, taking into account the previously created districts. For both problems an exact formulation and a heuristic algorithm are proposed and tested with data from a real case study, producing reasonable results in term of routes and computational time.

I problemi di instradamento dei veicoli sono stati studiati per diversi decenni. Con l'obiettivo finale della profittabilità, l'obiettivo più comune perseguito da questi problemi è la minimizzazione dei costi, sotto forma di tempo totale di viaggio, distanza totale di viaggio o numero di veicoli impiegati per soddisfare la domanda. I recenti sviluppi nel settore della logistica, tuttavia, hanno dimostrato che le strategie che cercano solo di minimizzare i costi sono inefficienti rispetto alle strategie che cercano di stimolare i profitti concentrandosi sulla soddisfazione del cliente. Un cliente soddisfatto costruirà un forte legame con la sua azienda, rimanendo con essa per lungo tempo e generando maggiori profitti. Questi cambiamenti strategici sono stati tradotti nel mondo della ricerca operativa con il concetto di coerenza: i problemi di instradamento coerente dei veicoli cercano di instradare i veicoli in modo tale che ogni cliente sia sempre servito dallo stesso autista alla stessa ora del giorno. La coerenza genera benefici a lungo termine non solo per i clienti stessi, ma anche per l'autista che li serve. Quest'ultimo, infatti, svilupperà un rapporto personale più forte con i suoi clienti e acquisirà familiarità con la zona in cui vivono, potendo così muoversi più velocemente al suo interno. Questa tesi propone un framework per risolvere il problema dell'instradamento coerente dei veicoli. In uno scenario con servizi da svolgere su un orizzonte temporale di più giorni, ciascuno con una propria data di rilascio e scadenza, e un insieme finito di autisti, questo framework andrà ad instradare giorno per giorno i veicoli mantenendo il concetto di coerenza. Il problema verrà affrontato in 2 fasi: nella prima fase verranno create aree di competenza per ogni autista risolvendo una nuova variante del problema delle p-mediane, il problema delle p-mediane bilanciato multiperiodo. Nella seconda fase, verrà risolto un problema di instradamento dei veicoli per ogni giorno, tenendo conto dei distretti precedentemente creati. Per entrambi i problemi viene proposta una formulazione esatta e un algoritmo euristico che viene testato con i dati di un caso di studio reale, producendo risultati ragionevoli in termini di instradamento e di tempo di calcolo. .