FURI | Spring 2025

Generating Near-optimal Solutions for the Traveling Salesman Problem (TSP) Via Reinforcement Learning (RL)

The traveling salesman problem (TSP) has broad applicability in multiple industries, making improved approximate solutions critical. Computing an optimal tour for TSP can be formulated as a shortest path problem on a decision tree, which is generally exponentially expensive. Reinforcement learning (RL) addresses scalability issues by generating approximately optimal paths via heuristics. This project uses an auction-based path-finding heuristic within an RL framework. It is suited to TSP, as it computes paths without enumerating all subtours. The research group then compares it to a greedy heuristic and the optimal solution, showing that this approach effectively generates near-optimal solutions for TSP.