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

• URL: http://arxiv.org/abs/2606.31820v1
• Date: Tue, 30 Jun 2026 15:31:40 GMT
• Title: Adaptive Cluster-First Route-Second Decomposition for Industrial-Scale Vehicle Routing
• Abstract summary: We propose an adaptive CFRS system that formulates a decomposition procedure as an iterative decision-making process.<n>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.<n>We evaluate the approach on synthetic and benchmark-derived CVRP instances containing up to 500,000 customers.
• Score: 2.3204178451683264
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• ASPaeroFlow: Decomposition Heuristics for Joint Air Traffic Flow & Capacity Management [60.85136195443409]
  We propose ASPaeroFlow: a for the joint Air Traffic Flow and Capacity Management (ATFCM)<n>It combines instance-space decompositions with a local exact approach using Answer Set Programming.<n>We benchmark ASPaeroFlow from small to industry-sized instances and compare it with exact and alternative approaches.
  arXiv  Detail & Related papers  (2026-08-10T08:57:18Z)
• Before Thinking, Learn to Decide: Proactive Routing for Efficient Visual Reasoning [87.18590662029432]
  We propose PRP, a Proactive Routing Paradigm that enables early decision-making by jointly evaluating the competence of both the draft and target models.<n>Our draft Rating Learning (DRL) equips the draft model with an internal confidence estimator, while Joint Rating Learning (JRL) predicts how well the target model can handle a given query.<n>These ratings enable fine-grained, instance-level textbfProactive Routing and substantially accelerate inference without compromising overall performance.
  arXiv  Detail & Related papers  (2026-06-29T12:30:24Z)
• AutoOR: Scalably Post-training LLMs to Autoformalize Operations Research Problems [54.593031581486116]
  We present AutoOR, a scalable synthetic data generation and reinforcement learning pipeline that trains LLMs to autoformalize optimization problems specified in natural language.<n>AutoOR generates verified training data from standard optimization forms and uses solver execution feedback as the reward signal for RL post-training.<n>We believe that methods such as AutoOR can significantly accelerate industrial decision-making with AI.
  arXiv  Detail & Related papers  (2026-04-18T03:24:54Z)
• Adaptive decision-making for stochastic service network design [1.2154569665167423]
  This paper addresses the Service Network Design (SND) problem for a logistics service provider (LSP) operating in a multimodal freight transport network.<n>A two-stage optimization approach is proposed, which combines metaheuristics, simulation and machine learning components.
  arXiv  Detail & Related papers  (2026-03-25T14:51:57Z)
• Multi-Agent DRL for V2X Resource Allocation: Disentangling Challenges and Benchmarking Solutions [51.22818149833102]
  Multi-agent reinforcement learning (MARL) has emerged as a promising approach for radio resource allocation in vehicle-to-everything (C-V2X) networks.<n>However, the multifaceted challenges inherent to MARL are often intertwined, making it difficult to understand their individual impact on performance in vehicular environments.<n>We bridge this gap by formulating C-V2X RRA as a sequence of multi-agent interference games with progressively increasing complexity.
  arXiv  Detail & Related papers  (2026-02-18T14:46:56Z)
• VAGPO: Vision-augmented Asymmetric Group Preference Optimization for Graph Routing Problems [27.70647397895125]
  Graph routing problems play a vital role in web-related networks, where finding optimal paths across graphs is essential.<n>Recent data-driven optimization methods have made significant progress, yet they often face limitations in training efficiency and generalization to large-scale instances.<n>We propose a novel Vision-augmented Asymmetric Group Preference Optimization (VAGPO) approach, which captures both spatial structure and temporal dependencies.
  arXiv  Detail & Related papers  (2025-08-03T14:19:12Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• From approximation error to optimality gap -- Explaining the performance impact of opportunity cost approximation in integrated demand management and vehicle routing [0.0]
  We propose an explainability technique that quantifies and visualizes the magnitude of approximation errors, their immediate impact, and their relevance in specific regions of the state space.<n>Applying the technique to a generic i-DMVRP in a full-factorial computational study, we show that the technique contributes to better explaining algorithmic performance and provides guidance for the algorithm selection and development process.
  arXiv  Detail & Related papers  (2024-12-18T13:46:46Z)
• Making Large Language Models Better Planners with Reasoning-Decision Alignment [70.5381163219608]
  We motivate an end-to-end decision-making model based on multimodality-augmented LLM. We propose a reasoning-decision alignment constraint between the paired CoTs and planning results. We dub our proposed large language planners with reasoning-decision alignment as RDA-Driver.
  arXiv  Detail & Related papers  (2024-08-25T16:43:47Z)
• Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering [1.3927943269211591]
  Efficiently solving a vehicle routing problem in a practical runtime is a critical challenge for delivery management companies. This paper explores both a theoretical and experimental connection between the Capacitated Vehicle Problem (CVRP) and the Constrainedid-Based Clustering (CCBC) The proposed framework consists of three stages. At the first step, a constrained centroid-based clustering algorithm generates feasible clusters of customers.
  arXiv  Detail & Related papers  (2024-03-20T22:24:36Z)
• Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows [0.0]
  We propose a decompose-route-improve (DRI) framework that groups customers using clustering. Its similarity metric incorporates customers' spatial, temporal, and demand data. We apply pruned local search (LS) between solved subproblems to improve the overall solution.
  arXiv  Detail & Related papers  (2024-01-20T06:06:01Z)
• Application-Driven Learning: A Closed-Loop Prediction and Optimization Approach Applied to Dynamic Reserves and Demand Forecasting [41.94295877935867]
  We present application-driven learning, a new closed-loop framework in which the processes of forecasting and decision-making are merged and co-optimized. We show that the proposed methodology is scalable and yields consistently better performance than the standard open-loop approach.
  arXiv  Detail & Related papers  (2021-02-26T02:43:28Z)
• An adaptive data-driven approach to solve real-world vehicle routing problems in logistics [0.0]
  Transportation occupies one-third of the amount in the logistics costs. This work presents an adaptive data-driven innovative modular approach for solving the real-world Routing Vehicle Problems (VRP) in the field of logistics.
  arXiv  Detail & Related papers  (2020-01-05T17:47:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.