A promising solution to coordinated vehicle/drone delivery to a grid of locations. The black curves are the routes the truck follows at 5 meters per second, and the blue lines inticate the route a drone takes while flying at 25 meters per second.
LOS ALAMOS, N.M., Nov. 26, 2019—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," said study coauthor 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 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.
Sundar's coauthor, Sujit PB of Indraprastha Institute of Information Technology in Delhi, will present the study at the Indian Control Conference, December 18-20, in Hyderabad, Telangana, India – just in time for the holidays, if Santa happens to attend the conference.
The work is a collaboration with David W. Casbeer and Satyanarayana Gupta Manyam from Air Force Research Laboratory, Wright Patterson Air Force Base, in Dayton, Ohio and Sujit PB of Indraprastha Institute of Information Technology in Delhi, India.
Publication: Coordinated Air-Ground Vehicle Routing with Timing Constraints, Indian Control Conference, 2019-132-18/2019-12-20 (Hyderabad, India)
