← Back to all news
arXiv Machine Learning

GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer

The paper presents a method for reducing the size of Quadratic Unconstrained Binary Optimization (QUBO) models used to solve the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) on quantum annealers. It introduces adaptive penalty calibration to improve constraint satisfaction and replaces hand‑tuned merge heuristics with a graph neural network (GNN) that consistently achieves higher feasibility across Solomon benchmark families. Experiments on simulated annealing and a D‑Wave Advantage2 processor show significant reductions in constraint violations and improved feasibility rates, with the QUBO size remaining 5–6 times smaller.

Related stories

arXiv Machine Learning
Sep 2

A hybrid quantum-classical neural network for learning to route

The paper investigates hybrid quantum‑classical neural networks for learning routing heuristics, focusing on whether small quantum neural networks can replace parameter‑heavy modules in an attention‑based routing model without sacrificing solution quality. For the capacitated vehicle routing problem, replacing the encoder feed‑forward component with a quantum version reduces model parameters by 56.6% while maintaining performance close to the classical baseline on small and medium instances, though the gap widens for larger instances. The study also compares the hybrid approach to classical routing algorithms, finding that classical methods remain highly competitive and often superior on fixed Euclidean test sets, indicating no quantum advantage but highlighting encoder feed‑forward replacement as a viable compression strategy for neural combinatorial optimization.

By Marcus Rolf Peter Ritt, Alexsandro Santos da Rosa J\'unior, Marcos Vinicius Reballo, Cesar Augusto do Amaral, Fernando Augusto Caletti de Barros
More like this →
arXiv AI
Sep 17

APGEM: Adaptive Policy-Guided Error Mitigation for Quantum Reinforcement Learning on a Real-World CVRP Case Study

The paper introduces APGEM, an adaptive controller that dynamically selects among four error‑mitigation techniques—Zero‑Noise Extrapolation, Probabilistic Error Cancellation, Clifford Data Regression, and Readout Error Mitigation—based on a utility function and Q‑learning scores. Applied to a realistic Delhi‑based Capacitated Vehicle Routing Problem, the adaptive approach improves the quantum reinforcement learning agent’s approximation ratios from 0.84‑0.87 to 0.92‑0.94 under high noise, outperforming constructive heuristics and approaching metaheuristics. The controller’s strategy shifts from a Clifford‑data‑regression‑heavy regime early in training to a balanced use of all techniques as training progresses, demonstrating regime‑dependent selection.

By Shabir Ahmad Sofi, Bisma Majid, Mir Mohammad Yousuf
agentsreinforcement-learning
More like this →
arXiv Machine Learning
Jul 17

Low-Latency Relay Selection in NR-V2X Vehicular Communications via Graph Isomorphism Networks with Edge Features

arXiv:2607. 14176v1 Announce Type: new Abstract: Reliable, low-latency uplink connectivity is a key requirement for C-V2X networks in dense urban environments, where fast channel variations and blockages often degrade direct vehicle-to-infrastructure links.

By Giambattista Amati, Federica Mangiatordi, Emiliano Pallotti, Simone Angelini, Pierpaolo Salvo, Paola Vocca
efficiency
More like this →
arXiv Machine Learning
Sep 4

Learning Constraints-Based Adaptive Hypergraph Neural Networks for Solving Vehicle Routing Problems

The paper presents an end‑to‑end framework that uses constraint‑oriented hypergraphs and reinforcement learning to solve vehicle routing problems. It introduces a dynamic hyperedge reconstruction strategy for better hypergraph representation and a double‑pointer attention decoder for iterative solution generation. Experiments on benchmark datasets show that the method removes the need for complex heuristic operators while improving solution quality.

By Zhenwei Wang, Tiehua Zhang, Jing Liu, Heng Yu, Kaizhu Huang, Ruibin Bai
reinforcement-learningbenchmarks
More like this →