Proposal for a Model to Optimize the Vehicle Routing Problem With Drones That Perform Last-Mile Parcel Deliveries Focusing on Customer Satisfaction

The integration of drones for last-mile parcel deliveries tends to be a key factor in improving logistics services. Therefore, this work aims to define a Mixed Integer Linear Programming (MILP) model in order to study the Vehicle Routing Problem with Drones (VRP-D). The mathematical formulation is based on the Simultaneous Traveling Repairman Problem with Drone (STRPD), in which a vehicle with one or more drones departs from a depot to deliver parcels, aiming to reduce customer waiting times. Whereas in the STRPD the drone can only serve one customer per trip, in the proposed study the drone can serve multiple customers per trip. However, its endurance is limited by battery energy consumption, which depends on the weight carried by the drone. This problem is called the Simultaneous Traveling Repairman Problem with Drone with Multiple Visits (STRPDMV), and this work validated the mathematical model through the analysis of nineteen instances. Due to the inability to obtain results for some instances with twenty or more customers, a heuristic was developed to find feasible solutions within reduced processing times. Then, the results provided by the new model and the heuristic were compared and the analyses were presented. Additionally, another analysis performed was the impact of varying drone speed compared to vehicle speed, and vice-versa.