The Vehicle Routing Problem with Drones and Flexibility Demands

In recent years, the Vehicle Routing Problem, with its variants handling complex realistic constraints, continues to be a key area of research, reflecting its enduring importance in modernized societies. Nevertheless, less attention has been paid to the variant with the flexibility of customer demands. This paper introduces the problem of addressing the integration of drones into the existing transportation system to maximize the profit of distributing freight during a limited working time by allowing flexibility in the delivered quantity. We propose a Mixed Integer Linear Programming (MILP) formulation and a genetic algorithm (GA) to solve the problem. To assess the proposed algorithm, we create the benchmark instances of the problem from published data sources. Experimental results on the instances show a significantly better performance of our proposal than MILP. Moreover, we evaluate our approach by comparing its performance with existing solutions in published closely related works.