  In this work, we consider the problem of finding a set of tours to a
traveling salesperson problem (TSP) instance maximizing diversity, while
satisfying a given cost constraint. This study aims to investigate the
effectiveness of applying niching to maximize diversity rather than simply
maintaining it. To this end, we introduce a 2-stage approach where a simple
niching memetic algorithm (NMA), derived from a state-of-the-art for
multi-solution TSP, is combined with a baseline diversifying algorithm. The
most notable feature of the proposed NMA is the use of randomized
improvement-first local search instead of 2-opt. Our experiment on TSPLIB
instances shows that while the populations evolved by our NMA tend to contain
clusters at tight quality constraints, they frequently occupy distant basins of
attraction rather than close-by regions, improving on the baseline
diversification in terms of sum-sum diversity. Compared to the original NMA,
ours, despite its simplicity, finds more distant solutions of higher quality
within less running time, by a large margin.
