Optimal Collaborative Transportation for Under-Capacitated Vehicle Routing Problems using Aerial Drone Swarms

Akash Kopparam Sreedhara, Deepesh Padala, Shashank Mahesh, Kai Cui, Mengguang Li, Heinz Koeppl

TL;DR

This paper introduces the under-capacitated Vehicle Routing Problem (uVRP), a new logistical framework where multiple drones must collaborate to transport payloads that exceed any single drone's capacity. The authors develop a hybrid optimization algorithm called SAGA (Simulated Annealing + Genetic Algorithm) to coordinate these swarms, successfully demonstrating the system both in high-fidelity simulations and with real-world nano-quadcopters.

What Problem Does This Paper Address?

As the demand for last-mile drone delivery grows, engineers face a physical bottleneck: battery and motor technology limit the "thrust-to-weight" ratio of small drones. To carry heavy packages, you usually need massive, expensive drones.

The alternative is collaborative transportation—using a swarm of smaller, cheaper drones to lift a single heavy object. However, this turns standard logistics into a nightmare of coordination. Traditional Vehicle Routing Problems (VRP) assume one vehicle per delivery. In the "under-capacitated" scenario (uVRP), the system must account for:

  1. Synchronization: Drones must arrive at the same place at the same time to lift a package.
  2. Waiting Times: Total mission time isn't just travel distance; it includes drones sitting idle while waiting for their partners.
  3. Deadlocks: If Drone A is waiting for Drone B to help with Package 1, while Drone B is waiting for Drone A to help with Package 2, the entire swarm freezes.

Methods

The authors propose a multi-objective optimization approach that balances total distance traveled (energy cost) against total time taken (opportunity cost). Their primary contribution is the SAGA algorithm, which operates within an Alternating Minimization (AM) framework.

  • The Split: The problem is decomposed into two parts: the Mission Order (the sequence of deliveries) and Drone Assignments (which specific drones handle which package).
  • Genetic Algorithm (GA): Used to optimize drone assignments. It evolves populations of "genotypes" representing which drones are assigned to which tasks, ensuring every package has enough "lift" to move.
  • Simulated Annealing (SA): Used to optimize the mission order. It "shuffles" the delivery sequence to find the most efficient path while avoiding local optima.
  • Deadlock Prevention: The authors use "node potentials" to enforce a strict partial order of missions, mathematically ensuring that circular waiting dependencies can never occur.
  • Physical Integration: The system was integrated with ROS2 and the Informed RRT* path planner for collision avoidance, using magnetic docking mechanisms for the physical drones to "grab" payloads.

Datasets

The paper does not use a standard public dataset, as uVRP is a newly defined problem. Instead, the authors evaluated their system using:

  • Synthetic Benchmarks: 100 randomly generated problem instances ranging from small (4 drones, 60 missions) to large (20 drones, 300 missions) within a 4m x 4m workspace.
  • Real-world Hardware: Experiments conducted using Crazyflie 2.0 nano-drones equipped with a Lighthouse positioning system.

Key Insights and Ideas

  • Collaboration as a Timing Constraint: In standard VRP, time is usually a function of distance. In uVRP, time is a complex variable because the "slowest" drone in a sub-group dictates the start of the mission.
  • The Pareto Frontier: There is no single "best" solution. By adjusting a scalarization parameter ($\mu$), the authors show a clear trade-off curve (Pareto frontier) between saving energy (shorter distance) and saving time.
  • Encoding Matters: By carefully choosing how to represent the solution (Table I), the authors made it possible to apply metaheuristics like GA and SA to a problem that is otherwise computationally intractable (NP-hard).

Key Results

  • Optimization Performance: SAGA consistently outperformed Random Assignment (RA) across all scales. For large-scale tests (20 drones, 300 missions), SAGA reduced the total cost by approximately 16% compared to the baseline.
  • Model Accuracy: The gap between the uVRP model’s predicted time and the actual time recorded in a physics-enabled simulation was remarkably small. For a 5-drone/25-mission setup, the predicted time was ~202s while the actual time was ~208s.
  • Hardware Validation: The authors successfully demonstrated two drones collaborating to lift a heavy payload, followed by those same drones splitting up to handle smaller, individual payloads—proving the flexibility of the swarm.

Limitations and Future Work

  • Homogeneous Swarms: The current model assumes all drones have the same capacity and velocity. While the authors claim extending this to heterogeneous swarms is straightforward, it wasn't the focus of this study.
  • Perfect Information: The algorithm assumes payload masses and locations are known in advance. In a real-world "search and rescue" or construction site, these variables might be unknown, requiring online system identification.
  • Centralization: The SAGA solver is centralized. As swarms grow into the hundreds or thousands, a decentralized approach—perhaps using Graph Neural Networks (GNNs) or Reinforcement Learning—would be necessary to maintain real-time performance.

Summary updated

Abstract

Swarms of aerial drones have recently been considered for last-mile deliveries in urban logistics or automated construction. At the same time, collaborative transportation of payloads by multiple drones is another important area of recent research. However, efficient coordination algorithms for collaborative transportation of many payloads by many drones remain to be considered. In this work, we formulate the collaborative transportation of payloads by a swarm of drones as a novel, under-capacitated generalization of vehicle routing problems (VRP), which may also be of separate interest. In contrast to standard VRP and capacitated VRP, we must additionally consider waiting times for payloads lifted cooperatively by multiple drones, and the corresponding coordination. Algorithmically, we provide a solution encoding that avoids deadlocks and formulate an appropriate alternating minimization scheme to solve the problem. On the hardware side, we integrate our algorithms with collision avoidance and drone controllers. The approach and the impact of the system integration are successfully verified empirically, both on a swarm of real nano-quadcopters and for large swarms in simulation. Overall, we provide a framework for collaborative transportation with aerial drone swarms, that uses only as many drones as necessary for the transportation of any single payload.
BibTeX
@inproceedings{sreedhara2024optimal,
  author = {Akash Kopparam Sreedhara and Deepesh Padala and Shashank Mahesh and Kai Cui and Mengguang Li and Heinz Koeppl},
  title = {{Optimal Collaborative Transportation for Under-Capacitated Vehicle Routing Problems using Aerial Drone Swarms}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2024},
  url = {https://openreview.net/forum?id=SQyJH8Bpme},
}
Figure