Robust Feasible Route Construction through Collaborative Partition Optimization

• URL: http://arxiv.org/abs/2607.03694v1
• Date: Sat, 04 Jul 2026 03:58:46 GMT
• Title: Robust Feasible Route Construction through Collaborative Partition Optimization
• Abstract summary: Collaborative Routing Constructors (CoRC) is a routing framework that enables independently solved subproblems to exchange customers and vehicles.<n>CoRC consistently constructs feasible routing solutions where competing partition-based methods do not.<n>These results demonstrate that collaboration between routing subproblems provides a robust and scalable approach for feasible large-scale route construction.
• Score: 2.3204178451683264
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• RouteRepair: Instance-Level Failure Diagnosis and Targeted Repair in LLM-Based Automated Heuristic Design for Routing Optimization [41.634732070837906]
  This study develops RouteRepair, which diagnoses parent-specific weaknesses from instance-level performance and applies targeted modifications to the corresponding components.<n> Experiments on the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP) span constructive search, guided local search, and ant colony optimization.<n>Results show that failure-aware, evidence-constrained refinement can improve routings on difficult instances while preserving performance on cases they already solve well.
  arXiv  Detail & Related papers  (2026-09-10T12:21:18Z)
• Adaptive Cluster-First Route-Second Decomposition for Industrial-Scale Vehicle Routing [2.3204178451683264]
  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.
  arXiv  Detail & Related papers  (2026-06-30T15:31:40Z)
• Efficient and Interpretable Multi-Agent LLM Routing via Ant Colony Optimization [58.59491516762626]
  We propose AMRO-S, an efficient and interpretable routing framework for Multi-Agent Systems (MAS)<n>AMRO-S models MAS routing as a semantic-conditioned path selection problem, enhancing routing performance through three key mechanisms.<n>Extensive experiments on five public benchmarks and high-concurrency stress tests demonstrate that AMRO-S consistently improves the quality--cost trade-off over strong routing baselines.
  arXiv  Detail & Related papers  (2026-03-13T12:26:05Z)
• Relatron: Automating Relational Machine Learning over Relational Databases [50.94254514286021]
  We present a study that unifies RDL and DFS in a shared design space and conducts architecture-centric searches across diverse RDB tasks.<n>Our analysis yields three key findings: (1) RDL does not consistently outperform DFS, with performance being highly task-dependent; (2) no single architecture dominates across tasks, underscoring the need for task-aware model selection; and accuracy is an unreliable guide for choice architecture.
  arXiv  Detail & Related papers  (2026-02-26T02:45:22Z)
• CONCUR: A Framework for Continual Constrained and Unconstrained Routing [79.85419373937765]
  AI tasks differ in complexity and are best addressed with different computation strategies.<n>Most prior methods build the routing framework by training a single model across all strategies.<n>We propose CONCUR, a continual routing framework that supports both constrained and unconstrained routing.
  arXiv  Detail & Related papers  (2025-12-10T07:30:13Z)
• An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problems [66.60904891478687]
  We propose an Agentic Framework with LLMs (AFL) for solving complex vehicle routing problems.<n>AFL directly extracts knowledge from raw inputs and enables self-contained code generation.<n>We show that AFL substantially outperforms existing LLM-based baselines in both code reliability and solution feasibility.
  arXiv  Detail & Related papers  (2025-10-19T03:59:25Z)
• Rich Vehicle Routing Problem in Disaster Management enabling Temporally-causal Transhipments across Multi-Modal Transportation Network [1.1470070927586018]
  A rich vehicle routing problem is considered, allowing multiple trips of heterogeneous vehicles stationed at geographically distributed vehicle depots having access to different modes of transportation.<n>The problem arises from the real-world requirement of optimizing the disaster response time by minimizing the makespan of vehicular routes.<n>The superiority of the proposed cascaded minimization approach is demonstrated through our developed Mixed-Integer Linear Programming formulation.
  arXiv  Detail & Related papers  (2025-09-16T16:37:18Z)
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
  Vehicle Routing Problems (VRP) are a fundamental NP-hard challenge in Evolutionary optimization.<n>We introduce an optimization framework where a reinforcement learning agent is trained on prior instances and quickly generates initial solutions.<n>This framework consistently outperforms current state-of-the-art solvers across various time budgets.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• DeepMDV: Global Spatial Matching for Multi-depot Vehicle Routing Problems [2.218667838700643]
  Rapid growth of online retail and e-commerce has made effective and efficient Vehicle Routing Problem (VRP) solutions essential.<n>To meet rising demand, companies are adding more depots, which changes the VRP problem to a complex optimization task of Multi-Depot VRP.<n>We propose a novel approach to solve MDVRP addressing these interdependencies, hence achieving more effective results.
  arXiv  Detail & Related papers  (2024-11-26T03:41:01Z)
• Controllable Prompt Tuning For Balancing Group Distributional Robustness [53.336515056479705]
  We introduce an optimization scheme to achieve good performance across groups and find a good solution for all without severely sacrificing performance on any of them. We propose Controllable Prompt Tuning (CPT), which couples our approach with prompt-tuning techniques. On spurious correlation benchmarks, our procedures achieve state-of-the-art results across both transformer and non-transformer architectures, as well as unimodal and multimodal data.
  arXiv  Detail & Related papers  (2024-03-05T06:23:55Z)
• 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)

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.