利用强化学习构建、合并、求解与适应的最小-最大多旅行商问题

The Multiple Traveling Salesman Problem (mTSP) extends the Traveling Salesman Problem to multiple tours that start and end at a common depot while visiting all customers exactly once. In the min-max variant, the objective is to minimize the longest tour, reflecting workload balance. A hybrid approach, termed Reinforcement Learning-based Construct, Merge, Solve & Adapt (RL-CMSA), is proposed for the symmetric single-depot min-max mTSP. This method iteratively constructs diverse solutions using probabilistic clustering guided by learned pairwise q-values, merges routes into a compact pool, solves a restricted set-covering MILP, and refines solutions through inter-route remove, shift, and swap moves. The q-values are updated by reinforcing city-pair co-occurrence.