Optimizing Drone-Assisted Last-Mile Deliveries: The Vehicle Routing Problem with Flexible Drones

The ever-widening acceptance and deployment of drones in last-mile distribution continue to increase the need for planning and managing the delivery operations involving drones effectively. Motivated by the growing interest towards drone-assisted last-mile transportation, we study a hybrid delivery system in which (multiple) trucks and (multiple) drones operate in tandem. In particular, we introduce the vehicle routing problem with flexible drones (VRPFD), which seeks to find a set of delivery routes for a fleet of trucks and drones operating in synchronization, with the goal of minimizing the makespan, i.e., the return time of the very last vehicle (drone or truck) to the depot after completing its service. The VRPFD is fundamentally different from the majority of the vehicle routing problems with drones considered in the literature, because (1) drones are not dedicated to certain trucks, and (2) the trucks are allowed to visit the same location multiple times in our problem setting. We formulate the VRPFD as a mixed integer linear program on a time-space network, and present an efficient optimization algorithm based on a dynamic discretization discovery approach. We demonstrate the benefits of drone flexibility and the efficiency of the proposed solution approach through a detailed computational study performed on a newly generated set of benchmark instances. Our findings suggest that the flexible use of drones facilitates higher drone utilization and therefore results in makespan improvements. In clustered geographies, drone flexibility reduces the makespan by up to 12.12%, with an average of 5.39%. Our proposed solution approach is able to efficiently solve the VRPFD instances by making use of an intelligent lower bounding mechanism while keeping its subproblems small. Computational experiments reveal that it is able to reduce the solution time by up to a factor of 6.5 when compared to solving the VRPFD using a commercial solver. With additional computational experiments where we attempt to solve larger VRPFD instances within a time limit, we observe that our solution approach is able to find good bounds, even when directly solving the VRPFD with a commercial solver does not return a feasible solution.

Article

Download

View PDF