In large-scale Capacitated Vehicle Routing Problems (CVRPs), customer partitioning into smaller independent routing problems is a common solution. While this significantly reduces computational complexity, independently constructed routing solutions may leave some customer demands unserved even when sufficient resources exist elsewhere in the fleet. We present Collaborative Routing Constructors (CoRC), a routing framework that allows independently solved subproblems to exchange customers and vehicles during optimization instead of relying solely on a fixed partition or a subsequent global re-optimization stage.
Computational experiments on AGS benchmark instances and synthetic instances containing up to 200,000 customers compare CoRC against independent routing, post-routing global re-optimization, and state-of-the-art end-to-end routing frameworks. Across all evaluated partitioning strategies, CoRC consistently constructs feasible routing solutions where competing partition-based methods do not. Furthermore, it remains effective on problem instances for which the evaluated end-to-end routing frameworks did not produce solutions under the same computational budget. These results demonstrate that collaboration between routing subproblems provides a robust and scalable approach for feasible large-scale route construction.
Blogger's Review: The introduction of CoRC offers a fresh perspective on solving large-scale vehicle routing problems. By enhancing resource utilization through collaborative optimization, it overcomes the limitations of isolated solutions. Its effectiveness in real-world applications, especially in handling complex customer demands, showcases its significant potential.