Drone Scheduling Optimization Considering Capacity and Reliability of Batteries

Simple item page
dc.contributor.advisorLim, Gino J.
dc.contributor.committeeMemberFeng, Qianmei
dc.contributor.committeeMemberLee, Taewoo
dc.contributor.committeeMemberRao, Jagannatha R.
dc.contributor.committeeMemberVipulanandan, Cumaraswamy
dc.creatorTorabbeigi, Maryam
dc.date.accessioned2021-08-13T19:46:14Z
dc.date.createdDecember 2020
dc.date.issued2020-12
dc.date.submittedDecember 2020
dc.date.updated2021-08-13T19:46:16Z
dc.description.abstractDrones, 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.
dc.description.departmentIndustrial Engineering, Department of
dc.format.digitalOriginborn digital
dc.format.mimetypeapplication/pdf
dc.identifier.citationPortions of this document appear in: Torabbeigi, Maryam, Gino J. Lim, and Seon Jin Kim. "Drone delivery scheduling optimization considering payload-induced battery consumption rates." Journal of Intelligent & Robotic Systems 97, no. 3 (2020): 471-487.; Torabbeigi, Maryam, Gino J. Lim, and Seon Jin Kim. "Drone delivery schedule optimization considering the reliability of drones." In 2018 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 1048-1053. IEEE, 2018.
dc.identifier.urihttps://hdl.handle.net/10657/8099
dc.language.isoeng
dc.rightsThe author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. UH Libraries has secured permission to reproduce any and all previously published materials contained in the work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s).
dc.subjectDrone
dc.subjectUnmanned Aerial Vehicle (UAV)
dc.subjectPath Planning
dc.subjectBattery Consumption Rate
dc.subjectExpected Loss of Demand
dc.subjectSimulated Annealing
dc.subjectAutonomous Battery Swap Station
dc.subjectBattery Degradation
dc.titleDrone Scheduling Optimization Considering Capacity and Reliability of Batteries
dc.type.dcmiText
dc.type.genreThesis
local.embargo.lift2022-12-01
local.embargo.terms2022-12-01
thesis.degree.collegeCullen College of Engineering
thesis.degree.departmentIndustrial Engineering, Department of
thesis.degree.disciplineIndustrial Engineering
thesis.degree.grantorUniversity of Houston
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
TORABBEIGI-DOCTORALTHESISEDD-2020.pdf
Size:
4.46 MB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.43 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.82 KB
Format:
Plain Text
Description:
Download

Collections

Published ETD Collection