Scientific Program > Talks by Topic

The growth of last-mile delivery and demand for next- and same-day service is pushing logistics beyond traditional transportation management and supply chain analytics. One recent evolution in urban logistics involves the usage of unmanned aerial vehicle (drones) in the delivery process. Delivery by drones offers new possibilities, but also induces new challenging routing problems.
The problem of parcel delivery with drone has received increasing attention these last years. We consider the problem of combining K vehicles and M drones without synchronization between the vehicles and drones (vehicles perform classical delivery tours from the depot, while drones make back and forth trips to the depot). The objective is to minimize the makespan. We propose a solution approach based on dynamic programming which consists in an iterative three-steps heuristic. The first step builds a giant tour visiting all customers. In the second step, the giant tour is split in order to determine a set of vehicles tours (each vehicle tour following the order defined by the giant tour) and a set of customers assigned to drones. Thirdly, an improvement step performs some moves of customers between vehicle/vehicle or vehicle/drone. To ensure execution time efficiency, some bounding and heuristic-based mechanisms for controlling labels in step two are introduced. A branch&cut procedure helping to obtain optimal solutions for small size instances is also provided.
The results obtained are very promising. Experiments conducted confirm the efficiency of our heuristic and give some insights on this kind of drone delivery system.