We introduce the $k$-Interconnected Multi-Depot Multi-Traveling Salesmen Problem, a new problem that resembles some network design and location routing problems but carries the inherent difficulty of not having a fixed set of depots or terminals. We …