Routing drones with refuelling constraints

• Main Author: Lee, Gary Yanqing
• Other Authors: Huang Shell Ying
• Format: Final Year Project
• Language: English
• Published: 2018
• Subjects: DRNTU::Engineering::Computer science and engineering::Computer applications
• Online Access: http://hdl.handle.net/10356/76132
• Institution: Nanyang Technological University

Drone delivery reduces the time and cost of delivery which benefit both the company and the end-user. However, battery constraint is one of the main factor that limits the effective range of the drone and requires additional recharge during flight mission and this translates to additional costs. The environment states when the drone is executing the flight plan may change and affect the recharging plan and the overall cost therefore this report proposed heuristic Insert, Reduce, Exchange (heuristicIRE) algorithm that can generate a near optimal solution fast. The problem scenario is the drone starts from initial depot, visit a sequence of targets and recharge along the way if needed, and return to the initial depot. The average cost difference against the benchmark algorithm is less than 1% and the solution is generated in less than 10ms with a range of targets from 15 to 30 incremented by 5. The algorithm improves drone adaptability during re-planning of flight during flight execution when environment state changes and the reduced cost and time can bring more benefits to the company and the end-user in drone routing.