Adaptive Cluster-First Route-Second Decomposition for Industrial-Scale Vehicle Routing

📄 arXiv: 2606.31820v1 📥 PDF

作者: Oguzhan Karaahmetoglu, Hyong Kim

分类: cs.AI

发布日期: 2026-06-30

备注: 29 pages, 6 figures, 5 tables

💡 一句话要点

提出自适应聚类-优先路线-次级分解方法以解决工业规模车辆调度问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 车辆调度 聚类算法 大规模优化 机器学习 决策支持 物流管理 自适应系统

📋 核心要点

  1. 现有的CFRS方法依赖于固定的划分规则，导致在不同特征的实例中表现不一致，难以适应复杂的调度需求。
  2. 本文提出了一种自适应CFRS系统，利用大型语言模型进行高层决策，动态调整聚类和分解策略，以适应每个问题的特性。
  3. 在对合成和基准CVRP实例的评估中，提出的方法在性能和可扩展性上均优于现有方法，尤其在处理更大规模问题时表现突出。

📝 摘要（中文）

大规模的有容量限制的车辆调度问题（CVRP）通常采用聚类-优先路线-次级（CFRS）方法进行处理，该方法将调度实例分解为更小的可计算子问题。现有的分割方法通常依赖于固定的划分规则、预定义的优化目标或学习的策略，这可能导致在不同空间、需求和操作特征的实例中表现不一致。本文提出了一种自适应CFRS系统，将分解过程表述为一个迭代决策过程。该系统利用大型语言模型（LLM）作为高层决策者，分析不断变化的分解状态，并选择性地应用进一步的聚类、平衡和细化操作。实验结果表明，该方法在基准规模实例上表现出竞争力，同时在更大规模问题上展现出更好的可扩展性和稳健的调度质量。

🔬 方法详解

问题定义：本文解决的是大规模有容量限制的车辆调度问题（CVRP），现有方法在处理不同特征的实例时表现不一致，难以有效应对复杂的调度需求。

核心思路：提出的自适应CFRS系统将分解过程视为一个迭代决策过程，利用大型语言模型（LLM）作为决策者，动态分析分解状态并调整聚类策略，以实现容量感知的客户和车辆分区。

技术框架：该方法的整体架构包括初始聚类、动态决策和细化操作三个主要模块。首先进行初步的客户聚类，然后通过LLM分析当前状态，最后根据需求和特性进行进一步的聚类和优化。

关键创新：最重要的创新点在于将LLM引入到车辆调度的决策过程中，使得分解策略能够根据实时数据进行自适应调整，显著提高了处理复杂问题的能力。

关键设计：在设计中，关键参数包括聚类算法的选择、LLM的训练数据和决策逻辑，损失函数则侧重于调度效率和客户满意度的平衡。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，提出的方法在基准规模实例上表现出竞争力，并在处理高达500,000个客户的大规模问题时，展现出更好的可扩展性和稳健的调度质量，显著优于传统方法。

🎯 应用场景

该研究的潜在应用领域包括物流运输、城市配送和供应链管理等。通过自适应的调度策略，可以显著提高车辆利用率和客户服务水平，降低运营成本，具有广泛的实际价值和未来影响。

📄 摘要（原文）

Large-scale capacitated vehicle routing problems (CVRPs) are commonly addressed using cluster-first route-second (CFRS) approaches that split a routing instance into smaller, computationally tractable subproblems. Existing splitting methods typically rely on fixed partitioning rules, predefined optimization objectives, or learned policies, which may perform inconsistently across instances exhibiting different spatial, demand, and operational characteristics. In this work, we propose an adaptive CFRS system that formulates a decomposition procedure as an iterative decision-making process. Motivated by the recent success of large language models (LLMs) in reasoning and tool selection, the system employs an LLM as a high-level decision maker that analyzes the evolving decomposition state and selectively applies further clustering, balancing, and refinement operators. The proposed algorithm jointly partitions customers and vehicles, enabling capacity-aware clustering while adapting partitioning decisions to the characteristics of each problem. We evaluate the approach on synthetic and benchmark-derived CVRP instances containing up to 500,000 customers. Experimental results demonstrate competitive performance on benchmark-scale instances while exhibiting improved scalability and robust routing quality on substantially larger problems. These results highlight the potential of adaptive, LLM-guided decision support as a practical approach for industrial-scale vehicle routing and large-scale logistics planning.