Has deep learning helped improve solving the Traveling Salesman Problem (TSP), such as by discovering better heuristics?
It seems so, as reinforcement learning (RL) has helped discover more efficient matrix multiplication algorithms.
related: "Can neural networks efficiently solve the traveling salesmen problem?"
Deep learning may not yet improve TSP's known best optimization algorithm, however, there's some DL research to learn TSP's and related problems' heuristics directly from training data in an end-to-end fashion, especially through RL and GNNs. A recent paper is Kool et al's 2019 "Attention, Learn to Solve Routing Problems!".
we propose a model based on attention layers with benefits over the Pointer Network and we show how to train this model using REINFORCE with a simple baseline based on a deterministic greedy rollout, which we find is more efficient than using a value function. We significantly improve over recent learned heuristics for the Travelling Salesman Problem (TSP), getting close to optimal results for problems up to 100 nodes. With the same hyperparameters, we learn strong heuristics for two variants of the Vehicle Routing Problem (VRP), the Orienteering Problem (OP) and (a stochastic variant of) the Prize Collecting TSP (PCTSP), outperforming a wide range of baselines and getting results close to highly optimized and specialized algorithms.
However, the challenge of extrapolating reliably to all possible instances remains, and DL approaches are generally seen as complementary to, rather than outright replacements for, classical optimization algorithms.
