A scheduling decision support model for minimizing the number of drones with dynamic package arrivals and personalized deadlines. (1st April 2021)

• Record Type: Journal Article
• Authors: Liu, Chuang; Chen, Huaping; Li, Xueping; Liu, Zeyu
• Is Part Of: Expert systems with applications. Volume 167(2021)
• Publication Date: 2021-04-01
• Subjects: Unmanned aerial vehicles (UAVs) -- Drone delivery -- Decision support -- Scheduling -- Genetic algorithm; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2020.114157
• Languages: English
• ISSNs: 0957-4174

Abstract

Abstract: Unmanned Aerial Vehicles (UAVs, commonly known as drones) hold great potential to reduce operational costs and guarantee on-time delivery of packages. This paper aims to minimize the number of drones used in a depot, in which each package has its own customized release time, distance to the depot, and personalized deadline. For decision-makers, it is difficult to determine the optimal number of drones to ensure that all packages can be delivered before the corresponding deadline. We propose a mixed integer programming model formulate the problem. Due to the NP-hardness of the problem, a scheduling decision support model with a genetic algorithm (SDSMGA) is developed to address the problem. A fitness function that can determine the minimum number of drones required by a package delivery sequence is proposed. We develop a swap-based correction algorithm to correct unqualified individuals in SDSMGA. Experimental results show that compared with CPLEX for small instances, SDSMGA can obtain solutions of the same quality or sub-optimal solutions. Computational results among SDSMGA, Estimation of Distribution Algorithm (EDA), and Particle Swarm Optimization (PSO) indicate that SDSMGA can effectively and efficiently address the problem. As the number of packages increases, SDSMGA outperforms the other two algorithms. Sensitivity analysis shows that the smaller the dense factor, or the more extensive the service radius, the more drones are needed. Highlights: We formulate a MIP model to determine the optimal number of drones with deadline constraints. We introduce a scheduling decision support model with a genetic algorithm (SDSMGA). We propose a deterministic approach to select the most proper drone for all packages. We develop a swap-based correction algorithm. We conduct computational experiments to evaluate the performance of the SDSMGA.