Collaborative Truck-Drone Delivery System
Supervisor: Dr. Maged M. Dessouky
Affiliated with Daniel J. Epstein Department of Industrial and Systems Engineering at University of Southern California
The logistics industry faces significant challenges in keeping up with evolving demand and supply conditions, especially in urban areas. Traffic congestion during peak hours makes on-time delivery hard. Moreover, time-sensitive products like emergency blood and medicine must be delivered to the customer at the desired time. Drones are a viable answer to urban logistics problems since they provide several benefits for package delivery. Drones are resilient to traffic delays since they function independently of road infrastructure, unlike conventional vehicles. Although there has been significant research interest in developing truck-drone routing algorithms, there is still a gap in developing models that allow for en route drone launching points and recovery points. That is, existing research primarily only considered a customer’s location as a potential point for drone launching and recovery. This work proposes a Mixed Integer Programming (MIP) formulation and a heuristic algorithm to solve the problem. The consideration of en route launching and recovery points in the truck-drone collaborative parcel delivery system showed a 6.58% improvement compared to discrete (customer) launching and recovery points in a small instance with 4 customers. A heuristic based on the Dynamic Programming and General Variable Neighborhood Search metaheuristic are used to handle large instances. A greedy heuristic is also proposed and continuous appriximation analysis has been condusted to derive an upper bound of the problem. The proposed algorithms can solve the system with 175 customers with a 4.6% optimality gap.