Riassunto analitico
In questa tesi di dottorato ci concentriamo sullo studio e sviluppo di algoritmi esatti ed euristici per risolvere "vehicle routing problems with pickups and deliveries" (VRPPD). In particolare, siamo interessati in varianti che hanno importanti applicazioni nel mondo reale.
Innanzitutto affrontiamo la classe "one-to-many-to-one single vehicle routing problems with pickups and deliveries" e ci concentriamo sul problema più studiato di questa classe, noto come "single vehicle routing problem with deliveries and selective pickups". Per risolvere questo problema, la maggior parte dagli approcci in letteratura è basato su formulazioni disaggregate, noi invece impieghiamo delle formulazioni aggregate. Mediante l'utilizzo di Benders Decomposition, valid inequalities e tecniche di ottimizzazione basate su framework di branch-and-cut, sviluppiamo algoritmi esatti che migliorano i risultati presenti in letteratura e ottengono soluzioni ottimali per tutte le istanze di riferimento. Abbiamo poi generalizzato gli algoritmi per risolvere diversi altri VRPPD, ad esempio i casi con split deliveries, dropoff intermedi, pickup obbligatori e l'uso di diversi veicoli. Infine, estendiamo i nostri approcci per risolvere due varianti di problemi della classe many-to-many single VRPPD. Queste due varianti si trovano comunemente nel contesto di bike sharing rebalancing e, per convalidare l'efficienza dei metodi proposti, sono utilizzate istanze reali.
Nella seconda parte della tesi studiamo un caso pratico di carpooling sorto in una azienda italiana, in cui lo scopo è quello di incoraggiare i propri dipendenti ad utilizzare il carpooling per ridurre i costi di trasporto e le emissioni di CO2. L'obiettivo è quello di minimizzare le emissioni mediante lo sviluppo di un'applicazione web integrata. L'applicazione è utilizzata dai dipendenti al fine di organizzare equipaggi per il carpooling di ogni giorno, in modo da raggiungere una destinazione comune. Cerchiamo possibili equipaggi mediante l'utilizzo di due formulazioni matematiche e due algoritmi euristici. Gli algoritmi euristici vengono poi integrati nell'applicazione web per fornire agli utenti soluzioni di carpooling. I risultati sperimentali nello scenario reale attestano un grande potenziale di risparmio di CO2 grazie all'utilizzo del carpooling.
Infine, studiamo un caso pratico di un problema di home attended delivery, incontrato da una grande azienda multi-utility italiana che fornisce servizi energetici, di gas e d'acqua in Italia. Questa azienda offre un'applicazione web in cui i clienti possono richiedere un servizio, scegliendo un intervallo di tempo per la sua prestazione. Una volta fatto questo, l'azienda dovrebbe creare le route che gli operatori devono fare al fine di minimizzare i costi. L'obiettivo è quello di valutare la qualità dei time slot schedules attualmente in vigore e proporre metodi per sostenere la creazione di nuove schedules che ottimizzino i costi di routing previsti. In pratica, il problema ha tre livelli: la decisione dei time slot schedules, la simulazione delle scelte dei clienti e la valutazione dei costi di routing. Per risolvere il secondo e il terzo livello proponiamo, rispettivamente, quattro strategie di simulazione e un algoritmo di branch-and-cut. Un algoritmo adaptive large neighborhood search viene utilizzato per risolvere il primo livello, usando le altre due componenti per valutare le soluzioni trovate ad ogni iterazione. I risultati sperimentali indicano che, in un grande insieme di istanze basate su casi reali, lo schedule utilizzato dall'azienda può essere migliorato.
|
Abstract
In this Ph.D. thesis we focus on the study and development of efficient exact and heuristic algorithms to solve vehicle routing problems with pickups and deliveries. More specifically, we are interested in variants that have relevant real world applications.
We first address the class of one-to-many-to-one single vehicle routing problems with pickups and deliveries, and concentrate our efforts on the
most studied problem of this class, known as the single vehicle routing problem with deliveries and selective pickups.
While most exact approaches in the literature are based on disaggregated formulations, we focus instead on aggregated ones. Through the use of Benders Decomposition, valid inequalities, and tailored optimization techniques based on branch-and-cut frameworks, we develop exact algorithms that outmatch previous results in the literature and obtain proven optimal solutions for all benchmark instances.
We then generalize the algorithms to solve several other vehicle routing problems with pickups and deliveries, including the cases of split deliveries, intermediate dropoffs, mandatory pickups, and multiple vehicles.
Finally, we extend our approaches to solve two problem variants of the class many-to-many single vehicle routing problems with pickups and deliveries. These two variants are commonly found in the context of bike sharing rebalancing and real instances are used to validate the efficiency of the proposed methods.
The second part of the thesis focus on a practical carpooling problem found in an Italian company, whose aim is to encourage its employees to use carpooling to reduce transportation costs and CO2 emissions.
The objective is to minimize emissions by developing an integrated web application to be used by the employees of this company to organize carpooling crews on a daily basis, so as to reach a common destination. We look for possible crews by the use of two mathematical formulations and two heuristic algorithms.
The heuristic algorithms are then embedded into the web application to provide users with carpooling solutions. Experimental results on the real scenario attest for a great potential in CO2 savings by the use of carpooling.
Finally, we approach a practical home attended delivery problem found in a large Italian multi-utility company that provides energy, gas and water services throughout the country.
This company offers an online application in which customers are able to request services by choosing a time slot of their like. Once this is done, the company has to route vehicles to serve the requests minimizing costs.
The objective is to evaluate the quality of the schedules currently in place and propose methods to support the creation of new ones that optimize the expected routing costs.
In practice the problem has three levels: the decision of the time slot schedules; the simulation of customers choices; and the evaluation of the expected routing costs.
To solve the second and third levels we propose, respectively, four simulation strategies and an exact branch-and-cut algorithm.
An adaptive large neighborhood search algorithm is then used to solve the first level, while using the other two components to evaluate the solutions found.
Experimental results indicate that the schedule used by the company can be consistently improved on a large set of instances based on historical data.
|