Capacitated Vehicle Routing with Target Geometric Constraints
This work addresses routing efficiency for robotics and logistics, but it is incremental as it adapts a known problem to a new context.
The paper tackles the capacitated vehicle routing problem by extending it to include 2D region targets instead of point locations, which is more realistic for robotics applications like aerial delivery, and develops fast algorithms that are optimal for convex regions and outperform greedy approaches in simulations.
We investigate the capacitated vehicle routing problem (CVRP) under a robotics context, where a vehicle with limited payload must complete delivery (or pickup) tasks to serve a set of geographically distributed customers with varying demands. In classical CVRP, a customer location is modeled as a point. In many robotics applications, however, it is more appropriate to model such "customer locations" as 2D regions. For example, in aerial delivery, a drone may drop a package anywhere in a customer's lot. This yields the problem of CVRG (Capacitated Vehicle Routing with Target Geometric Constraints). Computationally, CVRP is already strongly NP-hard; CVRG is therefore more challenging. Nevertheless, we develop fast algorithms for CVRG, capable of computing high quality solutions for hundreds of regions. Our algorithmic solution is guaranteed to be optimal when customer regions are convex. Numerical evaluations show that our proposed methods significantly outperform greedy best-first approaches. Comprehensive simulation studies confirm the effectiveness of our methods.