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

arXiv: https://arxiv.org/abs/2606.31820 · HTML: https://mlsanity.com/paper/2606.31820/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 52 references that are in the map.
- First posted on arXiv 30 Jun 2026.

## Builds on (most cited first, 11 of 11)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [The Rise and Potential of Large Language Model Based Agents: A Survey](https://mlsanity.com/paper/2309.07864/) (2023)
- [Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood](https://mlsanity.com/paper/2012.10384/) (2020)
- [An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem](https://mlsanity.com/paper/2107.07076/) (2021)
- [OptimAI: Optimization from Natural Language Using LLM-Powered AI Agents](https://mlsanity.com/paper/2504.16918/) (2025)
- [Large Language Models for Combinatorial Optimization: A Systematic Review](https://mlsanity.com/paper/2507.03637/) (2025)
- [Agentic LLMs in the Supply Chain: Towards Autonomous Multi-Agent Consensus-Seeking](https://mlsanity.com/paper/2411.10184/) (2024)
- [Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows](https://mlsanity.com/paper/2402.00041/) (2024)
- [Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering](https://mlsanity.com/paper/2403.14013/) (2024)
- [Large Language Models for Operations Research: A Comprehensive Survey](https://mlsanity.com/paper/2605.20849/) (2026)
- [An LLM-powered MILP modelling engine for workforce scheduling guided by expert knowledge](https://mlsanity.com/paper/2511.02364/) (2025)

## Abstract (arXiv)

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.