Solving Min-Max MTSP in a Reinforcement Learning context
Anda Buinoschi-Tirpescu, Mihaela Elena Breaban · Procedia Computer Science · 2024
Min-Max Multiple Travelling Salesmen Problem (MTSP) is a generalization of the well-known Travelling Salesmen Problem (TSP), with wide practical applicability, standing at the core of many scheduling and routing problems. Because of its complexity, there are many heuristics proposed in the literature to tackle the problem, very few coming lately from the field of Reinforcement Learning (RL). This paper investigates the feasibility of these latter approaches by studying RL-based methods for MTSP and bringing new enhancements to an existing technique, based on treating symmetrical states of the environment and on explicitly encoding visits information in order to handle the non-stationary character of the environment. Experiments are reported on instances from the mTSPLib benchmark.