The vehicle routing problem (VRP) is a fundamental NP-hard task in intelligent transportation systems with broad applications in logistics and distribution. Deep reinforcement learning (DRL) with Graph Neural Networks (GNNs) has shown promise, yet classical models rely on large multi-layer perceptrons (MLPs) that are parameter-heavy and memory-bound. We propose a Quantum Graph Attention Network (Q-GAT) within a DRL framework, where parameterized quantum circuits (PQCs) replace conventional MLPs at critical readout stages. The hybrid model maintains the expressive capacity of graph attention encoders while reducing trainable parameters by more than 50%. Using proximal policy optimization (PPO) with greedy and stochastic decoding, experiments on VRP benchmarks show that Q-GAT achieves faster convergence and reduces routing cost by about 5% compared with classical GAT baselines. These results demonstrate the potential of PQC-enhanced GNNs as compact and effective solvers for large-scale routing and logistics optimization.
Comments
11 pages, 3 figures, 2 tables. Accepted by SOICT 2025
The vehicle routing problem (VRP) is a fundamental NP-hard task in intelligent transportation systems with broad applications in logistics and distribution. Deep reinforcement learning (DRL) with Graph Neural Networks (GNNs) has shown promise, yet classical models rely on large multi-layer perceptrons (MLPs) that are parameter-heavy and memory-bound. We propose a Quantum Graph Attention Network (Q-GAT) within a DRL framework, where parameterized quantum circuits (PQCs) replace conventional MLPs at critical readout stages. The hybrid model maintains the expressive capacity of graph attention encoders while reducing trainable parameters by more than 50%. Using proximal policy optimization (PPO) with greedy and stochastic decoding, experiments on VRP benchmarks show that Q-GAT achieves faster convergence and reduces routing cost by about 5% compared with classical GAT baselines. These results demonstrate the potential of PQC-enhanced GNNs as compact and effective solvers for large-scale routing and logistics optimization.
The logistics vehicle routing optimization problem is a widely discussed combinatorial optimization(CO) problem with broad application prospects. Graph Neural Network(GNN) is extensively used in this context due to their suitability for the graph structure of transportation networks. However, existing methods lack interpretability for CO problem models and do not offer a generalized and unified modeling process. Additionally, traditional neural networks face shortcomings when handling dynamic graphs and directed graph problems, with suboptimal node information aggregation capabilities. Therefore, designing a method for the logistics vehicle routing optimization problem that features a unified and concise problem model, rapid solution speed, and accurate results is crucial. This paper proposes a framework for accelerating the solution of the logistics vehicle routing optimization problem using a Graph Attention Network (GAT) based on quadratic unconstrained binary op-timization(QUBO) modeling methods. The framework aims to abstract practical problems into QUBO form, and it constructs a concise and unified model for the problem while utilizing Multi-Head Attention mechanisms to aggregate node information in graph-structured problems. These are then solved using GNN. Comparing this method with actual results and traditional GNN solving methods demonstrates that, in cases with a higher number of nodes, this method has certain advantages in solution speed and accuracy.
Vehicle Routing Problem (VRP) is one of the most complex NP-hard combinatorial optimization problem in transportation and logistics that requires a dynamic solution approach. In this paper we present a new hybrid approach that combines the Quantum Approximate Optimization Algorithm (QAOA) into the QRL policy network, instead of the usual variational layers, QAOA mixing and cost Hamiltonian layers. This enhancement enables the agent to exploit problem specific particular quantum correlations when learning policies, and so richer exploration of the routing solution space. The QAOA-augmented QRL framework shows quicker convergence in training and can tackle larger VRP instances that are beyond the reach of Grover's Adaptive Search (GAS) and Quantum Reinforcement Learning (QRL) approaches. Experiments on standard VRP instances demonstrate better solutions, fewer episodes to converge and good memory usage on near term quantum hardware simulators. These findings demonstrate QAOA- integrated QRL as a viable approach to scalable, high quality quantum-assisted combinatorial optimization.
Quantum networks attract increasing attention due to their unique advantages over classical networks. However, the challenge of efficiently and economically constructing reliable wide-area quantum networks remains unresolved. This problem, termed network planning, is typically modeled as an Integer Linear Programming (ILP) problem. Existing solver-based solutions for classical networks face scalability issues, while heuristic approaches that sacrifice optimality for scalability heavily rely on human expertise and lack generalizability. Recently, deep reinforcement learning (DRL) has demonstrated potential in adaptive decision-making for classical network planning. However, quantum networks introduce unique constraints due to their end-to-end entanglement distribution requirements. To address this, we propose a two-stage quantum network resource allocation framework, QPLAN, that combines multi-agent DRL with traditional optimization solvers. Our approach uses a novel multi-agent reinforcement learning strategy using graph neural networks (GNNs) and transformers for traffic flow and corresponding hardware resource allocation to minimize hardware cost while cooperatively satisfying problem constraints as much as possible. The output of the DRL algorithm is then used as an initial input to prune the solution space, "warm-starting" the ILP solver and further improving the solution. This hybrid approach effectively reduces manual effort and enhances scalability. Experimental results show that our method yields near-optimal solutions with better scalability than only using ILP solvers.
Quantum computing and machine learning have potential for symbiosis. However, in addition to the hardware limitations from current devices, there are still basic issues that must be addressed before quantum circuits can usefully incorporate with current machine learning tasks. We report a strategy for such an integration in the context of attention models used for reinforcement learning. Agents that implement attention mechanisms have successfully been applied to certain cases of combinatorial routing problems by first encoding nodes on a graph and then sequentially decoding nodes until a route is selected. We demonstrate that simple quantum circuits can be used in place of classical attention head layers while maintaining performance. Our method modifies attention mechanisms by replacing key and query vectors for every node with quantum states that are entangled before being measured. The resulting hybrid classical-quantum agent is tested in the context of vehicle routing problems where its performance is competitive with the original classical approach. We regard our model as a prototype that can be scaled up and as an avenue for further study on the role of quantum computing in reinforcement learning.
Abstract The significant growth of e-commerce has created a vast demand for last-mile parcel delivery, in which case, parcel lockers will be the future of home delivery. But the Pickup and Delivery Problem with Lockers (PDPL) is computationally hard as it is an NP-hard problem with locker capacities, time windows, and stochastic customer availability. In this paper, we present Q-PDPL, a novel quantum-assisted hybrid approach for optimization that employs Variation Quantum Eigensolver (VQE), Quantum Approximate Optimization Algorithm (QAOA), and Quantum Graph Attention Networks (Q-GAT) in a Dantzig-Wolfe decomposition (DW) scheme. The framework recasts the pricing problem as a ground state of the energy optimization problem, which is quantum efficiently solvable by means of parameterized quantum circuits. In a stochastic setting, a Q-GAT-enhanced deep reinforcement learning module is employed that delivers online routing decisions. Tests with Solomon VRPTW and Li and Lim PDPTW datasets over the SQL demonstrate that Q-PDPL is 18.7% cheaper than classical Adaptive Large Neighborhood Search, 23.4% better than Branch-and-Price, and handles over 500 customers. The quantum pricing sub problem has O(√N⋅"poly" (logN)) complexity (classical O(N 2 )) and a solution quality within 2.1% of the optimal bound. These results hold out promise for quantum-classical hybrid algorithms for large-scale logistics.
This work studies hybrid quantum-classical neural networks for learning routing heuristics. Specifically, this paper asks whether small quantum neural networks can replace parameter-heavy modules inside a competitive attention-based routing model while maintaining solution quality. For the capacitated vehicle routing problem, encoder feed-forward replacement emerges as the most promising design: it reduces the number of model parameters by 56.6% while keeping the hybrid model close to the classical neural baseline at small and medium instance sizes, although the gap grows for larger instances. This work also compares to classical routing algorithms, which remain highly competitive and often superior on the fixed Euclidean test sets. Our results therefore do not indicate quantum advantage or solver dominance, but identify encoder feed-forward replacement as a viable hybrid-module compression strategy for neural combinatorial optimization.