Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks
This addresses a generalization of the Traveling Salesmen Problem that is less studied, providing a novel solution for optimization tasks in logistics and routing.
The paper tackles the Multiple Traveling Salesmen Problem by designing a neural network solution that treats salesmen, cities, and depot as sets, combining set-based and graph network architectures with constraint-enforcing layers and a dedicated loss, resulting in outperforming all meta-heuristics of the leading solver in the field.
While there are optimal TSP solvers, as well as recent learning-based approaches, the generalization of the TSP to the Multiple Traveling Salesmen Problem is much less studied. Here, we design a neural network solution that treats the salesmen, cities and depot as three different sets of varying cardinalities. We apply a novel technique that combines elements from recent architectures that were developed for sets, as well as elements from graph networks. Coupled with new constraint enforcing output layers, a dedicated loss, and a search method, our solution is shown to outperform all the meta-heuristics of the leading solver in the field.