Study 01 · Reinforcement Learning · Graph Neural Networks

A graph model for generating TSP routes using reinforcement learning

2018.09–2021.06 · Undergraduate research student

I implemented a graph-based TSP search program that uses reinforcement learning to select the next city to insert into the route.

1Representation via graphs
Cities, distances, and visitation status
2Structure2Vec + Q-learning
Calculating Q-values for each city
3City selection and route insertion
Insert cities selected by the model using a heuristic approach.

Reinforcement learning design

State: City connections (adjacency matrix), distances, and cities already on the route
Action: Choose the next city to add to the route
Reward: The extra route length from adding the city counts directly as a penalty

Implementation referring to NeurIPS 2017 graph combination optimization research

Reinforcement learningStructure2VecDeep Q-learningGraph neural networkTensorFlowNumPy

Roles and outcomes

Research goal: The goal was to find short routes faster than existing algorithms for the TSP, where the number of possible routes grows rapidly as cities are added. I approached it with reinforcement learning together with my supervising professor.
Assigned role: Based on the graph representations and Q-learning concepts from the referenced paper, I implemented experimental code that connects the TSP environment, model, training loop, and insertion rules.
Results: The program takes city locations, distances and visit status as graph input and uses an insertion heuristic to add the city chosen by the model to the route. Comparing the public code against baselines, I also traced why the learning did not work as intended.

Implemented and analyzed personally

Graph environment containing nodes, edges, and visitation status, along with a record of path costs
Structure2Vec embedding and Q value evaluation
Exploration loop connecting multi-step reward accumulation and experience sampling
A structure where the model selects a city, and an insertion heuristic determines where to place it.

Based research and disclosure model

NeurIPS 2017 Structure2Vec/Reinforcement Learning approach for graph combinatorial optimization research

Experiment results and trial and error

In the accelerated learning phase, no improvement was observed compared to random insertion.

When training with the original settings, the policy produced the same Q-value for all cities, resulting in cities being selected in numerical order.

TensorFlow 2.15
3 seeds
Episodes: 10,000 → 100

An animation showing the construction of a route—one city at a time—using both the learned policy and the farthest-insertion heuristic, based on the same set of 50 cities. The learned policy selects cities in numerical order, resulting in a path 1.12 times longer than that produced by OR-Tools, while the "farthest insertion" method yields a path 1.08 times longer. — The route generation process for a single 50-city problem. The Learned Policy (left) produced a route 1.12 times longer than the OR-Tools baseline, while Farthest-Insertion (right) produced a route 1.08 times longer. The table below shows the averages across multiple problems.

+12%Example with 50 cities (locations) — a longer route compared to the result from OR-Tools.
Improvement status unconfirmedShortcut learning compared to random-sequence insertion
2 thingsCause identified in the code

Expectations
Select a city that results in a shorter path, based on the learned Q-values.
Judgment at the time
Route cost fell as training went on but never reached the optimum; I put it down to too little exploration with many cities
Actual
Since the Q-values for all cities were identical, they were selected in numerical order.
Cause
Values spiked due to the sum of neighbors without normalization, and the TD target considered only the starting city.

Problem and solution

ProblemThe matrix size changes with the number of cities, so it could not be fed directly into a neural network with a fixed input size.
ResolveStructure2Vec builds an embedding for each city, and an evaluation network assigns a Q-value to every unvisited city.
ProblemSimply selecting the next city does not determine its specific position within the route.
ResolveA hybrid approach was used: a learned model handles city selection, while a heuristic determines the insertion point that results in the smallest increase in total route length.
ProblemEven when a short path is generated, it is difficult to distinguish whether this is due to the learning effect or the insertion rules.
Analysis and verificationWe applied the same insertion rules to random city sequences for comparison, tracking the Q-values and TD targets. In the "shortcut learning" scenario, we observed no improvement in the learning policy.

Experiment comparison and detailed results

A comparison between the path generated by the learned policy and the path produced by OR-Tools for the same 50 cities. The path from the learned policy is 1.12 times longer and features a long, intersecting edge on the left side. — The completed paths. The path generated by the learning policy (left) is 1.12 times longer than the OR-Tools path, and the long edges intersect.

Four stages showing the construction of a route for a 20-city problem. The selected cities, disconnected edges, and newly added edges are displayed. — This is the method for creating a path. When the policy selects the next city (orange dot), the insertion function breaks an existing edge (dotted line) at the point where the path length increases the least, and connects it with a new edge.

Average route length ratios by method for 50-city and 100-city problems: Learned Policy (1.13 and 1.12), Random-Order Insertion (1.14 and 1.13), and Farthest-Insertion (1.05 and 1.06). — Average path length with OR-Tools set to 1.00. The learning policy was almost the same as random ordered insertion, and was longer than simple closest insertion.

Average route length relative to the OR-Tools solution · trained on 30–400 cities · the learned policy produced the same route with all three seeds
Number of cities (number of problems)	Training policy	Random sequence + insertion	Insert Primitive	Nearest neighbor	Training policy vs. random (Wilcoxon p)
20 (100) · Outside the scope of learning	1.11	1.11	1.03	1.18	0.96
50 (50)	1.13	1.14	1.05	1.21	0.24
100 (30)	1.12	1.13	1.06	1.22	0.38

Observed causes and remaining challenges.

Q value explodes
Summing across the entire complete graph without normalization caused Q-values to reach the millions, and the update loss spiked to the order of 10¹⁵.
TD target error
The target value was being calculated based on the Q-value of the starting city rather than the remaining city, and the state at the n-step mark was also shifted by one position.
Reduced to 100 episodes
Since a large graph takes about 45 seconds per episode, 10,000 iterations would exceed 5 days per seed. I reduced only the number of iterations while keeping the other settings the same.

Criteria for interpreting results

Not an exact reproduction of the original paper (no target network; the n-step method differs)
Training on only 1% of the defined episodes
Performance after full training is unknown

Areas for improvement in the next experiment

Check against the correct answer using a smaller-scale problem first
Normalization of neighbor sums and adjustment of target values
Establishing a random-sequence baseline

Points connecting to recent projects

This was the first research in which I implemented a neural network in code myself. Representing graph elements and their relationships as training inputs led to my current research on recognizing furniture panels and faces.

AI that recognizes furniture panels and calculates resizing rules