Reinforcement learning for TSP
Learning routes in a combinatorial environment
Exploring DQN for the traveling salesman problem through a custom environment, training code, and baseline-solving scripts.
ROLE
Implementation and experimentation
APPROACH
DQN · TSP · Optimization
Research question
Route optimization provides a concrete setting for learning sequential decisions under constraints. I formulated city selection as a reinforcement-learning task, implementing the environment and DQN components needed to connect travel cost, action choices, and policy updates.
My contribution
- Implemented a custom Gym environment tracking the current city, visited flags, and accumulated distance.
- Connected a PyTorch Q-network, experience replay, epsilon-greedy exploration, and a periodically synchronized target network.
- Prepared dynamic-programming and LKH scripts for exploring comparisons with classical optimization.
Technical approach
- Represent route construction through the current city, visit history, and accumulated distance; select a city at each decision step.
- Use negative Euclidean travel distance as step reward and penalize revisits, linking the optimization objective to the learning signal.
- Train Q-values from replayed transitions with a temporal-difference loss and target-network updates, and inspect routes alongside dynamic-programming and LKH tooling.
Results & outcomes
- Built an executable route-learning workflow spanning problem formulation, environment implementation, DQN training, and route inspection.
- The project connects combinatorial optimization with reinforcement-learning components, providing a practical setting for studying how state and reward design shape sequential choices.