Hybrid genetic-sweep algorithm to solve the vehicle routing problem with drones

Energy consumption has become a crucial problem in the design of vehicle routing problems, hence the need to use another delivery method powered by batteries. Unmanned aerial vehicles have become fundamental tools in tasks for which man has limited skills that prevent a superlative optimization of time. The increasing use of drones by commercial companies such as Amazon, Google, and DHL has given birth to a new variant of vehicle routing problem (VRP) called VRP with drones (VRPD) which has a positive influence on the environment. Where vehicles and drones are used to deliver packages or goods to customers. In VRPD, vehicles and drones make dependent or independent deliveries. In the case of a dependent delivery, at a given point (customer or depot) the drone takes off from a vehicle to serve a customer and then return to travel with the same vehicle, as long as the capacity and endurance constraints for a drone are satisfied. In the other case, each type of vehicle travels independently to others. A MILP model is presented to describe the problem, and then we confirm the formulation via a CPLEX software with small instances. We propose a hybrid genetic algorithm to solve the VRPD. Experiments are carried out on the instances taken from the literature in different settings. The results show the performance of the proposed algorithm to solve this variant. (C) 2020 Elsevier B.V. All rights reserved.