Papers › Attention, Learn to Solve Routing Problems!
Attention, Learn to Solve Routing Problems!
Wouter Kool, Herke van Hoof, Max Welling
The recently presented idea to learn heuristics for combinatorial optimization problems is promising as it can save costly development. However, to push this idea towards practical implementation, we need better models and better ways of training. We contribute in both directions: we propose a model based on attention layers with benefits over the Pointer Network and we show how to train this model using REINFORCE with a simple baseline based on a deterministic greedy rollout, which we find is more efficient than using a value function. We significantly improve over recent learned heuristics for the Travelling Salesman Problem (TSP), getting close to optimal results for problems up to 100 nodes. With the same hyperparameters, we learn strong heuristics for two variants of the Vehicle Routing Problem (VRP), the Orienteering Problem (OP) and (a stochastic variant of) the Prize Collecting TSP (PCTSP), outperforming a wide range of baselines and getting results close to highly optimized and specialized algorithms.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
For agents, Syntology's MCP tool lists every function and class Syntology harvested from this paper and whether it ran (how to connect): get_harvested_code_for_paper(arxiv_id="1803.08475")
Code
Syntology Ran 14 of 40 code samples harvested from 7 repositories linked to this paper; 26 have no recorded run. Of those that ran: 3 ran · honoured contract; 6 ran · our draft was wrong; 1 ran · fixture could not drive it; 4 ran with no contract checked.
By repository: official repository: 5 samples from 1 repository, 3 ran; community (archive-listed): 35 samples from 6 repositories, 11 ran. The run record, sample by sample. “Ran” means executed on a synthesized input, not that the code is correct or reproduces the paper.
15 repositories listed; official and paper-mentioned ones first.
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
40 samples harvested; 14 ran; 3 honoured the contract we drafted; 26 have no recorded run. Read from Syntology's graph 2026-09-24; that is when this build read the record, not when the samples ran.
Licence: 3 of the 40 samples are pointer only, meaning Syntology does not serve that copy's text. This page shows no code text for any sample; each one links to its file in the repository.
Harvested from 7 repositories linked to this paper, official or community; each sample names its own and says which. “Ran” means the sample executed on a synthesized input. It does not mean the output is correct, and nothing here reproduces the paper's results. “Honoured” and “violated” refer to a contract Syntology drafted from the code itself; “our draft was wrong” and “fixture could not drive it” are failures of Syntology's instrument, not of the code.
Each sample ends with its code_sha256, Syntology's identity for that exact code. An agent fetches the stored sample with Syntology's MCP tool get_code(code_sha256="…") (how to connect); click an identity to copy that call.
Repository labels, per sample. official repository: The archive marks this repository official for the paper. named in the paper: The archive records that the paper mentions this repository; it is not marked official. community (archive-listed): In the archive's code links for this paper, not marked official and not recorded as mentioned in the paper. found in paper text by Syntology: Syntology found this repository in the paper's own text; whether it is the authors' implementation is not asserted. community: Not in the archive's code links for this paper; a community repository Syntology harvested. Samples from a repository marked official are listed first. Licence labels name the repository's licence as recorded at harvest. “Pointer only” means Syntology does not serve that copy's text, for one of four reasons: no licence file was found; the licence was not identified; the licence is recorded as permissive but that copy's record is not marked cleared; or the licence is outside the permissive list Syntology serves text under (MIT, Apache-2.0, BSD and similar). Some licences outside that list permit redistribution, such as WTFPL, and GPL-3.0 under its conditions; they are simply not on the list. Hover a licence label for the reason. File links open the file on GitHub at the default branch, which may have changed since the harvest.
82eaf1d494d4fc16 · report
50522f260eb670be · report
3a929eede11222c2 · report
c2eb1a9181034240 · report
c2edba20f4705527 · report
01df1926cf07ac89 · report
92bf6e766294e2b3 · report
7c1af2ae74b68db5 · report
08cb493b027671f6 · report
ddda4a28f60dd187 · report
fd794d93df5fe1c0 · report
69062811f34d8ff6 · report
454003b7383dce9f · report
10638ccfaa13fb59 · report
1a3bb2f0ebdf9a4e · report
107d6628712f1a21 · report
f25ac4888d367dac · report
64903ec0e6fee27f · report
9d5b8d4a73d01c19 · report
1004553fb8c91911 · report
8daaa059e9c3cb2d · report
82c1f4dc5f78132f · report
a58fa4a05eb041d8 · report
be9c547a8e748da5 · report
25f758eab8954cab · report
f8bd592f10d20c70 · report
0f6f8675d8280c4f · report
646e8f569fdfb4c8 · report
63a2c7b484c8eb97 · report
a9dc1cf1047bd89e · report
bfdb082b8b60d5ae · report
c43c60dd79880c30 · report
222a077ac0dc342e · report
b71b6ddb1c0ba51a · report
5deb1f5b2269293b · report
7432af444f223046 · report
c33c1c373528994c · report
3855f5b5d541ad04 · report
cf9bc36f5580661b · report
0538f709044ed305 · report
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Methods
Introduced by this paper: AM
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections