Solving the Traveling Salesman Problem with reinforcement learning
In my master's thesis, I trained a PPO agent to construct routes for the Traveling Salesman Problem and combined it with classical local search. Under a strict time limit, the hybrid pipeline found routes up to about 25% shorter than a greedy baseline.
01 / Overview
From classic optimization to learned heuristics
During my master's thesis, I explored a question at the intersection of operations research and artificial intelligence: can a reinforcement learning agent learn effective routing heuristics for the Traveling Salesman Problem (TSP)?
The TSP is one of the best-known combinatorial optimization problems: given a set of cities and the travel costs between them, find the shortest route that visits every city exactly once and returns to the start. The problem sounds simple, but the number of possible tours grows factorially with the number of cities, so practitioners rely on exact algorithms or carefully designed heuristics.
02 / Why Reinforcement Learning
Learning routes through trial and error
Reinforcement learning has achieved strong results in game playing, robotics, and resource allocation by letting agents learn behavior through trial and error instead of explicit rules.
The core idea of the thesis: represent a TSP instance as an environment, let an agent build routes city by city, reward short tours, and let it refine its routing heuristic over millions of training steps.
Learning Algorithm
I chose Proximal Policy Optimization (PPO), a widely used policy-gradient method with relatively stable training and a good balance between exploration and exploitation.
- Policy gradient: Learns directly from tour quality signals without requiring a model of the environment.
- Stable training: PPO's clipped objective prevents large, destabilizing policy updates.
Its stability and simplicity made PPO a robust choice for this high-variance combinatorial setting.
03 / Environment Design
Turning the TSP into an RL task
The main technical challenge was translating a combinatorial optimization problem into a reinforcement learning environment with clear states, actions, and rewards.
At each decision step, the agent chooses which city to visit next, and the episode continues until a complete Hamiltonian cycle has been constructed. The reward structure is tied to tour quality, so shorter routes receive better returns while inefficient decisions are penalized.
A key design question was the state representation. Instead of raw distances only, I tested several representations combining distances, relative cost differences, and positional features of candidate cities.
04 / Action Space
Why "all cities" was too many actions
Initially, the agent could choose any city as its next action. That seemed natural but caused severe learning problems.
The agent repeatedly selected cities it had already visited, got stuck in invalid behavior, and struggled to complete tours, especially on larger instances. In hindsight, action masking would address this directly.
05 / Training Strategies
Instance-specific vs. generalized learning
Training required millions of environment interactions. I compared two strategies.
Instance-specific: the agent trained on slightly modified versions of the TSPLIB benchmark instances, to internalize their routing structure.
Generalized: the agent trained on randomly generated cost matrices, forcing it to learn routing principles that transfer across instances. In practice, these models performed comparably to, and sometimes better than, the instance-specific ones.
06 / Hybrid Optimization
Why RL alone was not enough
A central insight: RL alone produced good initial solutions, but classical optimization remained essential for refining them.
Instead of replacing traditional heuristics, the framework combined both: the RL model produced candidate routes, which were then improved with simulated annealing, 3‑Opt local search, the custom Sequence Shuffle procedure, and additional permutation-based local optimization.
This hybrid pipeline proved substantially more effective than using RL alone, especially under the fixed time budget for each instance.
07 / Sequence Shuffle
Learning from recurring subsequences
A distinctive contribution of the thesis is a custom post-processing method, Sequence Shuffle. It builds on the observation that certain subsequences recur in the best routes produced by the RL agent.
- Identify: Detect recurring route segments among the best solutions found so far.
- Preserve: Lock in these subsequences as structural anchors.
- Rearrange: Optimize the remaining parts of the tour around them using 3‑Opt.
08 / Evaluation
Benchmarks and performance
The experimental evaluation used six asymmetric TSP benchmark instances with between 17 and 443 cities, with both deterministic and stochastic variants to test robustness under uncertainty.
Performance was measured as percentage deviation from the best-known solution and compared against greedy construction, simulated annealing, and 3‑Opt local search. Within a 5‑minute computation budget, the hybrid pipeline reduced route costs by up to about 25% relative to the greedy baseline.
09 / Lessons Learned
What this thesis taught me
Machine learning and classical operations research are not competing approaches. Reinforcement learning can learn useful construction heuristics from experience, while established methods remain very strong at refining solutions. The best results came from combining both.
10 / Outlook
From thesis to real-world routing
The thesis showed how a hybrid framework can tackle difficult routing problems under tight time constraints.
The same ideas extend to richer routing problems with time windows, multiple depots, or stochastic travel times, and more broadly to logistics and decision-support systems where fast, high-quality routes matter.
Key Takeaways
What worked
- Hybrid wins: RL construction + classical refinement outperforms either approach alone.
- Generalization: Training on random cost matrices transfers well to benchmark instances.
- Candidate actions: Limiting the action space is essential for scaling to larger instances.
- Sequence Shuffle: Exploiting recurring subsequences delivers consistent gains with 3‑Opt.