A Hybrid Machine Learning-Optimization Framework for Enhanced TSP Solutions
TL;DR
This work proposes a hybrid framework combining machine learning and traditional optimization techniques to solve the Traveling Salesman Problem efficiently, using an encoder-decoder neural network with local attention to predict near-optimal city sequences by training on smaller TSP instances.
Abstract
This work proposes a hybrid framework combining machine learning and traditional optimization techniques to solve the Traveling Salesman Problem (TSP) efficiently. Using an encoder-decoder neural network with local attention, the framework learns to predict near-optimal city sequences by training on smaller TSP instances. Its design includes a generalization method, enabling the framework to adapt these learned patterns to larger problems by leveraging the temporal structure of city sequences. A feasibility-check loop iteratively refines the initial solution to ensure the predicted solutions are feasible. It also removes infeasible segments using an optimization solver to produce a valid, near-optimal tour. The framework is particularly well-suited for logistics and route planning applications, where efficiency and accuracy are critical issues. Experimental results are presented comparing the approach to traditional TSP-solving techniques.