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

Introduction

The rapid expansion of last-mile delivery services has highlighted a significant physical limitation in aerial robotics: the thrust-to-weight ratio of small drones. While large drones can carry heavy packages, they are expensive and logistically cumbersome. An alternative approach is collaborative transportation, where a swarm of smaller, cost-effective drones works together to lift a single heavy object. This paper introduces the under-capacitated Vehicle Routing Problem (uVRP), a novel framework designed to address the unique synchronization and coordination challenges inherent in multi-drone logistics.

The uVRP Framework

Traditional Vehicle Routing Problems (VRP) typically assume a one-to-one mapping between vehicles and deliveries. In the uVRP scenario, a single payload may exceed the capacity of any individual drone, necessitating simultaneous collaboration. This introduces three primary complexities:

  1. Synchronization: Multiple drones must converge at a specific location and time to initiate a lift.
  2. Waiting Times: The efficiency of the swarm is constrained by the "slowest" participant; drones must often remain idle while awaiting their partners.
  3. Deadlock Prevention: Circular dependencies—where Drone A waits for Drone B while Drone B waits for Drone A—must be mathematically precluded to ensure mission completion.

The SAGA Algorithm

To solve the uVRP, the authors developed SAGA (Simulated Annealing + Genetic Algorithm), a hybrid optimization approach integrated into an Alternating Minimization (AM) framework. The problem is decomposed into two distinct sub-problems:

  • Mission Order Optimization: Using Simulated Annealing (SA), the algorithm explores various delivery sequences to minimize total travel distance and time, effectively avoiding local optima through stochastic "shuffling."
  • Drone Assignment Optimization: A Genetic Algorithm (GA) evolves populations of drone-to-task assignments. This ensures that every mission has sufficient collective lift while balancing the workload across the swarm.

To prevent deadlocks, the authors implement "node potentials," enforcing a strict partial order on missions to ensure that circular waiting dependencies cannot form.

System Architecture

The proposed solution is not merely theoretical; it is designed for real-time execution. The system integrates the uVRP solver with a high-level mission scheduler and low-level path planning.

System architecture for the uVRP solver and mission execution.

As shown in the architecture, the uVRP Solver generates the optimal mission plan, which is then processed by a Mission Scheduler. This scheduler coordinates with individual drones and an Informed RRT* path planner to ensure collision-free trajectories at a 5 Hz update rate.

Experimental Results

The system was validated through both large-scale synthetic benchmarks and physical hardware experiments.

Simulation Performance

In synthetic tests involving up to 20 drones and 300 missions, SAGA demonstrated superior performance, reducing total operational costs by approximately 16% compared to random assignment baselines. Furthermore, the mathematical model showed high predictive accuracy; in a 5-drone setup, the predicted mission time of 202 seconds closely matched the 208 seconds observed in physics-enabled simulations.

Hardware Validation

Physical experiments were conducted using Crazyflie 2.0 nano-quadcopters. These drones utilized a Lighthouse positioning system and specialized magnetic docking mechanisms to interface with payloads.

Hardware setup featuring a quadcopter with a magnetic docking station for collaborative payload transport.

The hardware trials successfully demonstrated the swarm's flexibility: drones were able to collaborate to lift heavy payloads and subsequently decouple to handle smaller, individual tasks independently.

Conclusion

This research provides a robust foundation for collaborative drone logistics. By formalizing the uVRP and introducing the SAGA algorithm, the authors demonstrate that swarms of small drones can effectively replace larger, more expensive vehicles for heavy-lift tasks. Future work will focus on extending the framework to heterogeneous swarms and developing decentralized solvers to support thousands of concurrent agents in dynamic environments.

Summary updated

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