Online Drone Scheduling for Last-Mile Delivery

Delivering a parcel from the distribution hub to the customer’s doorstep is called the last-mile delivery step in delivery logistics. In this paper, we study a hybrid truck-drones model for the last-mile delivery step, in which a truck moves on a predefined path carrying parcels and drones deliver the parcels. We define the online drone scheduling problem, where the customer’s requests for the parcels appear online during the truck’s movement. The objective is to schedule a drone for every request, aiming to minimize the number of drones used subject to the battery budget of the drones and compatibility of the schedules. We propose a 3-competitive deterministic algorithm with O(logn) worst-case time per request, where n is the total number of requests being served at any instance. We further improve the competitive ratio to 2.7 with the same time complexity. We also introduce online variable-size drone scheduling problem (OVDS). Here, all customer requests are available in advance, but the drones with different battery capacities appear online, and the objective is the same as the online drone scheduling problem. We propose a (2α+1)-competitive algorithm for the OVDS problem with running time O(nlogn), where n is the total customer requests and α is the ratio of maximum to minimum drone battery capacities.