通过协作优化提升大规模路径规划的可行性与效率
Robust Feasible Route Construction through Collaborative Partition Optimization
- 子问题间动态交换客户与车辆，打破固定分区限制
- 在20万客户规模下，所有策略中唯一实现全程可行解
- 适合资源紧张但需保证全覆盖的大规模物流场景
大规模带容量约束的车辆路径问题（CVRP）通常通过将客户划分为更小的子问题独立优化来求解。尽管这显著降低了计算复杂度，但独立构建的路径解可能因资源分配不均导致部分客户需求无法满足，即使车队整体资源充足。本文提出协同路径构造框架（CoRC），使独立求解的子问题在优化过程中可交换客户与车辆，无需依赖固定分区或后续全局重优化。在包含最多20万客户的AGS基准实例与合成实例上的实验表明，相比独立求解、事后全局重优化以及当前最先进的端到端框架，CoRC在所有划分策略下均能持续生成可行解，而其他基于分治的方法无法做到。此外，在相同计算预算下，现有端到端框架未能求解的部分实例，CoRC仍能有效求解。结果证明，子问题间的协同机制为大规模可行路径构造提供了鲁棒且可扩展的新范式。
原文摘要 · Abstract (English)
Large-scale Capacitated Vehicle Routing Problems (CVRPs) are commonly solved by partitioning customers into smaller routing problems that can be optimized independently. While this substantially reduces computational complexity, independently constructed routing solutions may leave some customer demand unserved even when sufficient resources exist elsewhere in the fleet. We present Collaborative Routing Constructors (CoRC), a routing framework that enables independently solved subproblems to exchange customers and vehicles during optimization rather than 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。