An exact and heuristic approach for the traveling salesman problem with drone and variable drone speeds selection

Drone-assisted deliveries have gained popularity in the last few years thanks to the recent technological advances. In this thesis, we propose an exact and heuristic method for the Flying Sidekick Traveling Salesman Problem with Variable Drone Speeds Selection (FSTSP-VDS), an extension of the Flying Sidekick Traveling Salesman Problem (FSTSP) in which the standard vehicle (e.g., a truck) is combined with a drone that can fly at variable speeds to deliver parcels to customers with the objective to minimize the completion time. In particular, we focus on the generic case in which the drone power consumption is modeled by a nonlinear function with respect to speed and weight. We show that if the drone energy-per-meter function is convex (and this is true for the most popular drone power consumption models in literature), then, the minimum and maximum feasible drone travel times can be computed using a generic convex optimization solver. Under this assumption, we present the first Mixed Integer Linear Programming (MILP) formulation for the FSTSP-VDS. The formulation we present has the advantage to be compact (i.e., it features a polynomial number of variables and constraints) and allows to solve instances with up to 25 customers. Furthermore, we propose a genetic heuristic method to tackle larger FSTSP-VDS instances. The quality of our heuristic method is validated in two ways. First, we compared it with the current state of the art FSTSP-VDS heuristic, obtaining an average improvement of 6%. Then, we tested our heuristic on the Traveling Salesman Problem with Drone (TSP-D), a nearly identical problem to the FSTSP in which the drone flying speed is fixed, and show that our method is the first heuristic that can find known optimal solutions of TSP-D instances with up to 39 customers. In particular, for a total of 227 TSP-D with known optimal solutions evaluated, the genetic algorithm was to able to find the optimal solution for 194 instances (85.5%), with an average optimality gap of only 0.30%

Grazie al rapido avanzamento tecnologico avvenuto negli ultimi anni, i sistemi di consegna via drone stanno diventando sempre più popolari. In questa tesi, proponiamo un metodo esatto e un metodo euristico per il problema del Flying Sidekick Traveling Salesman Problem with Variable Drone Speeds Selection (FSTSP-VDS), un'estensione del Flying Sidekick Traveling Salesman Problem (FSTSP) in cui un veicolo tradizionale (e.g., un furgone) è assistito da un drone che può viaggiare a velocità variabile con l'obiettivo di servire un insieme di clienti nel minore tempo possibile. In particolare, ci concentriamo sul caso generico in cui il consumo energetico del drone è carattererizzato da un modello non lineare rispetto alla velocità e al peso trasportato. Mostriamo che, se la funzione che descrive il consumo di energia per metro del drone è convessa, allora, i tempi di percorrenza minimi e massimi del drone, possono essere calcolati utilizzando metodi standard di ottimizzazione convessa. Sotto questa ipotesi, proponiamo la prima formulazione di Programmazione Lineare Intera Mista (PLIM) per il problema del FSTSP-VDS. La formulazione che proponiamo ha il vantaggio di essere compatta (i.e., ha un numero polinomiale di variabli e vincoli) e permette di risolvere all'ottimo instanze fino a 25 clienti. Inoltre, presentiamo un algoritmo genetico per poter affrontare istanze con un numero maggiore di clienti. La qualità dell'algoritmo genetico proposto viene validato in due modi. Prima, lo compariamo con lo stato dell'arte per il problema del FSTSP-VDS, ottenendo un miglioramento medio del 6%. Infine, testiamo l'algoritmo genetico sul problema del Traveling Salesman Problem with Drone (TSP-D), un problema analogo al FSTSP in cui la velocità del drone è fissata, e mostriamo che il metodo sviluppato è il primo euristico capace di trovare soluzioni ottime note per istanze con 39 clienti. In particolare, delle 227 instanze valutate, 194 sono state risolte all'ottimo (85.5%), ottenendo un scarto medio complessivo dello 0.30%.