Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning

As a practical and crucial supplement to the classic TSP, it is Existing neural methods for the Travelling Salesman Problem (TSP) highly desired in many real-world scenarios, where a single solution mostly aim at finding a single optimal solution. To discover diverse may be insufficient. For example, 1) when the single target route yet high-quality solutions for Multi-Solution TSP (MSTSP), we propose (solution) becomes unavailable due to unexpected circumstances, a novel deep reinforcement learning based neural solver, which MSTSP offers desirable alternatives; 2) while the single target route is primarily featured by an encoder-decoder structured policy. Concretely, may overlook other important metrics like user preferences, MSTSP on the one hand, a Relativization Filter (RF) is designed to allows for personalized choices among a set of high-quality candidate enhance the robustness of the encoder to affine transformations of routes; 3) while the single target route may incur spontaneous the instances, so as to potentially improve the quality of the found and simultaneous pursuit of the same choice, MSTSP can distribute solutions. On the other hand, a Multi-Attentive Adaptive Active users or loads across different routes, potentially mitigating the jam Search (MA3S) is tailored to allow the decoders to strike a balance and enhancing the overall performance.