Communications of the ACM
Should Santa Deliver by Drone?
Santa has always run a one-sleigh operation, but a new analysis could help him speed deliveries and save energy, if he ever decided to add a drone to his route.
"People have considered combinations of ground vehicles and drones for deliveries in the past," says Kaarthik Sundar of the Information Systems and Modeling group at Los Alamos National Laboratory, "but they focused on trucks that would move from one point to the next, park while the drones visited various nearby locations, and then wait for the drones to return before moving on. We instead propose solutions for a truck that moves continuously, while a drone flies out and returns to the truck as it proceeds along its route."
Sundar is coauthor of "Coordinated Air-Ground Vehicle Routing with Timing Constraints," to be presented later this month at the Sixth Indian Control Conference in Hyderabad, India. Just in time for the holidays, should Santa attend.
Sundar and his coauthors formulate the problem of a ground vehicle (a sleigh, perhaps, in Santa's case, although not a flying one) and a companion drone that must visit a set of locations (or, say, chimneys). The goal is to find a feasible route that takes into account the fact that drones are speedy, but have limited fuel and capacity, and that trucks are relatively slow, but have long ranges and large payloads.
A basic version of the so-called Variable Neighborhood Search algorithm identifies good solutions to the problem. The approach doesn't provide the most optimal route for a truck and drone, but finds promising routes quickly.
The study focuses primarily on surveillance scenarios involving a ground vehicle that serves as a moving base for a drone that flies out to collect data and returns to the ground vehicle to upload data and refuel. But Sundar points out that the problem is essentially the same for a delivery service truck and a drone dropping of packages.
Coauthor P.B. Sujit, of Indraprastha Institute of Information Technology in Delhi, will present the study at the ICC. Additional collaborators are David W. Casbeer and Satyanarayana Gupta Manyam from Air Force Research Laboratory, Wright Patterson Air Force Base, in Dayton, Ohio.
No entries found