Riassunto analitico
La consegna dei droni sta diventando sempre più popolare negli ultimi anni per diversi motivi: si possono raggiungere zone inaccessibili per altri tipi di veicoli e zone in stato di emergenza, si possono ridurre i costi di consegna, i tempi di consegna e anche l'impatto ambientale, in quanto l'uso di tutti i veicoli tradizionali a benzina verrebbe ridotto a favore dell'uso di droni alimentati a batteria. Tuttavia, quando si introduce questo nuovo tipo di veicoli, i modelli di ottimizzazione associati alla consegna dei pacchi devono essere modificati, tenendo conto sia dei veicoli tradizionali come i camion che di quelli più innovativi, i droni. Questa tesi presenta il lavoro svolto presso la Vrije Universiteit di Amsterdam in merito allo studio del Traveling Salesman Problem with Multiple Drones, dove più droni e un camion lavorano in tandem per soddisfare le richieste dei clienti, la formulazione di un modello matematico e lo sviluppo di un metodo di soluzione esatta che possa risolvere questo complesso problema in tempi ragionevoli. Lo scopo di questa tesi è quello di indagare il TSP-MD e migliorare le tecniche di risoluzione esistenti risolvendo casi di medie dimensioni. Questa tesi presenta una revisione della letteratura sui problemi di consegna dei droni. Per formulare il TSP-MD viene proposto un modello compatto di Programmazione Lineare MILP (Mixed-Integer Linear Programming) e diverse famiglie di disuguaglianze valide. Inoltre, viene illustrato un esatto approccio di decomposizione basato sul MILP compatto e su un algoritmo branch-and-cut. Infine, gli esperimenti computazionali mostrano risultati interessanti: il metodo di risoluzione proposto può risolvere istanze con un massimo di 24 clienti ad una comprovata ottimalità, migliorando le prestazioni dei metodi esatti esistenti che possono risolvere problemi simili solo con un massimo di dieci clienti. Questo lavoro è l'oggetto di un paper scientfico.
|
Abstract
Drone delivery is becoming increasingly popular in recent years for several reasons: inaccessible areas for other types of vehicles and areas in a state of emergency can be reached, delivery costs, delivery times, and also environmental impact can be reduced, as the use of all traditional petrol-powered vehicles would be lowered in favor of the use of battery-powered drones. However, when introducing this new type of vehicle, the optimization models associated with parcel delivery must be modified, taking into account both traditional vehicles such as trucks and the more innovative ones, drones. This thesis presents the work done at the Vrije Universiteit Amsterdam regarding the study of the Traveling Salesman Problem with Multiple Drones, where multiple drones and a truck work in tandem to fulfill the customers' requests, the formulation of a mathematical model and the development of an exact solution method that can solve this complex problem in a reasonable time. The aim of this thesis is to investigate the TSP-MD and improve existing resolution techniques solving medium size instances. This thesis presents a literature review on drone delivery problems. A compact Mixed-Integer Linear Programming (MILP) model and different families of valid inequalities are proposed to formulate the TSP-MD. Moreover, an exact decomposition approach based on the compact MILP and a branch-and-cut algorithm is illustrated. Finally, computational experiments show valuable results: the solution method proposed can solve instances with up to 24 customers to proven optimality, improving the performance of existing exact methods that can solve similar problems with up to ten customers only. This work is the object of a scientific paper.
|
