A hybrid quantum-classical neural network for learning to route

# A hybrid quantum-classical neural network for learning to route
Source: [https://arxiv.org/html/2609.00489](https://arxiv.org/html/2609.00489)
Alexsandro Santos da Rosa Júnior1Marcos Vinicius Reballo1 Cesar Augusto do Amaral1,2Fernando Augusto Caletti de Barros1 1Instituto de Pesquisas Eldorado – Porto Alegre – RS – Brazil 2Departamento de FísicaUniversidade Federal de Santa CatarinaFlorianópolis 88040\-900SCBrazil 3Instituto de InformáticaUniversidade Federal do Rio Grande do SulPorto AlegreBrazil \{marcus\.ritt\.BE, alexsandro\.junior, marcos\.reballo, cesar\.amaral\.BE, fernando\.barros\}@eldorado\.org\.br

###### Abstract

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\.

###### keywords

Vehicle routing, hybrid quantum\-classical neural networks, neural combinatorial optimization, quantum machine learning\.

## 1Introduction

There is ongoing research on solving combinatorial optimization problems by learning, in particular by training neural networks to solve them from sampled instances instead of designing problem\-specific algorithms manually\. Current neural architectures for this task, however, have too many parameters to be replaced entirely by quantum neural networks on near\-term devices\.

This paper studies whether hybrid quantum\-classical solutions can achieve good performance with fewer parameters, and thereby point to possible ways of replacing selected components of classical neural networks by quantum versions\. This work focus on the classical capacitated vehicle routing problem \(CVRP\), a strongly NP\-hard routing problem with direct practical relevance\([Dantzig and Ramser, 1959](https://arxiv.org/html/2609.00489#bib.bib1)\)\.

Classical approaches to the CVRP range from exact branch\-and\-cut formulations to a wide variety of constructive, local\-search heuristics, and metaheuristics, which remain highly effective in practice\([Toth and Vigo, 2014](https://arxiv.org/html/2609.00489#bib.bib15);[Bogyrbayeva et al\., 2024](https://arxiv.org/html/2609.00489#bib.bib14)\)\. In parallel, there is growing interest in quantum optimization methods such as QAOA and VQE, which typically encode routing problems into QUBO formulations that are then transformed into equivalent Ising Hamiltonians for implementation on quantum hardware and solve them as variational hybrid quantum\-classical programs\. More recently, quantum machine learning \(QML\) methods have been proposed, in which parametric quantum circuits act as learnable components inside larger models\. However, current quantum devices and simulators severely limit circuit width and depth, which makes it difficult to replace entire neural architectures for routing\. This work therefore focuses on a narrower question: whether small QNN modules can replace parameter\-heavy subcomponents of competitive classical neural models while keeping most of their solution quality\.

The CVRP can be defined as follows\. LetV=\{0,1,…,n\}V=\\\{0,1,\\dots,n\\\}be the set of nodes, where00represents the depot andN=\{1,…,n\}N=\\\{1,\\dots,n\\\}denotes the customers\. The distance between nodesiiandjjisdi​jd\_\{ij\}, andqiq\_\{i\}is the demand of customerii, withq0=0q\_\{0\}=0\. The problem assumes a homogeneous fleet where the capacity of all vehicles isQQ\. The objective is to serve all customers minimizing the total travelled distance of all vehicles\.

The problem can be understood as a partition of the set of customersNNwhere each part forms a route together with the depot such that the total cost of the routes is minimized\. For a routerrletV⁡\(r\)V\(r\)be the customers serviced on it, and for any set of customersS⊆NS\\subseteq Ndenote byℛ\\mathcal\{R\}a set of feasible routes to serve them, where a router∈ℛr\\in\\mathcal\{R\}is feasible if

∑i∈V⁡\(r\)qi≤Q\.\\sum\_\{i\\in V\(r\)\}q\_\{i\}\\leq Q\.\(1\)Then,k⁡\(S\)k\(S\)can be defined as the minimum number of vehicles required to service customers inS⊆NS\\subseteq N:

k\(S\)=min\{\|ℛ\|:S⊆⋃r∈ℛV\(r\),feasible route setℛ\}\.k\(S\)=\\min\\left\\\{\|\\mathcal\{R\}\|:S\\subseteq\\bigcup\_\{r\\in\\mathcal\{R\}\}V\(r\),\\text\{feasible route set $\\mathcal\{R\}$\}\\right\\\}\.\(2\)
Introducing a binary decision variablexi​jx\_\{ij\}which assumes11if a vehicle travels from nodeiito nodejj, and00otherwise, a standard arc\-based integer programming formulation of this problem is as follows\. The objective minimizes the total travelled distance, constraints enforce flow conservation and depot capacity, and capacity\-cut constraints ensure feasibility and eliminate subtours:

min\.∑\(i,j\)∈V2i≠jdi​j​xi​j,\\displaystyle\\min\.\\sum\_\{\\begin\{subarray\}\{c\}\(i,j\)\\in V^\{2\}\\\\ i\\neq j\\end\{subarray\}\}d\_\{ij\}x\_\{ij\},\(3\)s\.t\.∑j∈V∖\{i\}xi​j=∑j∈V∖\{i\}xj​i=1,\\displaystyle\\sum\_\{j\\in V\\setminus\\\{i\\\}\}x\_\{ij\}=\\sum\_\{j\\in V\\setminus\\\{i\\\}\}x\_\{ji\}=1,∀i∈N,\\displaystyle\\forall i\\in N,\(4\)∑j∈Nx0​j≤K,\\displaystyle\\sum\_\{j\\in N\}x\_\{0j\}\\leq K,\(5\)∑i∈S∑j∉Sxi​j≥k⁡\(S\),\\displaystyle\\sum\_\{i\\in S\}\\sum\_\{j\\notin S\}x\_\{ij\}\\geq k\(S\),∀S⊆N,S≠∅,\\displaystyle\\forall S\\subseteq N,S\\neq\\emptyset,\(6\)xi​j∈\{0,1\},\\displaystyle x\_\{ij\}\\in\\\{0,1\\\},∀i,j∈V\.\\displaystyle\\forall i,j\\in V\.\(7\)Here, \([3](https://arxiv.org/html/2609.00489#S1.E3)\) minimizes total distance, \([4](https://arxiv.org/html/2609.00489#S1.E4)\) ensures that each customer is entered and left exactly once, \([5](https://arxiv.org/html/2609.00489#S1.E5)\) limits the number of vehicles leaving the depot to at mostKK, \([6](https://arxiv.org/html/2609.00489#S1.E6)\) are capacity\-cut constraints requiring at leastk⁡\(S\)k\(S\)arcs to leave each customer subsetSS, and \([7](https://arxiv.org/html/2609.00489#S1.E7)\) enforces integrality\. Note that there is an exponential number of constraints \([6](https://arxiv.org/html/2609.00489#S1.E6)\), so the model is typically solved by branch\-and\-cut methods\.

This paper presents three main contributions to solving the CVRP\. A hybrid quantum\-classical neural network is proposed for solution generation, its robustness is validated experimentally, and the results indicate that competitive performance can be achieved while reducing the number of required parameters by more than50%50\\%\.

## 2A hybrid quantum\-classical neural network

This approach takes inspiration from[Kool et al\. \(2018\)](https://arxiv.org/html/2609.00489#bib.bib4), who proposed a classical neural network for learning to route two\-dimensional Euclidean instances\. Their model consists of an encoder that takes the positions of the depot and customers, together with the customer demands, and produces a representation for each node\. These representations are processed by several layers, each combining an attention mechanism, following the transformer architecture of[Vaswani et al\. \(2017\)](https://arxiv.org/html/2609.00489#bib.bib8), with a feed\-forward layer\. After the encoder, a decoder, which also employs an attention mechanism, iteratively extends partial routes until complete routes are obtained\. For the CVRP, the approach produced good results on problem instances from2020up to100100customers, which covers the small\-to\-medium regime considered in this work\.

Figure[1](https://arxiv.org/html/2609.00489#S2.F1)shows the encoder and Figure[2](https://arxiv.org/html/2609.00489#S2.F2)shows the decoder\. The encoder consists of an initial node embedding of coordinates and capacities\(xi,yi,qi\)\(x\_\{i\},y\_\{i\},q\_\{i\}\)of each node into a latent space of dimensiondhd\_\{h\}, followed byLLlayers, each consisting of a multi\-head attention \(MHA\) step withM=8M=8attention heads, followed by a feed\-forward \(FF\) network with one hidden layer and ReLU activation, both with residual connections\. Additionally, batch normalization is applied after the MHA and FF parts\. The encoder produces a final node embeddinghih\_\{i\}fori∈Vi\\in Vas well as a graph embeddingh¯=∑i∈Vhi/\|V\|\\overline\{h\}=\\sum\_\{i\\in V\}h\_\{i\}/\|V\|\.

The decoder has a single context node that consists of the embeddings of the graph, the first node of the current route, and the last node of the current route\. This context node attends to the embeddings of all other nodes to produce a discrete probability distribution over all possible continuations of the current route\. Already visited customers, as well as customers that would exceed the vehicle capacity, are masked\. Based on this probability distribution, a route is constructed iteratively, either by greedily taking the most probable node in each step or by sampling\. When no feasible successors exist, a new route is opened\. This is repeated until all customers are served\.

[Kool et al\. \(2018\)](https://arxiv.org/html/2609.00489#bib.bib4)propose a hidden size ofdh=128d\_\{h\}=128and a hidden layer of size512512in the feed\-forward network\. Therefore, the sizes and evaluation counts per forward step of the components are as shown in Table[1](https://arxiv.org/html/2609.00489#S2.T1)\. Note that the decoder does not use the usual all\-to\-all attention mechanism, but rather a one\-to\-all attention of the context node to all other nodes\. This is for performance reasons, since the decoder step must be repeatedn\+kn\+ktimes until a full routing withkkvehicles is produced\. Nevertheless, this remains the hottest path, requiring\|V\|2\|V\|^\{2\}evaluations per forward pass\.

Table 1:Component sizes and number evaluations per forward pass in the classical attention model\.ForL=3L=3, more than half of the model parameters are concentrated in the feed\-forward layers, which lie outside the critical decoder path\. This observation highlights a promising opportunity for hybridization, motivating the replacement of the feed\-forward component with a quantum neural network \(QNN\)\. As illustrated in Figure[3](https://arxiv.org/html/2609.00489#S2.F3), a classical projection first maps the hidden dimensiondhd\_\{h\}onto a lower\-dimensional space of sizeqq, corresponding to the number of qubits employed by the QNN\. The projected representation is encoded in a QNN throughRXR\_\{X\}rotations and then processed by the variational part, implemented as a brickwall ansatz with trainableRXR\_\{X\},RYR\_\{Y\}, andRZR\_\{Z\}rotations followed by CNOT gates\. The output is measured in the computational basis and up\-projected back to the original dimensiondhd\_\{h\}\. To reduce the overall parameter count, a strong bottleneck is imposed by selectingq≪dhq\\ll d\_\{h\}; the impact of this design choice is evaluated experimentally\.

Figure 1:Encoder architecture of the classical attention model\. The figure shows the node embedding and one layer of a total ofLLlayers\.Figure 2:Decoder architecture of the classical attention model\.Figure 3:Hybrid replacement of the encoder feed\-forward block\.
## 3Methodology

### 3\.1Problem Instances

This section reports computational results comparing the proposed learning\-based approach with classical algorithms\. Training is performed on randomly generated Euclidean instances with varying numbers of nodesn∈\{10,20,50,100\}n\\in\\\{10,20,50,100\\\}, where node coordinates are sampled uniformly from the unit square\[0,1\]2\[0,1\]^\{2\}\. Customer demands are drawn as random integers from\{1,2,…,9\}\\\{1,2,\\ldots,9\\\}, and vehicle capacities are set to2020,3030,4040, and5050for instances withn=10n=10,2020,5050, and100100customers, respectively\.

### 3\.2Models and Training Setup

Both the classical and hybrid neural networks are trained using a batch size of272^\{7\}samples and282^\{8\}batches per epoch, resulting in an epoch size of2152^\{15\}samples, and a total of272^\{7\}training epochs\. This setup deviates from the training regime of[Kool et al\. \(2018\)](https://arxiv.org/html/2609.00489#bib.bib4)in two respects\. First, the number of samples per epoch is reduced by approximately a factor of4040compared to the1,280​K1\{,\}280\\mathrm\{K\}samples used there\. Second, preliminary experiments indicate that improved performance is often achieved in later epochs, motivating an increase in the total number of training epochs\.

Following[Kool et al\. \(2018\)](https://arxiv.org/html/2609.00489#bib.bib4), the policy is trained end\-to\-end using the REINFORCE algorithm\([Williams, 1992](https://arxiv.org/html/2609.00489#bib.bib9)\), combined with a greedy rollout baseline, which demonstrated superior performance in prior work\. Optimization is carried out using the Adam optimizer with a learning rate of10−410^\{\-4\}\. The QNN components are simulated and trained via backpropagation\. A compact QNN configuration is adopted, consisting ofq=4q=4qubits andLq=2L\_\{q\}=2layers\. Under this setting, the hybrid FF\-QNN model comprises1,1561\{,\}156classical parameters and2424quantum parameters\. WithL=3L=3encoder layers, this design reduces the total number of parameters by391,596391\{,\}596, corresponding to a reduction of56\.6%56\.6\\%\.

The trained models are evaluated using both greedy decoding and stochastic sampling on a test set ofN=1,000N=1\{,\}000newly generated instances\. For the sampling\-based evaluation, the best solution among1,2801\{,\}280samples is reported\.

### 3\.3Baseline Algorithms

Performance is compared against five classical heuristic solvers on the same test instances: \(i\) CW, the Clarke\-Wright savings algorithm\([Clarke and Wright, 1964](https://arxiv.org/html/2609.00489#bib.bib10)\), and RCW, its randomized variant as in[Nazari et al\. \(2018\)](https://arxiv.org/html/2609.00489#bib.bib5), which selects at each step a random merge among the topmmfeasible candidates, withm∈\{1,…,10\}m\\in\\\{1,\\dots,10\\\}, and returns the best result over1010replications; \(ii\) GOT, the CVRP implementation from Google OR\-Tools v9\.15\([Furnon and Perron, 2024](https://arxiv.org/html/2609.00489#bib.bib11)\); \(iii\) LKH3, the Lin\-Kernighan\-Helsgaun heuristic\([Helsgaun, 2000](https://arxiv.org/html/2609.00489#bib.bib3)\); and \(iv\) RSW, a randomized capacitated angular sweep heuristic that returns the best solution over55runs with randomly selected starting angles, also introduced by[Nazari et al\. \(2018\)](https://arxiv.org/html/2609.00489#bib.bib5)\.

## 4Experimental results

All reported solutions are explicitly checked for feasibility\. For the neural models, decoder masking enforces feasibility by construction, and no invalid routes were observed in our experiments\.

To assess training stability, it is noted that[Kool et al\. \(2018\)](https://arxiv.org/html/2609.00489#bib.bib4)report robust performance of the classical attention model across different random seeds\. Table[2](https://arxiv.org/html/2609.00489#S4.T2)presents results for the FF\-QNN model over five independent training runs, reporting mean values and standard deviations\. The mean values are used for the FF\-QNN entries in Table[3](https://arxiv.org/html/2609.00489#S4.T3)\. The results indicate that the hybrid QNN\-based approach likewise exhibits stable training behavior, with low variability across runs\.

Table 2:FF\-QNN objective values averaged over five independent training runs\. Sampling reports the best of1,2801,280samples\.The comparison with the classical neural network and heuristic methods is now presented\. Table[3](https://arxiv.org/html/2609.00489#S4.T3)summarizes the results\. For each instance sizenn, the table reports the mean objective value over the1,0001\{,\}000test instances \(column “Obj\.”\), the average relative deviation from the best value obtained per instance \(column “r¯\\overline\{r\}”\), and the total evaluation time in minutes \(column “tt”\)\.

The average relative deviation is defined as follows\. Letvi​mv\_\{im\}denote the objective value obtained by methodmmon instancei∈\[N\]i\\in\[N\], and letμi=minm⁡vi​m\\mu\_\{i\}=\\min\_\{m\}v\_\{im\}denote the best value achieved for that instance across all methods\. The reported metric is given byr¯m=100​N−1​∑i∈\[N\]\(vi​m/μi−1\)\\overline\{r\}\_\{m\}=100N^\{\-1\}\\sum\_\{i\\in\[N\]\}\(v\_\{im\}/\\mu\_\{i\}\-1\)\.

Table 3:CVRP results for neural models and classical algorithms\. Objective values are route lengths in the unit square\. Relative deviations are from the best solution per instance\. Times are total evaluation times in minutes\. Sampling uses1,2801,280samples\.The analysis begins with an examination of overall expected objective values\. From[Beardwood et al\. \(1959\)](https://arxiv.org/html/2609.00489#bib.bib2), it is known that the expected length of the shortest Hamiltonian cycle for a random Euclidean instance in two dimensions scales asβ2​n\\beta\_\{2\}\\sqrt\{n\}, withβ2≈0\.71\\beta\_\{2\}\\approx 0\.71\. This yields approximate values of2\.352\.35,3\.253\.25,5\.075\.07, and7\.137\.13forn=10n=10,2020,5050, and100100, respectively, in the uncapacitated setting\. For the capacitated case, assuming an expected customer demand of55and vehicle capacities of2020,3030,4040, and5050, the same scaling principle can be used to estimate the expected route length, including returns to the depot\. This results in approximate upper\-scale values of3\.973\.97,6\.266\.26,13\.3113\.31, and23\.5523\.55, respectively\. Although these estimates do not constitute strict upper bounds—since efficient routes tend to exhibit spatial locality—they indicate that the observed CVRP objective values lie within a plausible range\.

The objective values are close for small instances, and the spread increases withnn\. Atn=10n=10, RCW gives the best mean objective, while several other methods are within a few percent\. Fromn=20n=20onward, LKH3 gives the best solution quality, as expected for a specialized routing solver\. The remaining methods are still competitive throughn=50n=50: for example, RSW is the weakest method at this size, but its average relative deviation is11\.68%11\.68\\%\. Atn=100n=100, the gaps are larger, although the learned methods remain in the same broad quality range as the constructive baselines\.

The main comparison in this work is between AM and FF\-QNN\. Across all instance sizes and both decoding modes, the FF\-QNN objective value is never more than about2%2\\%worse than AM, and atn=10n=10with sampling it is slightly better\. Thus, replacing all encoder feed\-forward blocks by a four\-qubit bottleneck preserves most of the AM solution quality while reducing the number of parameters by56\.6%56\.6\\%\.

The absolute quality of the neural results should be interpreted together with the training budget\.[Kool et al\. \(2018\)](https://arxiv.org/html/2609.00489#bib.bib4)report substantially smaller gaps for AM under a much larger training regime: forn=20,50,100n=20,50,100, their greedy gaps are4\.97%4\.97\\%,5\.86%5\.86\\%, and7\.34%7\.34\\%, and their sampling gaps are2\.49%2\.49\\%,2\.40%2\.40\\%, and3\.72%3\.72\\%\. As the same code base and methodology are employed, except for a reduction by nearly a factor of4040in the number of training samples per epoch, the lower absolute performance of the AM reported in Table[3](https://arxiv.org/html/2609.00489#S4.T3)is consistent with the more limited training regime\. The comparison between AM and FF\-QNN remains controlled, however, as both models are trained under the same computational budget\. In the measured range training wall\-clock time scales approximately linearly with the number of customers; a least\-squares fit through the origin gives about1\.9​n1\.9nmin for AM and8\.4​n8\.4nmin for the simulated FF\-QNN\.

Indeed, the quality of the learned approaches is largely limited by the reduced training regime used and improves with more samples\. In a test forn=100n=100with four times more samples per epoch, AM reached relative deviations of9\.3%9\.3\\%with greedy decoding and5\.2%5\.2\\%with sampling\. FF\-QNN reached9\.9%9\.9\\%and5\.6%5\.6\\%, respectively\. Thus, a modest increase in training samples already leads to a substantial improvement, as expected, while the QNN performance remains close to that of the classical approach\.

The runtime columns show a different tradeoff\. LKH3 gives the best solutions but has the largest evaluation time\. Greedy neural decoding is fast, whereas neural sampling is substantially more expensive\. The constructive methods CW and RCW are therefore strong quality\-time baselines on these fixed Euclidean instances\. In particular, our CW and RCW values are substantially better than the corresponding values reported by[Nazari et al\. \(2018\)](https://arxiv.org/html/2609.00489#bib.bib5)\. These results do not support a claim that learned methods dominate classical heuristics\. Rather, they show that learned policies can reach a comparable quality range, and that the QNN replacement preserves most of this quality with a substantially smaller model\.

## 5Related work

There is a large body of work on learning to solve combinatorial optimization problems, including both constructive and end\-to\-end approaches\. A recent survey is given by[Chung et al\. \(2025\)](https://arxiv.org/html/2609.00489#bib.bib13)\. End\-to\-end approaches based on large language models, in which an LLM is fine\-tuned to directly produce solutions, are promising, but still do not achieve the performance of specialized learning architectures\([Jiang et al\., 2025](https://arxiv.org/html/2609.00489#bib.bib7)\)\.

Our work focuses on such specialized architectures trained with reinforcement learning\. For routing problems, this continues a line of research that goes back to sequence\-to\-sequence learning and pointer networks\([Vinyals et al\., 2015](https://arxiv.org/html/2609.00489#bib.bib6)\), and includes reinforcement\-learning approaches for the CVRP such as[Nazari et al\. \(2018\)](https://arxiv.org/html/2609.00489#bib.bib5)\.

Beyond the attention model of[Kool et al\. \(2018\)](https://arxiv.org/html/2609.00489#bib.bib4), neural approaches to routing also include residual edge\-graph attention networks, such as the model proposed by[Lei et al\. \(2021\)](https://arxiv.org/html/2609.00489#bib.bib12)\. This architecture leverages edge embeddings, which shifts a larger portion of the computation to the encoder, making it a more demanding computational component\. While this design may yield improvements in solution quality, it also entails a substantially higher computational cost\. As a result, its suitability for hybrid quantum–classical integration remains less clear and warrants further investigation\.

## 6Conclusion

A hybrid quantum\-classical alternative to attention\-based routing approaches is introduced\. By replacing the encoder feed\-forward blocks with a narrow QNN module, the proposed method achieves a reduction in the number of parameters of more than50%50\\%\.

Experimental results indicate that, despite this substantial reduction, the hybrid model attains solution quality close to that of the classical neural network\. In comparison with classical heuristics, LKH3 consistently produces the best solutions, albeit at a higher computational cost, whereas CW and RCW provide strong and efficient baselines for Euclidean instances\. The main contribution of this work lies in demonstrating that a compact QNN can effectively substitute a large neural component with only a limited degradation in solution quality\.

A limitation of the present study is that it does not establish that the QNN bottleneck is superior to all size\-matched classical bottlenecks\. Future work should therefore include systematic ablations against compact classical compression modules, stronger routing\-specific inductive bias, alternative QNN architectures, and regimes in which QNNs may be more sample efficient\.

## Acknowledgments

This work was executed under the TIC26 – Brazil Quantum Camp project, funded within the scope of the Prioritized Informatics Programs and Projects \(PPI\), Process No\. 01245\.008254/2025\-22, under the responsibility of the Ministry of Science, Technology and Innovation \(MCTI\), with operational coordination by the Association for the Promotion of Brazilian Software Excellence \(SOFTEX\), and executed by CESAR and the Instituto de Pesquisas Eldorado\. The authors also want to thank VCI Vanguard Confecções Importadas S\.A\. \(Aramis\) for their collaboration on solving practical vehicle routing problems with hybrid approaches\.

## References

- Beardwoodet al\.\(1959\)J\. Beardwood, J\. H\. Halton, and J\. M\. HammersleyThe shortest path through many points\.Mathematical Proceedings of the Cambridge Philosophical Society55\(4\),pp\. 299–327\.External Links:ISSN 1469\-8064,[Document](https://dx.doi.org/10.1017/s0305004100034095)Cited by:[§4](https://arxiv.org/html/2609.00489#S4.p5.1)\.
- Bogyrbayevaet al\.\(2024\)A\. Bogyrbayeva, M\. Meraliyev, T\. Mustakhov, and B\. DauletbayevMachine learning to solve vehicle routing problems: a survey\.IEEE Transactions on Intelligent Transportation Systems25\(6\),pp\. 4754–4772\.Cited by:[§1](https://arxiv.org/html/2609.00489#S1.p3.1)\.
- Chunget al\.\(2025\)K\. T\. Chung, C\. K\. M\. Lee, and Y\. P\. TsangNeural combinatorial optimization with reinforcement learning in industrial engineering: a survey\.58\(5\)\.External Links:[Document](https://dx.doi.org/10.1007/s10462-024-11045-1)Cited by:[§5](https://arxiv.org/html/2609.00489#S5.p1.1)\.
- Clarke and Wright \(1964\)G\. U\. Clarke and J\. W\. WrightScheduling of vehicles from a central depot to a number of delivery points\.Operations Research12\(4\),pp\. 568–581\.Cited by:[§3\.3](https://arxiv.org/html/2609.00489#S3.SS3.p1.1)\.
- Dantzig and Ramser \(1959\)G\. B\. Dantzig and J\. H\. RamserThe truck dispatching problem\.Management Science6\(1\),pp\. 80–91\.External Links:ISSN 1526\-5501,[Document](https://dx.doi.org/10.1287/mnsc.6.1.80)Cited by:[§1](https://arxiv.org/html/2609.00489#S1.p2.1)\.
- Furnon and Perron \(2024\)V\. Furnon and L\. PerronOR\-tools routing library v9\.15\.Google\.External Links:[Link](https://developers.google.com/optimization/routing/)Cited by:[§3\.3](https://arxiv.org/html/2609.00489#S3.SS3.p1.1)\.
- Helsgaun \(2000\)K\. HelsgaunAn effective implementation of the lin–kernighan traveling salesman heuristic\.European Journal of Operational Research126\(1\),pp\. 106–130\.External Links:ISSN 0377\-2217,[Document](https://dx.doi.org/10.1016/s0377-2217%2899%2900284-2)Cited by:[§3\.3](https://arxiv.org/html/2609.00489#S3.SS3.p1.1)\.
- Jianget al\.\(2025\)X\. Jiang, Y\. Wu, M\. Li, Z\. Cao, and Y\. ZhangLarge language models as end\-to\-end combinatorial optimization solvers\.External Links:2509\.16865,[Link](https://arxiv.org/abs/2509.16865)Cited by:[§5](https://arxiv.org/html/2609.00489#S5.p1.1)\.
- Koolet al\.\(2018\)W\. Kool, H\. van Hoof, and M\. WellingAttention, learn to solve routing problems\!\.External Links:[Document](https://dx.doi.org/10.48550/ARXIV.1803.08475),1803\.08475Cited by:[§2](https://arxiv.org/html/2609.00489#S2.p1.1),[§2](https://arxiv.org/html/2609.00489#S2.p4.1),[§3\.2](https://arxiv.org/html/2609.00489#S3.SS2.p1.1),[§3\.2](https://arxiv.org/html/2609.00489#S3.SS2.p2.1),[§4](https://arxiv.org/html/2609.00489#S4.p2.1),[§4](https://arxiv.org/html/2609.00489#S4.p8.1),[§5](https://arxiv.org/html/2609.00489#S5.p3.1)\.
- Leiet al\.\(2021\)K\. Lei, P\. Guo, Y\. Wang, X\. Wu, and W\. ZhaoSolve routing problems with a residual edge\-graph attention neural network\.Neurocomputing\.External Links:[Document](https://dx.doi.org/10.1016/j.neucom.2022.08.005)Cited by:[§5](https://arxiv.org/html/2609.00489#S5.p3.1)\.
- Nazariet al\.\(2018\)M\. Nazari, A\. Oroojlooy, L\. Snyder, and M\. TakáčReinforcement learning for solving the vehicle routing problem\.InAdvances in Neural Information Processing Systems,Vol\.31\.Cited by:[§3\.3](https://arxiv.org/html/2609.00489#S3.SS3.p1.1),[§4](https://arxiv.org/html/2609.00489#S4.p10.1),[§5](https://arxiv.org/html/2609.00489#S5.p2.1)\.
- P\. Toth and D\. Vigo \(Eds\.\) \(2014\)P\. Toth and D\. Vigo \(Eds\.\)Vehicle routing: problems, methods, and applications\.SIAM\.Cited by:[§1](https://arxiv.org/html/2609.00489#S1.p3.1)\.
- Vaswaniet al\.\(2017\)A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, L\. Kaiser, and I\. PolosukhinAttention is all you need\.InAdvances in Neural Information Processing Systems,Vol\.30\.Cited by:[§2](https://arxiv.org/html/2609.00489#S2.p1.1)\.
- Vinyalset al\.\(2015\)O\. Vinyals, M\. Fortunato, and N\. JaitlyPointer networks\.External Links:[Document](https://dx.doi.org/10.48550/ARXIV.1506.03134),1506\.03134Cited by:[§5](https://arxiv.org/html/2609.00489#S5.p2.1)\.
- Williams \(1992\)R\. J\. WilliamsSimple statistical gradient\-following algorithms for connectionist reinforcement learning\.Machine Learning8\(3–4\),pp\. 229–256\.External Links:[Document](https://dx.doi.org/10.1007/BF00992696)Cited by:[§3\.2](https://arxiv.org/html/2609.00489#S3.SS2.p2.1)\.