Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning
This addresses the need for efficient and diverse solution generation in combinatorial optimization problems like TSP and CVRP, though it is incremental as it builds on existing neural methods.
The paper tackles the Multi-Solution Travelling Salesman Problem by proposing a deep reinforcement learning solver that finds diverse, high-quality solutions, achieving competitive performance against state-of-the-art heuristics with computational speedups of 1.3× to 15× faster.
Existing neural methods for the Travelling Salesman Problem (TSP) mostly aim at finding a single optimal solution. To discover diverse yet high-quality solutions for Multi-Solution TSP (MSTSP), we propose a novel deep reinforcement learning based neural solver, which is primarily featured by an encoder-decoder structured policy. Concretely, on the one hand, a Relativization Filter (RF) is designed to enhance the robustness of the encoder to affine transformations of the instances, so as to potentially improve the quality of the found solutions. On the other hand, a Multi-Attentive Adaptive Active Search (MA3S) is tailored to allow the decoders to strike a balance between the optimality and diversity. Experimental evaluations on benchmark instances demonstrate the superiority of our method over recent neural baselines across different metrics, and its competitive performance against state-of-the-art traditional heuristics with significantly reduced computational time, ranging from $1.3\times$ to $15\times$ faster. Furthermore, we demonstrate that our method can also be applied to the Capacitated Vehicle Routing Problem (CVRP).