Delivering a parcel from the distribution hub to the customer's doorstep is called the \textit{last-mile delivery} step in delivery logistics. In this paper, we study a hybrid {\it 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 \textsc{online drone scheduling} problem, where the truck moves in a predefined path, and the customer's requests appear online during the truck's movement. The objective is to schedule a drone associated with every request 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 using the next-fit strategy and 2.7-competitive algorithms using the first-fit strategy for the problem with $O(\log n)$ worst-case time complexity per request, where $n$ is the maximum number of active requests at any time. We also introduce \textsc{online variable-size drone scheduling} problem (OVDS). Here, we know all the customer's requests in advance; however, the drones with different battery capacities appear online. The objective is to schedule customers' requests for drones to minimize the number of drones used. We propose a $(2\alpha + 1)$-competitive algorithm for the OVDS problem with total running time $O(n \log n)$ for $n$ customer requests, where $\alpha$ is the ratio of the maximum battery capacity to the minimum battery capacity of the drones. Finally, we address how to generate intervals corresponding to each customer request when there are discrete stopping points on the truck's route, from where the drone can fly and meet with the truck.


    Access

    Download


    Export, share and cite



    Title :

    Online Drone Scheduling for Last-mile Delivery



    Publication date :

    2024


    Type of media :

    Preprint


    Type of material :

    Electronic Resource


    Language :

    English




    Last-Mile Drone Delivery: Past, Present, and Future

    Hossein Eskandaripour / Enkhsaikhan Boldsaikhan | DOAJ | 2023

    Free access

    Towards Fully Autonomous Drone-Based Last-Mile Delivery

    Imran, Navid Mohammad / Mishra, Sabya / Won, Myounggyu | ArXiv | 2021

    Free access

    DroneTalk: An Internet-of-Things-Based Drone System for Last-Mile Drone Delivery

    Chen, Kuan-Wen / Xie, Ming-Ru / Chen, Yu-Min et al. | IEEE | 2022



    CO2 emissions and delivery time of last‐mile drone delivery using trucks

    Hur, Sung Ho / Won, Minsu | Wiley | 2024

    Free access