Graph-Coarsening Approach for the Capacitated Vehicle Routing Problem with Time Windows

• URL: http://arxiv.org/abs/2510.22329v1
• Date: Sat, 25 Oct 2025 15:13:41 GMT
• Title: Graph-Coarsening Approach for the Capacitated Vehicle Routing Problem with Time Windows
• Authors: Mustafa Mert Özyılmaz,
• Abstract summary: This paper introduces a multilevel graph coarsening and refinement framework that aggregates customers into meta-nodes.<n>The proposed method reduces computation while preserving or improving solution quality, particularly with respect to capacity and time window constraints.<n>The paper also explores the integration of quantum-inspired optimization techniques, highlighting their potential to further accelerate large-scale vehicle routing tasks.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is a fundamental NP-hard optimization problem in logistics. Solving large-scale instances remains computationally challenging for exact solvers. This work introduces a multilevel graph coarsening and refinement framework that aggregates customers into meta-nodes using a spatio-temporal distance metric. The reduced problem is solved with classical heuristics and subsequently expanded back into the original space with feasibility corrections. Preliminary experiments on Solomon benchmark instances show that the proposed method reduces computation time while preserving or improving solution quality, particularly with respect to capacity and time window constraints. The paper also explores the integration of quantum-inspired optimization techniques, highlighting their potential to further accelerate large-scale vehicle routing tasks.

Related papers

• Speeding up Local Optimization in Vehicle Routing with Tensor-based GPU Acceleration [23.87172157992149]
  We introduce an original tensor-based GPU acceleration method to speed up the commonly used local search operators in vehicle routing.<n>Its low-coupling architecture, with intensive computations completely offloaded to the GPU, ensures seamless integration in various local search-based algorithms and frameworks.
  arXiv  Detail & Related papers  (2025-06-20T07:40:47Z)
• 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)
• Advanced Quantum Annealing Approach to Vehicle Routing Problems with Time Windows [7.819888986737809]
  We focus on two NP-Hard problems, including the Traveling Salesman Problem with Time Windows and the Capacitated Vehicle Routing Problem with Time Windows.<n>We utilize D-Wave's Quantum Annealer and Constrained Quadratic Model (CQM) solver within a hybrid framework to solve these problems.<n>We demonstrate that while the CQM solver effectively minimizes route costs, it struggles to maintain time window feasibility as the problem size increases.
  arXiv  Detail & Related papers  (2025-03-31T16:32:40Z)
• DNN Partitioning, Task Offloading, and Resource Allocation in Dynamic Vehicular Networks: A Lyapunov-Guided Diffusion-Based Reinforcement Learning Approach [49.56404236394601]
  We formulate the problem of joint DNN partitioning, task offloading, and resource allocation in Vehicular Edge Computing. Our objective is to minimize the DNN-based task completion time while guaranteeing the system stability over time. We propose a Multi-Agent Diffusion-based Deep Reinforcement Learning (MAD2RL) algorithm, incorporating the innovative use of diffusion models.
  arXiv  Detail & Related papers  (2024-06-11T06:31:03Z)
• A Greedy Quantum Route-Generation Algorithm [0.0]
  We propose a greedy algorithm that generates routes by using information from all samples obtained from the quantum computer.<n>By noticing the relationship between qubits in our formulation as a directed acyclic graph (DAG), we designed an algorithm that adaptively constructs a feasible solution.
  arXiv  Detail & Related papers  (2024-05-05T21:20:46Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  This paper presents a novel form of the PSO methodology that uses the Roulette Wheel Method (RWPSO) Experiments using the Solomon VRPTW benchmark datasets on the RWPSO demonstrate that RWPSO is competitive with other state-of-the-art algorithms from the literature.
  arXiv  Detail & Related papers  (2023-06-04T09:18:02Z)
• Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows [5.818566833386833]
  We introduce a novel temporal decomposition scheme for solving a class of offline PDPTWs. Our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty.
  arXiv  Detail & Related papers  (2023-03-06T20:07:05Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  Experimentally, ECORD achieves a new SOTA for RL algorithms on the Maximum Cut problem. Compared to the nearest competitor, ECORD reduces the optimality gap by up to 73%.
  arXiv  Detail & Related papers  (2022-05-27T17:13:10Z)
• Learning from Images: Proactive Caching with Parallel Convolutional Neural Networks [94.85780721466816]
  A novel framework for proactive caching is proposed in this paper. It combines model-based optimization with data-driven techniques by transforming an optimization problem into a grayscale image. Numerical results show that the proposed scheme can reduce 71.6% computation time with only 0.8% additional performance cost.
  arXiv  Detail & Related papers  (2021-08-15T21:32:47Z)
• Neural Fixed-Point Acceleration for Convex Optimization [10.06435200305151]
  We present neural fixed-point acceleration which combines ideas from meta-learning and classical acceleration methods. We apply our framework to SCS, the state-of-the-art solver for convex cone programming.
  arXiv  Detail & Related papers  (2021-07-21T17:59:34Z)
• MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
  This paper presents an approach named MineReduce, which uses mined patterns to perform problem size reduction. We present an application of MineReduce to improve a for the heterogeneous fleet vehicle routing problem.
  arXiv  Detail & Related papers  (2020-05-15T08:49:50Z)

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.