The travelling salesman problem with one truck and one drone

In the past few years, unmanned aerial vehicles (UAVs), also known as drones, have been accepted as part of a new logistics method in the commercial areas. Drones are used in synchronized way with trucks for delivering goods to customers to improve service quality and reduce shipping cost. A modern last-mile delivery concept, in which a truck cooperates with a drone to deliver, leads to a new variant of the Traveling Salesman Problem (TSP). In this thesis, we studied a TSP with one truck and one drone (TSP-TD) to minimize the completion time of deliveries. We presented four different versions of this problem with the same objective function. Then, we proposed four mixed integer linear programming formulations to solve these problems. We verified our solutions with several benchmark instances provided from the literature. Numerical results obtained on various instances with different sizes and characteristics are presented. Results show how much the quality of solutions is affected and improved. As future work, a heuristic method can be developed to solve larger instances.

Negli ultimi anni i veicoli aerei senza equipaggio (UAV), noti anche come droni, sono stati accettati come parte di un nuovo metodo logistico nelle aree commerciali. I droni sono utilizzati in modo sincronizzato con i camion nella consegna della merce ai clienti per migliorare la qualità del servizio e ridurre costi di spedizione. Un concetto moderno di consegna dell'ultimo miglio, dove un camion collabora con un drone per effettuare consegne, porta a una nuova variante del problema del commesso viaggiatore (TSP). In questa tesi, abbiamo studiato un problema di commesso viaggiatore con un camion e un drone (TSP-TD) per minimizzare i tempi di completamento delle consegne. Abbiamo presentato quattro diverse versioni di questo problema con la stessa funzione obiettivo. Quindi, abbiamo proposto quattro formulazioni di programmazione lineare intera mista per risolvere questi problemi. Abbiamo verificato le nostre soluzioni con diverse istanze di riferimento fornite dalla letteratura. Sono presentati risultati numerici ottenuti su numerose istanze con dimensioni e caratteristiche diverse. I risultati mostrano quanto la qualità delle soluzioni è influenzata e migliorata.