Cooperative Truck-Drone Scheduling Approach for Last-Mile Deliveries

We present our ongoing work on the cooperation between a truck and drones in a last-mile package delivery scenario. We model this application as an optimization problem where each delivery is associated with a cost (drone's energy), a profit (delivery's priority), and a time interval (launch and rendezvous times from and to the truck). We aim to find an optimal scheduling for drones that maximizes the overall profit subject to the energy constraints while ensuring that the same drone performs deliveries whose time intervals do not intersect. After seeing that this problem is NP-hard, we first devise an optimal Integer Linear Programming (ILP) formulation. We then design an optimal pseudo-polynomial algorithm using dynamic programming and a polynomial-time approximation algorithm that exploits optimal coloring on interval graphs for the single drone case. We also provide an approximation algorithm for the multiple drone case.