With companies like Amazon and UPS exploring unmanned aircraft delivery as a shipping option sooner rather than later, the drone may soon become your preferred delivery method. Drones have a lot of advantages — faster delivery and traffic alleviation among them. But once the technology becomes more readily available, how will companies ensure that their drones are taking the most efficient routes through the sky?
This problem caught the eye of Donghyun (David) Kim, assistant professor of computer science at Kennesaw State University and an expert in computer algorithm optimization.
Motivated by the recent advances in drone technologies and the occurrences of several natural disasters such as the 2011 Tōhoku earthquake and tsunami in Japan, Kim started working on the potential of drone usage during urgent search and rescue operations.
Of course, Amazon plays a role in his interest, too. “I might also be attracted to this problem because I am a loyal customer (Prime Member) of Amazon.com. I always appreciate the benefit of quick delivery,” says Kim.
Kim designed a study to create an algorithm to quickly handle the logistics involved in multiple delivery trucks and drones launched from them. “This requires the joint problem of package assignment, truck route computation, and drone route computation at the same time under various objectives such as maximizing the amount of packages delivered within the day, or minimizing the amount of resources (e.g. trucks) to deliver a given set of packages,” says Kim.
The study used multiple drone trajectory plans and mathematical computer science models to figure out and optimize the best combination of drone and truck as they move concurrently. Often delivery paths between the truck and drone overlap, making the delivery inefficient and delayed. The issue becomes even more complex when you account for the drone returning to the moving vehicle after package delivery.
“Currently, each of logistics companies has its own way to assign packages to the delivery trucks and schedule their route to maximize their efficiency,” says Kim. “The core question of my research would be how much the current system can be improved given the investment for drone delivery capability. As of now, no one knows.”
Kim’s approximation algorithm could help companies like UPS, Fedex, and Amazon develop a trajectory for multiple delivery drones scenarios to ensure packages are delivered in the most efficient, time-saving manner.
“This joint schedule optimization problem is theoretically very difficult,” says Kim.
And does Kim see legal battles becoming a problem for drone technology in general? He says no — drone innovation will continue to move forward as long as legal hurdles are resolved at the same pace as technology advances.
“The hardware technology will evolve the fastest,” says Kim. “The software technology to control individual drones is following. Then, the coordination technology will come. At the end of the day, all related legal issues have to be cleared.”