Drone Scheduling Optimization Considering Capacity and Reliability of Batteries

Drones, or Unmanned Aerial Vehicles (UAVs), are aircrafts without a human pilot that are typically controlled and programmed by ground base centers. Although drone utilization is becoming more commonplace in recent years, there are a few challenges and drawbacks that should be addressed in drone scheduling such as: 1) limited weight capacity, 2) accurate estimation of battery consumption, 3) drone failures during the flight, 4) long and continuous flight missions, and 5) battery capacity degradation over time. This research aims to address these challenges in three separate studies. The first contribution of my dissertation addresses the first and second challenges. Experimental data shows that the battery consumption rate (BCR) is a linear function of the payload amount. Any design of a parcel delivery system using drones then needs to consider the BCR, which includes strategic planning of the delivery system and operational planning for a given region. We developed a minimum set covering model for the strategic planning and a mixed integer linear programming problem (MILP) for the operational planning. In order to improve the computational time of the operational planning model, a variable preprocessing algorithm and several upper and lower bounds on the objective function are proposed. The results indicate the sequence of visiting customers impacts the remaining charge and that 3 out of 5 (60%) flight paths are not feasible if the BCR is not considered. The proposed computational techniques enabled us to solve all the tested problems, which was not possible without them. Among the three proposed lower bound generation methods, the network configuration method computationally outperformed the other two methods. The second contribution of my dissertation addresses the third challenge. Drone-based delivery network is considered to ship parcels to customers. In the event of failures, the demand of the corresponding customers would not be satisfied which is how we account for the lost demand. Therefore, drone failures in scheduling can be considered to minimize the expected loss of demand (ELOD). An optimization model (drone delivery schedule with drone failures (DDS-F)) is developed to determine the assignment of drones to customers along with the corresponding delivery sequence. A Simulated Annealing (SA) heuristic algorithm is proposed to solve the model to reduce the computational time. The proposed SA features a fast initial solution generation based on the Petal algorithm, a binary integer programming model for path selection, and a local neighborhood search algorithm to find better solutions. Numerical results showed that the DDS-F model outperformed the well-known Makespan problem in reducing the ELOD by 23.6% on a test case. The proposed SA algorithm was able to reduce the computational time by 44.35%, on average, compared with the exact algorithm. The third contribution of my dissertation addresses the last two challenges. A new approach based on a concept of autonomous battery swap stations (ABSSs) is proposed to reduce the time for battery swap in a drone-aided surveillance mission. A MILP model is proposed to determine the ABSS location based on the limitation on the revisiting gap between two consecutive visits at surveillance waypoints. A battery management algorithm is also proposed to optimize the number of batteries to be secured at a station for each drone with the goal of minimizing the battery acquisition and replacement cost over a planning horizon. The impact of average and standard deviation of battery State of Charge (SOC) on capacity degradation is considered in this study. Numerical results show that delay in charging the battery can improve the battery end-of-life by 15.6% when charging is delayed 25% more for a test case. The results also show that the battery end-of-life is a linear function of number of required batteries.