| This thesis studies the traveling salesman problem (TSP) through classical heuristics,
reinforcement-learning-inspired metaheuristics, and learned neural solvers, with the long-term
goal of integrating those methods into Redux, an interactive pedagogical system for NP-hard
and NP-complete problems. The work compares nearest-neighbor, 2-opt multi-start, Ant-Q,
graph neural network (GNN) solvers, and reinforcement learning (RL) policies. A major
contribution is the redesign of an RL approach from constructive routing to local-search
improvement over 2-opt actions. The thesis also examines behavior-cloning pretraining, sizematched retraining for learned models, runtime-quality tradeoffs, and visualization design for
explaining solver behavior. An additional extension considers RL3, a variable-size candidatebased local-improvement policy, as a more practical learned target for Redux because it
is better aligned with user-selected instances than fixed-size learned models. The broader
goal is not simply to improve TSP solver performance, but to use TSP as an accessible
optimization problem for showing how machine-learning-based solvers make decisions on
complex combinatorial tasks.
Keywords: TSP, NP-hard problems, NP-complete problems, reinforcement learning, graph
neural networks, Ant-Q, 2-opt, visualization, Redux |