A Simulated Annealing Algorithm for the Vehicle Routing Problem with Drones
Mahdi Moeini  1@  , Oliver Wendt  2  , Marius Schummer  2  
1 : Statistiques, Optimisation, Probabilités
Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux
2 : Kaiserslautern University of Technology

In this study, we focus on the Vehicle Routing Problem with Drones (VRPD), which is considered as an extension to the classical Vehicle Routing Problem (VRP). In the VRPD, we want to serve a given set of customers in the shortest possible time,
and for this purpose we use a mixed fleet of trucks and drones. We formulate the VRPD as a Mixed Integer Linear Program (MILP). Due to computational challenges of the model, MILP solvers can solve only small instances. To solve larger instances, we introduce a two-phase Simulated Annealing algorithm. To test our algorithm, we conducted extensive computational experiments on benchmark instances. Moreover, we investigate the impact of using drones on energy consumption of the delivery fleet. According to the numerical results, in addition to the efficiency our algorithm, we observe important benefits of using drones on reduction of makespan and energy consumption.


Personnes connectées : 1 Vie privée
Chargement...