A neural solver that produces a set of diverse yet near-optimal tours for the Multi-Solution TSP (MSTSP), trained end-to-end with deep reinforcement learning over an encoder-decoder policy. Its encoder applies a Relativization Filter, re-expressing each city in relative Cartesian and polar coordinates so the learned representation is invariant to affine transformations (translation, rotation, scaling) of an instance. Its decoding uses Multi-Attentive Adaptive Active Search, running several attention decoders whose reinforcement-learning baseline is adapted per decoder to balance individual tour optimality against inter-solution diversity, with quality-and-diversity scored by a Multi-Solution Quality Index. The same solver transfers to the Capacitated Vehicle Routing Problem.
The Multi-Solution Travelling Salesman Problem (MSTSP) asks for a set of diverse yet near-optimal tours rather than a single shortest tour, because many real TSP instances admit many optimal or near-…