Paper deep dive

Construct, Merge, Solve & Adapt with Reinforcement Learning for the min-max Multiple Traveling Salesman Problem

Guillem Rodríguez-Corominas, Maria J. Blesa, Christian Blum

Year: 2026Venue: arXiv preprintArea: cs.AIType: PreprintEmbeddings: 60

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%

Last extracted: 7/20/2026, 8:16:30 AM

Summary

The paper proposes RL-CMSA, a hybrid metaheuristic for the symmetric single-depot min-max Multiple Traveling Salesman Problem (mTSP). It combines reinforcement learning-guided probabilistic clustering, a candidate pool merge strategy, exact set-covering MILP solving, and local search improvements. The method uses Q-learning to reinforce city-pair co-occurrences in high-quality solutions, balancing exploration and exploitation to outperform state-of-the-art hybrid genetic algorithms.

Entities (7)

RL-CMSA · algorithm · 98%min-max mTSP · problem · 97%Q-learning · technique · 94%MILP · method · 93%Hybrid Genetic Algorithm · algorithm · 92%CPLEX · software · 90%TSPLIB · dataset · 88%

Relation Signals (5)

RL-CMSA → solves → min-max mTSP

confidence 98% · We propose a hybrid approach... for the symmetric single-depot min-max mTSP.

RL-CMSA → uses → Q-learning

confidence 95% · RL-CMSA [8], which augments standard CMSA with a Q-learning mechanism to guide and adapt key decisions during the search.

RL-CMSA → uses → MILP

confidence 93% · The method iteratively constructs diverse solutions... solves a restricted set-covering MILP

RL-CMSA → outperforms → Hybrid Genetic Algorithm

confidence 92% · RL-CMSA consistently finds (near-)best solutions and outperforms a state-of-the-art hybrid genetic algorithm under comparable time limits

MILP → solvedby → CPLEX

confidence 90% · The resulting subproblem is solved with CPLEX, a state-of-the-art MILP solver.

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:The Multiple Traveling Salesman Problem (mTSP) extends the Traveling Salesman Problem to m tours that start and end at a common depot and jointly visit all customers exactly once. In the min-max variant, the objective is to minimize the longest tour, reflecting workload balance. We propose a hybrid approach, Construct, Merge, Solve & Adapt with Reinforcement Learning (RL-CMSA), for the symmetric single-depot min-max mTSP. The 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 via inter-route remove, shift, and swap moves. The q-values are updated by reinforcing city-pair co-occurrences in high-quality solutions, while the pool is adapted through ageing and pruning. This combination of exact optimization and reinforcement-guided construction balances exploration and exploitation. Computational results on random and TSPLIB instances show that RL-CMSA consistently finds (near-)best solutions and outperforms a state-of-the-art hybrid genetic algorithm under comparable time limits, especially as instance size and the number of salesmen increase.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

58,645 characters extracted from source content.

Expand or collapse full text

Construct, Merge, Solve & Adapt with Reinforcement Learning for the min–max Multiple Traveling Salesman Problem Guillem Rodríguez-Corominas Artificial Intelligence Research Institute (IIIA-CSIC), Bellaterra, Catalunya, Spain grodriguez@iiia.csic.es, christian.blum@iiia.csic.es Universitat Politècnica de Catalunya (UPC), Barcelona, Catalunya, Spain maria.j.blesa@upc.edu Maria J. Blesa Universitat Politècnica de Catalunya (UPC), Barcelona, Catalunya, Spain maria.j.blesa@upc.edu Christian Blum Artificial Intelligence Research Institute (IIIA-CSIC), Bellaterra, Catalunya, Spain grodriguez@iiia.csic.es, christian.blum@iiia.csic.es Abstract The Multiple Traveling Salesman Problem (mTSP) extends the Traveling Salesman Problem to m tours that start and end at a common depot and jointly visit all customers exactly once. In the min–max variant, the objective is to minimize the longest tour, reflecting workload balance. We propose a hybrid approach, Construct, Merge, Solve & Adapt with Reinforcement Learning (RL-CMSA), for the symmetric single-depot min–max mTSP. The 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 via inter-route remove, shift, and swap moves. The q-values are updated by reinforcing city-pair co-occurrences in high-quality solutions, while the pool is adapted through ageing and pruning. This combination of exact optimization and reinforcement-guided construction balances exploration and exploitation. Computational results on random and TSPLIB instances show that RL-CMSA consistently finds (near-)best solutions and outperforms a state-of-the-art hybrid genetic algorithm under comparable time limits, especially as instance size and the number of salesmen increase. Keywords: Multiple Traveling Salesman Problem, Construct, Merge, Solve & Adapt, Reinforcement Learning 1 Introduction The Multiple Traveling Salesman Problem (mTSP) generalizes the TSP to m tours that start and end at a common depot and collectively visit each customer exactly once. It can be viewed as a simplified vehicle routing problem (VRP) without vehicle capacities or time windows [11, 7]. Two objectives are usually considered: (i) minimizing total traversal cost (the min-sum mTSP) and (i) minimizing the length of the longest tour among the m tours (the min–max mTSP). The min–max criterion is particularly relevant when balancing workload or service time is important, as in last-mile delivery with identical vehicles, coordinated multi-robot patrolling, UAV sortie planning, or technician routing, where fairness and service-level constraints are crucial [14]. This paper focuses on the single-depot min–max mTSP on symmetric graphs, a setting that captures many practical applications while remaining computationally challenging. Formally, let G=(V,E)G=(V,E) be a complete undirected graph with V=0,1,…,nV=\0,1,…,n\, where 0 denotes the depot and DijD_ij is the metric cost of edge (i,j)(i,j). The task is to construct m closed routes ℛ1,…,ℛm\R_1,…,R_m\ that (i) are node-disjoint except for the depot, (i) cover 1,…,n\1,…,n\ exactly once, and (i) minimize maxk=1,…,m⁡len(ℛk) _k=1,…,mlen(R_k), where len(⋅)len(·) is the tour cost. The problem is NP-hard even for metric instances by reduction from the TSP and balanced partitioning arguments. Consequently, exact algorithms scale only to modest sizes, while heuristics and metaheuristics dominate large-instance practice. In recent years, hybrid metaheuristics that combine heuristic search with exact optimization components have shown strong potential for tackling difficult combinatorial problems. Along these lines, we build on the Construct, Merge, Solve & Adapt (CMSA) framework, which is itself a hybrid metaheuristic integrating constructive solution generation with an exact solving phase. In particular, we consider its Reinforcement Learning extension, RL-CMSA [8], which augments standard CMSA with a Q-learning mechanism to guide and adapt key decisions during the search. We argue that this additional learning-driven adaptation can be especially beneficial for the problem studied in this paper. 2 Related Work Methodologically, mTSP algorithms largely follow the standard routing taxonomy: exact approaches (e.g., branch-and-cut on arc/flow models with subtour elimination, or set-partitioning with branch-and-price) and heuristics/metaheuristics that trade optimality guarantees for scalability [10, 13]. Within the latter, two recurring design patterns are cluster-first route-second (assign customers to m salesmen via balanced partitioning methods and then solve m TSPs) and route-first cluster-second (build a giant tour and optimally split it into m routes via shortest-path or dynamic-programming procedures) [5]. Modern hybrids strengthen these templates with powerful local search (e.g., 2-opt/Or-opt/k-exchange), tailored recombination, and diversity control, often yielding state-of-the-art performance in both min-sum and min–max settings. Figure 1: RL-CMSA: Schematic Algorithm Overview Genetic Algorithms are particularly prominent in the mTSP literature, evolving either explicit multi-route representations or TSP-like permutations with route delimiters, combined with selection and diversity mechanisms and typically hybridized with local improvement [4]. For the min–max mTSP, a strong representative is the Hybrid Genetic Algorithm (HGA) of [5], which encodes solutions as TSP sequences, evaluates individuals through a DP-based Split tailored to the min–max objective, and combines a similarity-aware crossover with both inter- and intra-route local search (e.g., 1-shift/1-swap/Or-opt/2-opt), plus intersection handling. When tested on four standard benchmark suites—including, for example, TSPLIB instances and random instances—the HGA achieves state-of-the-art average performance under comparable cutoffs and improves best-known results on a substantial subset of instances, making it a leading baseline for our setting. Therefore, in this paper, we study the min–max mTSP under the same modeling assumptions and use the HGA as a strong baseline for comparison. Beyond GAs, mTSP variants have been tackled by Ant Colony Optimization [15], Artificial Bee Colony [12], Invasive Weed Optimization [13], General Variable Neighborhood Search [10], and Memetic Algorithms [14, 2], to name a few. For the min–max variant, competitive examples include the Hybrid Search with Neighborhood Reduction (HSNR) [1], which alternates tabu-based inter-tour moves with EAX-based intra-tour improvement; and the Iterated Two-Stage Heuristic (ITSHA) [16], combining randomized or clustering-based initialization with variable neighborhood improvement (2-opt/insert/swap). Finally, Reinforcement Learning (LR) and GNN-based methods have emerged as promising alternatives. Notable examples include multi-agent RL frameworks (e.g., ScheduleNet) [6] and Neuro–Cross Exchange (NCE), which learns to activate a cross-exchange neighborhood [3]. These methods can produce competitive solutions quickly, though classical/hybrid metaheuristics still dominate many standard benchmarks under typical time budgets. 3 The Proposed Algorithm A schematic overview of our RL-CMSA algorithm is given in Figure 1. The algorithm iterates through six phases—Construct, Merge, Solve, Improve, Learn, and Adapt—until the stopping criterion is met (here, a time limit). In the following sections, all algorithm components are explained in detail. 3.1 Construct In the first phase of the algorithm, we generate nsolutionsn_solutions candidate solutions through a probabilistic construction process. Each construction is divided into two stages: Cluster and Route. Cluster stage: The goal of this stage is to partition the set of cities V (excluding the depot) into m clusters, one for each vehicle. The intuition is that cities that are likely to belong to the same route should be grouped together. Algorithm 1 provides pseudocode for this procedure. The clustering process begins by selecting m centers, which serve as the initial representatives for each cluster (see Seeding). These centers are chosen using a k-means++ style seeding procedure, biased by the q-values of city pairs (see lines 1-12 of Algorithm 1): 1. The first center is sampled from the non-depot cities with probability proportional to the squared distance from the depot. 2. Each subsequent center is chosen using a roulette-wheel selection, where the probability of selecting a city i depends on its squared distance to the nearest already-chosen center, adjusted by the corresponding q-value. This ensures that centers are both well separated and more likely to belong to different optimal routes. Figure 1 illustrates this process, where the chosen centers are marked with a star. After the centers are chosen, the remaining cities are assigned to clusters (Assignment). The so far unassigned cities from U are then assigned one by one to the clusters using a weighted assignment mechanism (see lines 13-32 of Algorithm 1). Cities with smaller angular distance (with respect to the depot) to a center (angdist(θu,θcj)angdist( _u, _c_j)) are more likely to be processed earlier. For each candidate city u, we compute the approximate assignment cost into each cluster CjC_j, defined as the distance to its two closest points in that cluster, including the depot when applicable (function twoClosestPoints()). When scoring the assignment of a city u into a cluster CjC_j (see line 26), we scale the cost by two additional factors: (i) the mean Q-compatibility between u and all current members of CjC_j, excluding the depot (see line 24), and (i) a running estimate ru,jr_u,j of how the max length would increase if the city is added to this cluster (see line 25).111Note that du,jd_u,j and LjapproxL^approx_j are proxies computed from anchor distances and are used only to guide clustering. Actual tours are constructed in the subsequent Route stage. Note that a small ε>0 >0 is added for numerical stability. Once the costs are computed, with probability drateconstructd_rate^construct, the city is assigned to the cluster with the lowest score. Ties are broken uniformly at random using reservoir sampling. Otherwise, the cluster is chosen with probabilities pj∝1sjp_j\; \; 1s_j. The factor LjapproxL^approx_j is updated incrementally after each insertion using the corresponding two-anchor insertion cost, which implicitly encourages load balancing by penalizing already long provisional routes. This procedure is repeated until all cities have been assigned to clusters. Input: D: pairwise distances; Q: q-values; m: # routes Output: ℛ=C1,…,CmR=\C_1,…,C_m\: m clusters Phase 1: Seeding Initialize U←V∖0U← V \0\ ; // Non-depot cities Initialize wi←D0,i2w_i← D_0,i^2 for all i∈Ui∈ U; for j=1j=1 to m do Sample center cj∈Uc_j∈ U with probability ∝wi w_i; U←U∖cjU← U \c_j\; Initialize cluster Cj← 0,cjC_j←\\,0,\,c_j\,\; Initialize Ljapprox←2⋅D0,cjL^approx_j← 2· D_0,c_j; foreach i∈Ui∈ U do wi←min⁡wi,Di,cj2⋅Qi,cj2w_i← \\,w_i,\;D_i,c_j^2· Q_i,c_j^2\,\; end foreach end for Phase 2: Assignment foreach u∈Uu∈ U do δu←minj=1,…,m⁡angdist(θu,θcj) _u← _j=1,…,mangdist( _u, _c_j); end foreach while U≠∅U≠ do Sample city u∈Uu∈ U with probability ∝1/δu 1/ _u; U←U∖uU← U \u\; Lmaxapprox←maxj=1,…,m⁡LjapproxL_ ^approx← _j=1,…,mL^approx_j; foreach j=1,…,mj=1,…,m do a,b←twoClosestPoints(u,Cj,D)\a,b\← twoClosestPoints(u,C_j,D); du,j←Du,a+Du,b−Da,bd_u,j← D_u,a+D_u,b-D_a,b; qu,jmean←1|Cj∖0|∑v∈Cj,v≠0Qu,vq^mean_u,j← 1|C_j \0\| _v∈ C_j,\ v≠ 0Q_u,v; ru,j←max⁡(Lmaxapprox,Ljapprox+du,j)/Lmaxapproxr_u,j← \! (L_ ^approx,\,L^approx_j+d_u,j )/L_ ^approx; sj←(du,j+ε)⋅ru,j⋅qu,jmeans_j←(d_u,j+ )· r_u,j· q^mean_u,j; end foreach With probability drateconstructd_rate^construct: choose j⋆∈arg⁡minj⁡sjj ∈ _js_j; Otherwise: sample j⋆j with probability pj∝1/sjp_j 1/s_j; Cj⋆←Cj⋆∪uC_j ← C_j ∪\u\; Lj⋆approx←Lj⋆approx+du,j⋆L^approx_j ← L^approx_j +d_u,j ; end while return ℛ=C1,…,CmR=\C_1,…,C_m\; Algorithm 1 Clustering algorithm biased by q-values Route stage: Once the clustering is complete, we build one route per cluster using a fast greedy insertion heuristic. Starting from the depot, we construct a tour for each cluster using best-insertion into the partial route. The resulting tour is then improved by applying intra-route local search: first a 2-opt procedure and then an Or-opt procedure restricted to relocating sequences of length 1 and 2. Both local searches scan candidate moves in random order and apply first improvement, to avoid systematic bias. This produces high-quality cluster tours at low computational cost. After all routes of a solution have been constructed, we apply the inter-route improvement operators described in Section 3.4. To reduce computational cost, we restrict the neighborhood to moves involving the longest route only, rather than considering all route pairs. By repeating the above procedure nsolutionsn_solutions times, RL-CMSA generates a set of nsolutionsn_solutions solutions to the problem. 3.2 Merge Next, in the Merge step of RL-CMSA (see the center of Figure 1), the nsolutions×mn_solutions× m routes generated in the Construct step are added to the pool ℛcandR_cand of candidate routes. Each route stored in ℛcandR_cand is assigned an age value, which is initialized to 0 upon insertion.222This will be important for the Adapt step explained in Section 3.6. Since the construction process may generate multiple routes visiting the same set of non-depot cities, we keep only one representative per visited-city set, namely the shortest one. To do so, we compute a canonical signature for each route by sorting its non-depot cities. This signature is then used for hashing and equality checks when inserting into ℛcandR_cand. Finally, we prune ℛcandR_cand by discarding any route whose length exceeds the current incumbent max-route length. Such routes will never be selected by the solver (as explained in the following section), and keeping them would only bias the subsequent learning step. 3.3 Solve After the Merge step, RL-CMSA conducts the Solve step (top right of Figure 1) to determine the best solution that can be assembled from the candidate pool ℛcandR_cand. We formulate a set-covering MILP that selects exactly m routes while ensuring that every non-depot city is covered at least once, and minimizes the length of the longest selected route. The resulting subproblem is solved with CPLEX, a state-of-the-art MILP solver. More formally, let xr∈0,1x_r∈\0,1\ be a binary variable indicating whether route r∈ℛcandr _cand is selected, and let z be an upper bound on the maximum length among selected routes. The model is: min z z s.t. z≥ℓr−M(1−xr) z≥ _r-M(1-x_r) ∀r∈ℛcand ∀ r _cand ∑r∈ℛcandxr=m _r _candx_r=m ∑r∋ixr≥1 _r ix_r≥ 1 ∀i∈V∖0 ∀ i∈ V \0\ where ℓr _r denotes the length of route r and M is a sufficiently large constant. Note that not forcing each city to be covered by only one route allows for greater flexibility. However, as the selected routes may overlap, the output ℛbestR_best is not necessarily a valid mTSP solution yet, and duplicates are resolved in the subsequent Improve step. Note that we can impose z to be bounded by the current incumbent best solution, which justifies pruning such routes from ℛcandR_cand in the previous step. 3.4 Improve In the Improve step of RL-CMSA (see bottom right in Figure 1), ℛbestR_best is refined by applying a series of local improvement operations to its routes. The primary objective is to minimize the length of the longest route in ℛbestR_best, henceforth denoted by z. 3.4.1 Remove This step turns ℛbestR_best into a feasible solution (if necessary) by removing non-depot cities occurring in more than one route in the following way. For each duplicated city, we evaluate the potential decrease in route length that would result from removing the city from a given route by directly connecting its predecessor and successor. Let u denote the city to be removed, and let a and b be its predecessor and successor in the route, respectively. The removal improvement Δremove _remove is defined as Δremove(u)=Dau+Dub−Dab. _remove(u)\;=\;D_au+D_ub-D_ab . Once these improvement values have been computed for all duplicated cities across all routes, we proceed as follows: with probability drateimproved_rate^improve, we remove the city yielding the highest removal improvement; otherwise, we select a city to remove using a roulette-wheel mechanism, with probabilities proportional to their respective Δremove _remove values. These values are scaled by the respective current route length to prioritize deletions from longer routes. This process is repeated iteratively until every non-depot city appears in exactly one route. 3.4.2 Shift: cross-route relocation (1-move) Aiming for further improvement, we attempt to shift a single city u across routes, that is, to relocate it from its current source route into some position within a different target route of ℛbestR_best. The goal of this operation is to reduce the total route length by moving cities that are poorly placed, i.e., far from their neighboring cities, into routes that are closer. For all eligible cities and insertion positions, the following values are computed: Δsrc−(u)=Dau+Dub−Dab(removal gain), ^-_src(u)=D_au+D_ub-D_ab (removal gain), Δtgt+(p,u)=Dcu+Dud−Dcd(insertion cost), ^+_tgt(p,u)=D_cu+D_ud-D_cd (insertion cost), where a and b are the predecessor and successor of u in its source route, and (c,d)(c,d) denotes the edge at the target insertion position p. Therefore, a relocation move has a net value given by: Δshift=Δsrc−(u)−Δtgt+(p,u), _shift= ^-_src(u)- ^+_tgt(p,u) , and is considered admissible only if the maximum route length after applying the move does not exceed z. Note that, with Δshift>0 _shift>0, the move strictly improves the secondary objective (total length), so it is unambiguously beneficial. Since the primary objective is to minimize the length of the longest route in ℛbestR_best, we also allow admissible moves with Δshift<0 _shift<0: these may slightly increase the total length but still improve the main objective. To balance exploitation and exploration, we select among admissible moves as follows: with probability drateimproved_rate^improve we select the best move; otherwise we sample a move via roulette–wheel with probabilities proportional to exp⁡(Δshiftz) \! ( _shiftz ). This weighting favors moves that reduce both z and the total length (Δshift>0 _shift>0), while still giving a small but nonzero chance to moves with Δshift<0 _shift<0 when they reduce z, our primary objective. After applying the chosen move, only the affected Δ values around the modified positions are incrementally updated. This repeats iteratively until no admissible relocation remains. 3.4.3 Swap: cross-route exchange (1–1 swap) In this phase, we attempt to swap two cities u and v belonging to different routes from ℛbestR_best, rsrcr_src and rtgtr_tgt (src≠tgtsrc≠tgt), respectively. The objective is to further reduce route lengths by exchanging cities that may be better suited to each other’s routes. The incremental cost of such a swap is evaluated locally around the affected positions in each route. Let a and b denote the predecessor and successor of u in rsrcr_src, and c and d those of v in rtgtr_tgt. The respective local cost variations are computed as: Δsrc(u↔v)=(Dau+Dub)−(Dav+Dvb), _src(u v)=(D_au+D_ub)-(D_av+D_vb), Δtgt(u↔v)=(Dcv+Dvd)−(Dcu+Dud). _tgt(u v)=(D_cv+D_vd)-(D_cu+D_ud). The total gain from performing the swap is then given by: Δswap=Δsrc(u↔v)+Δtgt(u↔v). _swap= _src(u v)+ _tgt(u v). Similarly to the shift move, a swap is considered admissible only if the maximum route length after applying the swap does not exceed z. Furthermore, we also allow moves with Δswap≤0 _swap≤ 0 if they improve the maximum route length z. Again, we select the swap with the maximum Δswap _swap with probability drateimproved_rate^improve. Otherwise, we sample a move using a roulette wheel with probabilities proportional to exp⁡(Δswapz) \! ( _swapz ). After applying the swap, only the cost entries in the neighborhoods of the modified positions are incrementally updated. The process repeats iteratively until no admissible improving swap moves remain. The final solution ℛbestR_best is the current best solution of RL-CMSA. This solution is marked in Figure 1 with a golden, encircled, asterisk. It serves as input to the Learn and Adapt steps, as explained below. 3.5 Learn We estimate two symmetric co-occurrence counts over unordered pairs i,j\i,j\ of non-depot cities: Scand(i,j) S_cand(i,j) =#routes in ℛcand containing both i,j =\#\routes in $ R_cand$ containing both i,j\ Sbest(i,j) S_best(i,j) =#routes in ℛbest containing both i,j =\#\routes in $ R_best$ containing both i,j\ In other words, Sbest(i,j)S_best(i,j) evaluates to either zero or one. For pairs that appear in the candidate pool (Scand(i,j)>0S_cand(i,j)>0), the following update of the corresponding q-values is conducted: Qij←Qij−lrate⋅Qij,if Sbest(i,j)>0(reinforce)Qij+lrate⋅(1−Qij),if Sbest(i,j)=0(discourage).Q_ij← casesQ_ij-l_rate· Q_ij,&if S_best(i,j)>0 (reinforce)\\[2.0pt] Q_ij+l_rate·(1-Q_ij),&if S_best(i,j)=0 (discourage). cases Thus, beneficial pairs drift toward 0 (more likely to end up in the same cluster in the Construct step), while unhelpful pairs drift toward 11. Moreover, a convergence proxy 2(n−1)(n−2)∑i<j|12−Qij| 2(n-1)(n-2) _i<j\! | 12-Q_ij | is monitored over a short time window. If it stagnates, we reset all q-values to 0.5 and clear the sub-instance. 3.6 Adapt In the Adapt step of RL-CMSA (see center left of Figure 1), the sub-instance ℛcandR_cand is updated using an age-based policy. Routes in ℛbestR_best that are not yet in ℛcandR_cand are inserted with age 0. Conversely, the age of each route in ℛcandR_cand that is not part of ℛbestR_best is increased by one. Finally, any route whose age reaches the threshold agemaxage_ is removed. This policy bounds the size of ℛcandR_cand, promotes turnover, and keeps the pool compact and up-to-date with the evolving reinforcement signal. 4 Experimental Evaluation The RL-CMSA algorithm described in the previous section stops at a user-defined computation time limit. It returns the best solution found. To assess the behaviour and applicability of our approach, we compare it with the state-of-the-art HGA algorithm from [5]. All experiments were performed on the Ars Magna computing cluster at IIIA-CSIC (Intel Xeon 2.2 GHz, 10 cores, 92 GB RAM). For each instance, both algorithms were executed with a time limit of n seconds (the number of cities). 4.1 Benchmark Instances We considered two types of benchmark instances. First, and most importantly, we used randomly generated instances. Random instances are the most-used ones in the mTSP literature; however, for the min–max mTSP, they may become unintentionally easy when one or a few cities lie far from the depot. In such cases—especially as the number of vehicles increases—the optimal solution often consists of a few-city route to visit the distant city (or cities), while the remaining routes cover only nearby cities. To mitigate this effect and obtain more challenging instances, we generated random instances as follows: city locations are sampled uniformly at random inside a circle of radius 11, placing the depot at the centre. This construction increases the likelihood that several cities lie near the boundary and thus at comparable distances from the depot. We generated 20 random instances for each n∈50,100,200n∈\50,100,200\. All these instances will be solved for m∈1100n,5100n,10100n,15100nm∈\ 1100n, 5100n, 10100n, 15100n\. In other words, the number of salesmen considered (m) depends on the number of cities (n) and is calculated as 1%1\%, 5%5\%, 10%10\% or 15%15\% of the number of cities (rounded). Second, we also considered instances from TSPLIB, which are commonly used in related work. In particular, we used eil51, berlin52, eil76, and rat99. These instances allow us to evaluate our approach on structured, well-known benchmarks and to test its behaviour across different problem characteristics. 4.2 Algorithm Tuning To ensure good performance of our algorithm, a scientific parameter tuning was performed using i-Race, an automatic algorithm configuration tool. In particular, parameter tuning was performed independently for each considered value of m (see above). For each m, a training set of five additional random instances with 200200 nodes (the largest size considered) was generated. Table 1: Summary of the parameters of RL-CMSA with their respective domain and the tuning results. Parameters Considered Domain Tuning results m=1%m=1\% m=5%m=5\% m=10%m=10\% m=15%m=15\% nsolutionsn_solutions 2,3,…,19,20\2,3,...,19,20\ 1919 1717 1313 1717 drateconstructd_rate^construct 0.00,0.01,…,0.89,0.90\0.00,0.01,...,0.89,0.90\ 0.870.87 0.830.83 0.660.66 0.860.86 drateimproved_rate^improve 0.00,0.01,…,0.99,1.00\0.00,0.01,...,0.99,1.00\ 0.960.96 0.970.97 0.980.98 0.930.93 lratel_rate 0.10,0.11,…,0.49,0.50\0.10,0.11,...,0.49,0.50\ 0.310.31 0.260.26 0.450.45 0.200.20 agemaxage_max 2,3,…,19,20\2,3,...,19,20\ 1212 1313 22 1515 Table 1 reports the parameter domains explored by i-Race and the best configurations obtained. Overall, a clear pattern emerges for m∈1%,5%,15%m∈\1\%,5\%,15\%\: both nsolutionsn_solutions and agemaxage_max take relatively large values, suggesting that maintaining a larger sub-instance is beneficial. In addition, lratel_rate is set to a medium value, indicating that the algorithm tends to learn more slowly. Concerning the determinism rates, drateconstructd_rate^construct and drateimproved_rate^improve are high (the latter is close to 11), which implies that newly constructed solutions are kept close to the current best solution. This behaviour is consistent with an intensification strategy: the algorithm focuses the search in the neighbourhood of the best-so-far solution, and retaining a large sub-instance helps include routes similar to the incumbent, enabling a more thorough local exploration. In contrast, the configuration found for m=10m=10 differs substantially. Here, nsolutionsn_solutions takes a more moderate value and agemaxage_max is very small, which leads to smaller sub-instances and a shorter retention of seemingly bad routes. Combined with a lower value of drateconstructd_rate^construct, this indicates a stronger emphasis on diversification: the algorithm generates more diverse candidates and keeps only the highest-quality ones. Moreover, the relatively high lratel_rate suggests faster convergence. For the HGA algorithm, we used the parameter values reported by the authors in [5]. These values were tuned on a diverse set of instances, including random instances and the TSPLIB instances considered in this study. 4.3 Results Tables 2(a)-(d) summarize the comparative results of RL-CMSA and HGA for each value of m on the random instances. Each row corresponds to one instance (identified by id). For each problem size n∈50,100,200n∈\50,100,200\, the tables report, separately for RL-CMSA and HGA, the average objective value over 4040 independent runs (mean), the number of runs in which the method achieved the best value among the two compared algorithms (#b), and the average time in seconds for finding the best solution of a run (time). In addition, the last column of each table block (regarding n and m) reports the best objective value obtained on that instance across all runs and both algorithms (best). Boldface highlights the best mean value between the two algorithms for the corresponding instance and size, while the shaded cells provide a visual cue of which method performs better (blue for RL-CMSA, red for HGA, and grey for ties). The arrow and bolt symbols indicate, respectively, which algorithm attains a higher best-runs count and which one is faster for the corresponding instance, following the same color pattern. Table 2: Summary of the obtained results on random instances. n 5050 100100 200200 HGA RL-CMSA HGA RL-CMSA HGA RL-CMSA id mean #b time mean #b time best mean #b time mean #b time best mean #b time mean #b time best 0 5.0575160 40 0.87 5.0575160 40 0.04 5.0575160 7.0156623 39 5.60 7.0156453 40 1.41 7.0156453 9.6706542 2 92.60 9.6904399 0 87.50 9.6328396 1 5.3701311 40 1.52 5.3701311 40 0.09 5.3701311 6.8430869 40 6.88 6.8430869 40 0.34 6.8430869 9.3918357 11 90.76 9.3618625 4 77.57 9.3195580 2 5.3316439 40 1.38 5.3316439 40 0.04 5.3316439 7.0299344 40 12.08 7.0299344 40 2.25 7.0299344 9.4244805 2 61.20 9.4208673 4 86.93 9.4005750 3 5.2586716 40 1.27 5.2586716 40 0.04 5.2586716 6.9746008 27 26.94 6.9623471 40 1.91 6.9623471 9.4609795 1 84.39 9.4815937 0 89.62 9.4181420 4 5.2818492 40 4.39 5.2818492 40 3.41 5.2818492 6.5344532 40 2.57 6.5344532 40 0.51 6.5344532 9.5270634 30 61.71 9.5305576 2 96.43 9.5068409 5 5.5771440 40 13.71 5.5771440 40 0.17 5.5771440 7.0521714 38 17.69 7.0521697 40 0.50 7.0521697 9.5016956 21 3.44 9.5576244 0 100.38 9.5016780 6 5.4362003 40 7.77 5.4362003 40 0.21 5.4362003 6.7743343 37 20.44 6.7743163 40 0.25 6.7743163 9.4178382 5 98.84 9.4047427 0 107.28 9.3804741 7 5.1861317 39 1.51 5.1861317 40 0.05 5.1861317 7.1473452 2 17.13 7.1456589 40 3.27 7.1456589 9.8416262 1 78.96 9.8262728 0 109.67 9.7941297 8 5.2554913 40 1.70 5.2554913 40 0.17 5.2554913 7.1174241 40 23.65 7.1174241 40 1.87 7.1174241 9.6955254 23 72.83 9.7544799 0 83.74 9.6632823 9 5.0439071 40 1.89 5.0439071 40 0.18 5.0439071 6.8502046 38 3.39 6.8501996 40 0.19 6.8501996 9.9153469 1 47.17 9.9314959 1 102.36 9.9020767 10 5.4938819 40 2.25 5.4938819 40 0.11 5.4938819 6.9835233 33 41.22 6.9754031 40 5.11 6.9754031 9.4262128 0 92.06 9.4447663 1 90.95 9.3872947 11 5.1127317 40 2.35 5.1127317 40 0.32 5.1127317 7.3087733 3 16.61 7.2843068 40 0.93 7.2843068 9.4586790 0 53.46 9.4140465 8 92.25 9.3869246 12 5.1685487 40 1.56 5.1685487 40 0.07 5.1685487 7.1775547 35 21.11 7.1736817 40 2.14 7.1736817 9.4299383 0 80.90 9.4496652 1 103.29 9.4020946 13 5.4491950 40 1.84 5.4491950 40 0.08 5.4491950 7.1035381 37 19.57 7.1009282 40 0.39 7.1009282 9.6017114 2 106.89 9.5883556 0 96.15 9.5591736 14 5.4295509 40 5.35 5.4295509 40 0.41 5.4295509 7.3270959 9 19.66 7.3128586 40 15.50 7.3128586 9.7496029 19 74.67 9.7945466 0 99.37 9.7342914 15 5.2143740 40 1.28 5.2143740 40 0.07 5.2143740 7.0079489 40 6.27 7.0079489 40 0.63 7.0079489 9.6790111 25 54.16 9.6640371 29 97.16 9.6592723 16 4.9260863 40 1.37 4.9260863 40 0.04 4.9260863 6.6627477 23 20.07 6.6541699 40 8.98 6.6541699 9.6199999 19 52.40 9.6707371 0 113.18 9.5969447 17 5.5142674 40 1.53 5.5142674 40 0.08 5.5142674 7.3124578 16 33.06 7.3035378 40 11.32 7.3035378 9.7159209 4 81.64 9.7271230 0 95.28 9.6979334 18 5.5010121 40 1.91 5.5010121 40 0.03 5.5010121 7.0377697 38 5.22 7.0377389 40 1.40 7.0377389 9.5419951 0 49.03 9.5166366 7 98.41 9.5111777 19 5.3125777 40 1.25 5.3125777 40 0.07 5.3125777 7.1538031 12 25.53 7.1452419 40 8.18 7.1452419 10.0551592 9 101.97 10.1359320 0 96.50 10.0190911 (a) Results for m=1%m=1\% n 5050 100100 200200 HGA RL-CMSA HGA RL-CMSA HGA RL-CMSA id mean #b time mean #b time best mean #b time mean #b time best mean #b time mean #b time best 0 3.8060317 40 1.31 3.8060317 40 0.05 3.8060317 3.3622935 31 14.73 3.3503727 40 12.85 3.3503727 2.7276857 0 68.43 2.7174812 1 79.86 2.7143117 1 3.8893238 40 2.39 3.8893238 40 1.86 3.8893238 3.3650106 5 40.50 3.3585642 36 29.56 3.3584696 2.6392363 0 81.83 2.6373016 6 79.28 2.6334384 2 3.9158255 40 1.27 3.9158255 40 0.04 3.9158255 3.2834014 40 9.64 3.2834014 40 1.23 3.2834014 2.6194326 0 95.05 2.5987804 1 59.89 2.5972380 3 3.7164153 40 1.29 3.7164153 40 0.05 3.7164153 3.2887294 36 7.54 3.2875503 40 0.60 3.2875503 2.6726960 0 53.89 2.6637605 4 96.35 2.6555002 4 3.7717124 40 1.40 3.7717124 40 0.07 3.7717124 3.1383856 15 11.44 3.1265507 40 7.17 3.1265507 2.6468459 0 79.90 2.6385345 2 85.81 2.6326597 5 3.8417454 40 1.48 3.8417454 40 0.05 3.8417454 3.4173598 22 26.93 3.4120586 40 6.11 3.4120586 2.6646631 8 50.16 2.6547707 34 72.79 2.6545120 6 3.8581195 40 1.76 3.8581195 40 0.10 3.8581195 3.2701157 39 14.86 3.2686303 40 4.61 3.2686303 2.6411774 1 50.21 2.6326352 32 77.57 2.6325962 7 3.8385517 40 1.56 3.8385517 40 0.08 3.8385517 3.3440450 20 18.01 3.3407747 40 2.13 3.3407747 2.7314775 20 35.32 2.7178544 34 79.15 2.7166784 8 3.8192852 40 5.49 3.8192852 40 0.15 3.8192852 3.3371203 27 6.85 3.3370511 40 2.59 3.3370511 2.7035522 0 52.76 2.6929041 8 110.25 2.6855182 9 3.7176965 40 2.11 3.7176965 40 0.10 3.7176965 3.3023053 8 8.73 3.2971546 40 3.73 3.2971546 2.6947364 1 67.33 2.6881647 1 92.68 2.6837119 10 3.8777639 37 1.25 3.8777632 40 0.04 3.8777632 3.3361308 12 2.44 3.3360682 40 1.02 3.3360682 2.6646670 0 96.51 2.6547440 1 113.09 2.6445914 11 3.7106351 40 2.83 3.7106351 40 0.26 3.7106351 3.4415860 29 6.61 3.4334664 40 1.40 3.4334664 2.6117045 30 70.40 2.6114520 40 15.54 2.6114520 12 3.8366626 40 1.38 3.8366626 40 0.05 3.8366626 3.3620073 9 1.96 3.3618698 40 0.42 3.3618698 2.6651408 6 83.31 2.6504960 33 77.98 2.6500865 13 3.9645314 40 1.38 3.9645314 40 0.05 3.9645314 3.4173927 26 35.69 3.4151303 40 14.95 3.4151303 2.6479474 7 35.94 2.6443081 11 52.76 2.6318981 14 3.9277470 40 1.38 3.9277470 40 0.09 3.9277470 3.4156498 33 10.49 3.4126897 40 3.21 3.4126897 2.7136794 0 88.24 2.6916992 2 65.02 2.6881828 15 3.7609393 40 1.32 3.7609393 40 0.04 3.7609393 3.4142478 7 30.22 3.4062272 40 6.59 3.4062272 2.7185863 6 74.90 2.7143756 4 68.39 2.7088578 16 3.6615527 40 3.06 3.6615527 40 0.30 3.6615527 3.2011292 3 9.83 3.1772333 23 33.57 3.1751375 2.6716608 3 83.87 2.6620640 40 59.85 2.6620640 17 3.8950231 40 1.26 3.8950231 40 0.04 3.8950231 3.4356241 0 7.81 3.4335737 10 16.01 3.4333963 2.6908033 16 62.60 2.6852623 12 75.98 2.6803302 18 4.0027226 37 9.65 4.0026860 40 0.98 4.0026860 3.3241243 35 36.26 3.3217752 40 1.69 3.3217752 2.6586214 11 87.76 2.6386782 34 75.10 2.6369368 19 3.8903967 40 3.21 3.8903967 40 0.47 3.8903967 3.3743201 23 31.61 3.3513830 40 5.83 3.3513830 2.7352698 1 70.14 2.7275546 0 69.25 2.7188531 (b) Results for m=5%m=5\% n 5050 100100 200200 HGA RL-CMSA HGA RL-CMSA HGA RL-CMSA id mean #b time mean #b time best mean #b time mean #b time best mean #b time mean #b time best 0 2.7574461 40 2.74 2.7574461 40 0.08 2.7574461 2.3681336 4 4.39 2.3619281 10 41.93 2.3573197 2.1192907 7 35.27 2.1188193 40 63.00 2.1188193 1 2.7528314 40 1.27 2.7528314 40 0.06 2.7528314 2.3719676 25 30.78 2.3610634 40 3.80 2.3610634 2.1137251 0 84.29 2.1071810 2 69.32 2.1043948 2 2.7920320 11 9.57 2.7920166 40 1.47 2.7920166 2.2629216 32 29.18 2.2614223 40 18.58 2.2614223 2.0871657 0 15.55 2.0868983 40 22.29 2.0868983 3 2.7855829 36 1.32 2.7855642 40 0.05 2.7855642 2.3370123 25 5.59 2.3368099 40 1.32 2.3368099 2.1275814 0 13.44 2.1275340 27 47.95 2.1275207 4 2.7617259 14 1.31 2.7617003 40 0.13 2.7617003 2.2571316 23 19.84 2.2534861 40 7.58 2.2534861 2.1262232 0 37.55 2.1261649 3 29.11 2.1259449 5 2.8081556 40 5.59 2.8081556 40 1.60 2.8081556 2.3713419 37 2.02 2.3713327 40 0.35 2.3713327 2.1347042 1 58.68 2.1265479 37 53.94 2.1265465 6 2.8639990 40 1.56 2.8639990 40 0.12 2.8639990 2.3439967 19 7.14 2.3439926 40 0.41 2.3439926 2.1172305 0 25.60 2.1147659 16 93.64 2.1145286 7 2.7566503 40 1.58 2.7566503 40 0.04 2.7566503 2.2685452 37 2.63 2.2685095 40 1.88 2.2685095 2.1450988 28 69.60 2.1449060 40 16.39 2.1449060 8 2.8675943 40 4.47 2.8675943 40 1.91 2.8675943 2.3285961 40 1.65 2.3285961 40 0.17 2.3285961 2.1187162 12 93.62 2.1184234 40 12.74 2.1184234 9 2.7539342 18 1.33 2.7537033 40 0.08 2.7537033 2.3058106 23 10.12 2.3057027 40 0.42 2.3057027 2.1412236 9 34.17 2.1377367 33 80.09 2.1374771 10 2.8136595 40 3.65 2.8136595 40 0.13 2.8136595 2.4036452 0 3.28 2.4014057 37 35.47 2.4012250 2.0939011 20 105.47 2.0957310 11 53.81 2.0929610 11 2.6562718 40 1.27 2.6562718 40 0.05 2.6562718 2.3893410 2 21.20 2.3833549 40 24.86 2.3833549 2.1071735 31 4.27 2.1071187 40 0.82 2.1071187 12 2.6590834 40 1.28 2.6590834 40 0.03 2.6590834 2.3986828 1 25.91 2.3966068 1 4.75 2.3960052 2.1218171 0 7.71 2.1217093 1 35.29 2.1193930 13 2.8613073 40 1.26 2.8613073 40 0.06 2.8613073 2.3808739 40 11.98 2.3808739 40 0.78 2.3808739 2.1209439 1 10.01 2.1159893 39 65.51 2.1159444 14 2.7572644 40 2.70 2.7572644 40 0.36 2.7572644 2.3103459 40 4.65 2.3103459 40 0.52 2.3103459 2.1378664 4 70.51 2.1296244 10 104.18 2.1283515 15 2.6964404 40 1.30 2.6964404 40 0.06 2.6964404 2.3726073 26 27.18 2.3635699 40 5.59 2.3635699 2.1358190 1 94.95 2.1358372 4 62.67 2.1347028 16 2.5821538 40 1.26 2.5821538 40 0.03 2.5821538 2.3111260 0 49.98 2.2949602 15 44.89 2.2922352 2.1528709 0 10.61 2.1431735 5 84.94 2.1383626 17 2.8437884 40 1.26 2.8437884 40 0.04 2.8437884 2.3509711 39 32.85 2.3509627 40 2.71 2.3509627 2.1257072 0 3.71 2.1256453 40 20.03 2.1256453 18 2.8429501 40 1.29 2.8429501 40 0.04 2.8429501 2.3394594 40 3.77 2.3394594 40 0.92 2.3394594 2.0974674 14 5.64 2.0974484 40 1.08 2.0974484 19 2.7372673 40 1.60 2.7372673 40 0.27 2.7372673 2.3725333 24 22.75 2.3720750 23 26.53 2.3700339 2.1369142 3 100.11 2.1340539 0 43.74 2.1311628 (c) Results for m=10%m=10\% n 5050 100100 200200 HGA RL-CMSA HGA RL-CMSA HGA RL-CMSA id mean #b time mean #b time best mean #b time mean #b time best mean #b time mean #b time best 0 2.3504231 36 13.86 2.3495407 40 8.73 2.3495407 2.1095184 38 30.04 2.1094164 40 1.90 2.1094164 2.0121224 0 62.14 2.0107240 40 20.02 2.0107240 1 2.2185136 40 1.25 2.2185136 40 0.03 2.2185136 2.0555863 36 1.33 2.0555316 40 0.09 2.0555316 1.9933915 24 64.64 1.9920623 40 7.56 1.9920623 2 2.2581272 40 2.52 2.2581272 40 0.44 2.2581272 2.1022590 0 21.39 2.1023582 8 26.24 2.1018293 2.0053289 17 60.28 2.0047136 38 50.69 2.0046551 3 2.3395868 39 1.25 2.3395761 40 0.03 2.3395761 2.0922831 40 1.57 2.0922831 40 0.10 2.0922831 2.0069311 1 44.77 2.0057571 40 81.44 2.0057571 4 2.2494590 40 1.55 2.2494590 40 0.07 2.2494590 2.0693047 5 7.21 2.0686593 40 6.22 2.0686593 2.0156729 36 9.46 2.0156027 40 1.54 2.0156027 5 2.3763216 1 1.35 2.3762059 40 1.79 2.3762059 2.1690782 40 5.21 2.1690782 40 4.18 2.1690782 2.0074899 39 8.06 2.0074899 40 4.00 2.0074899 6 2.2833336 40 1.26 2.2833336 40 0.05 2.2833336 2.0859718 37 2.50 2.0859297 40 1.51 2.0859297 2.0001868 0 19.35 1.9998790 40 7.00 1.9998790 7 2.2077380 40 1.36 2.2077380 40 0.06 2.2077380 2.1013177 40 1.70 2.1013177 40 0.16 2.1013177 2.0120580 38 9.06 2.0120532 40 2.68 2.0120532 8 2.2511865 40 1.77 2.2511865 40 0.20 2.2511865 2.0934904 40 3.75 2.0934904 40 0.30 2.0934904 2.0170358 1 13.39 2.0165845 40 2.36 2.0165845 9 2.2994502 40 1.23 2.2994502 40 0.03 2.2994502 2.1183118 40 2.00 2.1183118 40 6.94 2.1183118 2.0178637 15 34.40 2.0173647 40 8.88 2.0173647 10 2.1968319 23 1.51 2.1966549 40 0.11 2.1966549 2.0619787 20 1.50 2.0617194 40 0.12 2.0617194 1.9925477 36 29.15 1.9925463 40 5.57 1.9925463 11 2.1931679 40 1.23 2.1931679 40 0.05 2.1931679 2.1570184 3 2.42 2.1565155 40 0.88 2.1565155 2.0012389 36 5.50 2.0012262 40 2.69 2.0012262 12 2.2802949 40 1.34 2.2802949 40 0.13 2.2802949 2.1644623 40 1.67 2.1644623 40 0.36 2.1644623 1.9984947 40 25.29 1.9984947 40 4.05 1.9984947 13 2.3567332 12 8.61 2.3566110 17 10.59 2.3563811 2.1592386 39 1.41 2.1592334 40 0.17 2.1592334 1.9979209 38 7.17 1.9979129 40 1.37 1.9979129 14 2.2545735 40 1.36 2.2545735 40 0.12 2.2545735 2.0847019 39 3.69 2.0846985 40 1.36 2.0846985 2.0063463 1 19.94 2.0058849 40 7.24 2.0058849 15 2.1879923 40 1.23 2.1879923 40 0.04 2.1879923 2.1448607 36 3.65 2.1448603 40 0.19 2.1448603 2.0091411 4 9.96 2.0087446 40 6.23 2.0087446 16 2.1730531 38 1.24 2.1730496 40 0.03 2.1730496 2.0151934 13 1.49 2.0151429 40 0.43 2.0151429 2.0005126 26 46.96 1.9992092 40 8.66 1.9992092 17 2.4438280 24 1.24 2.4437333 40 0.05 2.4437333 2.0903545 40 3.04 2.0903545 40 0.71 2.0903545 2.0113141 23 37.82 2.0112612 40 4.64 2.0112612 18 2.2578446 39 1.25 2.2578415 40 0.03 2.2578415 2.0892135 0 1.51 2.0888411 40 11.37 2.0888411 2.0017508 0 26.25 1.9971005 40 8.18 1.9971005 19 2.2395591 39 1.23 2.2395591 40 0.05 2.2395591 2.0824728 14 1.83 2.0824238 40 3.02 2.0824238 2.0260973 37 44.17 2.0260921 40 2.84 2.0260921 (d) Results for m=15%m=15\% Several consistent trends can be observed. In terms of mean solution quality, RL-CMSA generally outperforms HGA. For the smallest instances (n=50n=50), the results show that RL-CMSA and HGA tie for small values of m, with both methods producing a best-found solution in all executions. As m increases, however, RL-CMSA begins to pull ahead on some instances: while HGA no longer attains a best-found solution consistently across runs, RL-CMSA still does, yielding better average objective values. For larger instances (n=100n=100 and n=200n=200), RL-CMSA more regularly achieves better average objective values than HGA; the main exception occurs for m=1%m=1\% (see Table 2(a)), where HGA seems to outperform RL-CMSA on the largest instances (n=200n=200). Note that the number of runs producing a best-found solution (#b) is an indication of algorithm robustness. For n=50n=50 and n=100n=100, RL-CMSA reaches a best-found solution for almost all instances and in nearly all of the 4040 executions, indicating very stable performance. For n=200n=200, RL-CMSA initially struggles to match the best solution frequently (particularly for small m), but this behaviour greatly improves as m increases: the #b counts grow with m, and for m=15%m=15\% RL-CMSA again reaches the best solution in almost all runs for most instances. Finally, regarding running times, RL-CMSA is consistently faster for n=50n=50 and n=100n=100, reaching its best obtained solutions within noticeably lower CPU times than HGA. For n=200n=200, the comparison depends on m: for m=1%m=1\% HGA is generally faster, for m∈5%,10%m∈\5\%,10\%\ both methods exhibit similar running times (with instance-dependent differences), and for m=15%m=15\% RL-CMSA becomes faster in most instances. Overall, these results show that RL-CMSA dominates in average objective value and best-run frequency for almost all settings, with the main drawback appearing for the largest instances when m is small. With increasing m, RL-CMSA improves both robustness and runtime on large instances and becomes the preferred option. The weaker performance of RL-CMSA for small values of m can be explained by the intrinsic mechanics of the method. As m increases, tours become shorter, which makes the Solve step more effective: the sub-instance contains shorter route components that can be recombined in many feasible ways, increasing the number of promising route combinations and thus facilitating the construction of high-quality solutions. In other words, a given sub-instance offers greater combinatorial flexibility when routes are short. In contrast, when m is very small, routes are necessarily much longer and substantially harder to combine. Consequently, the Solve step provides less benefit. This also explains why the tuning process tends to favour larger sub-instances in this setting: retaining a bigger pool of routes increases the chance of including routes that can be combined into a competitive solution. Table 3: Statistical tests comparing RL-CMSA vs HGA, paired by instance. n 5050 100100 200200 m rbr_rb p-value rbr_rb p-value rbr_rb p-value 1%1\% 0.0000 1.000e+00 -1.0000 4.883e-04*** 0.3714 5.000e-01 5%5\% -1.0000 1.000e+00 -1.0000 4.196e-05*** -1.0000 2.289e-05*** 10%10\% -1.0000 5.000e-01 -1.0000 2.747e-04*** -0.8762 1.175e-03** 15%15\% -1.0000 3.906e-02* -0.8242 3.662e-02* -1.0000 4.196e-05*** Table 3 summarises the paired statistical comparison between RL-CMSA and HGA for each combination of m∈1%,5%,10%,15%m∈\1\%,5\%,10\%,15\%\ and problem size n∈50,100,200n∈\50,100,200\. For each instance, we compute the mean objective value over the 4040 independent runs of each algorithm and then apply a paired Wilcoxon signed-rank test across instances. The table reports the rank-biserial correlation rbr_rb as an effect-size measure and the corresponding Holm-corrected p-values. Negative values of rbr_rb indicate that RL-CMSA tends to obtain better performance than HGA, and viceversa. These statistical results confirm that RL-CMSA is statistically superior in most settings. For n=100n=100, RL-CMSA significantly outperforms HGA for all considered values of m, with very large effect sizes (rb=−1r_rb=-1) and corrected p-values below 0.050.05. For n=200n=200, the advantage is also significant for m∈5%,10%,15%m∈\5\%,10\%,15\%\, again with large negative effect sizes, whereas for m=1%m=1\% the difference is not significant and the effect size favours HGA. For n=50n=50, a significant difference is only observed for m=15%m=15\%, whereas for m∈1%,5%,10%m∈\1\%,5\%,10\%\ the comparison is not significant after correction. This indicates that, on the smallest instances and for smaller values of m, HGA and RL-CMSA behave similarly. To better understand why RL-CMSA tends to produce more consistent results than HGA, we analyze a Search Trajectory Network (STN) [9] built from all executions of both algorithms on instance id=17 with n=200n=200 and m=10%m=10\% (a large instance with a medium-high number of vehicles). Figure 2 depicts the trajectories followed by the two methods during the search. Each node corresponds to one ore more solutions visited during an execution, and each directed edge indicates a transition to better solutions. Node colours follow the same scheme as in Table 2, while grey nodes represent solutions visited by both algorithms. Yellow squares indicate initial solutions, and black triangles represent the final solutions of each run. The best solutions found are highlighted with a red circle; note that, as in the mTSP, it is very common that multiple different solutions share the same best objective value. The vertical position of a node encodes solution quality (fitness): higher nodes correspond to worse solutions, whereas lower nodes correspond to better ones. Since the STN is displayed with perspective, some black triangles may appear higher than the red-circled nodes depending on the viewpoint, although the red nodes correspond to the best solutions found. It can be observed that HGA typically starts from a narrow set of similar initial solutions and then disperses over a broader portion of the search space; several runs approach the region of high-quality solutions, but they rarely reach the best solutions. In contrast, RL-CMSA starts from more diverse initial solutions (often of better quality) and, in most runs, rapidly converges towards the same region where the best-found solutions are located. This behaviour suggests that RL-CMSA is more effective at guiding the search towards promising search space areas, which in turn explains its higher robustness across runs. Figure 2: STN graphic regarding instance 17 with n=200n=200 and m=10%m=10\%. Figure 3: Structural distances between the 40 best-found solutions per run (and per algorithm) for the 20 problem instances with n=200n=200 and m=10%m=10\%. Figure 3 shows the distribution of the pairwise structural distances between the 40 solutions obtained by each algorithm on each of the 20 problem instances (with n=200n=200 and m=10%m=10\%) using violinplots. Again, HGA is colored red, while RL-CMSA is colored blue. Wider regions of a violin indicate that many distances fall in that range, while the overlaid box/whiskers summarize the central tendency and spread (median and interquartile range), helping compare how dispersed the obtained solutions are for each method on each instance. Overall, a clear pattern emerges: HGA tends to produce solutions that are more different to each other (the red violins are usually shifted upward and often wider), which indicates higher diversity / more scattered search trajectories. In contrast, RL-CMSA typically produces solutions more similar among each other with tighter distributions (blue violins are generally lower and narrower). This is consistent with what was observed in the context of the STN graphic of Figure 2. Table 4: Summary of the obtained results for the TSPLIB instances. eil51 berlin52 eil76 rat99 HGA RL-CMSA HGA RL-CMSA HGA RL-CMSA HGA RL-CMSA m mean #b mean #b best mean #b mean #b best mean #b mean #b best mean #b mean #b best 1%1\% 222.75794 37 222.73337 40 222.73337 4110.21310 40 4110.21310 40 4110.21310 281.22379 25 280.85394 40 280.85394 665.99090 40 665.99090 40 665.99090 5%5\% 159.57151 40 159.57151 40 159.57151 3069.58569 40 3069.58569 40 3069.58569 159.50091 40 159.50091 40 159.50091 450.33361 0 450.29462 24 450.27258 10%10\% 118.13375 40 118.13375 40 118.13375 2440.92196 40 2440.92196 40 2440.92196 127.56176 39 127.56175 40 127.56175 436.44014 40 436.44014 40 436.44014 15%15\% 112.07141 40 112.07141 40 112.07141 2440.92196 40 2440.92196 40 2440.92196 127.56175 40 127.56175 40 127.56175 436.44014 40 436.44014 40 436.44014 Finally, Table 4 reports results on the TSPLIB instances using the same summary format as before. Here, the four horizontal blocks correspond to the tested instances (ordered by increasing size), and rows to the different m values. Overall, RL-CMSA matches HGA’s mean objective in most settings and improves it in five of them. It achieves the best-known solution in all executions except for one case (rat99 with m=5%m=5\%), where it still reaches the best in more than half of the runs. The table omits the time to reach the best-found solutions due to space limitations. Nonetheless, RL-CMSA is generally faster than HGA. The few exceptions coincide with settings where RL-CMSA is also stronger in solution quality, suggesting that additional search time can help it escape local optima and converge to better solutions. 5 Conclusions and Future Work In this paper, we introduced RL-CMSA, a hybrid Construct–Merge–Solve–Adapt framework with reinforcement-guided clustering for the min–max mTSP. The method generates diverse candidate solutions, maintains a compact pool of high-quality routes, and repeatedly solves a restricted set-covering MILP to recombine them, while updating pairwise q-values to bias future constructions. On randomly generated instances, RL-CMSA is robust and generally improves both the mean objective value and the frequency of best runs compared to the state-of-the-art HGA. These gains are statistically significant in most settings, and become more pronounced as the number of cities and vehicles increases. The main exception occurs on the largest instances when the number of routes is very small. Moreover, on the considered TSPLIB instances, RL-CMSA outperforms HGA in five settings. In the remaining cases, the two methods achieve comparable results, although RL-CMSA is generally faster. An analysis of the search dynamics further indicates that RL-CMSA tends to drive runs toward a single high-quality region, yielding more consistent outcomes, whereas HGA explores more broadly and exhibits greater run-to-run variability. As future work, we will strengthen RL-CMSA by enriching the route pool, e.g., by integrating additional large-scale neighborhoods, and by extending the reinforcement scheme to learn higher-order route features beyond pairwise co-occurrences. We also plan to evaluate the approach on broader and larger benchmark families and to extend it to more general routing settings with additional constraints. Acknowledgements This work was supported in part by the Department of Research and Universities of the Government of Catalonia by means of an European Social Fund (ESF)-Founded Pre-Doctoral Grant of the Catalan Agency for Management of University and Research Grants (AGAUR) under Grant 2022 FI_B 00903, in part by the Agencia Estatal de Investigación (AEI) under grants PID-2020-112581GB-C21 (MOTION) and PID2022-136787NB-I00 (ACISUD), and in part by the European Commission–NextGenerationEU, through Momentum CSIC Programme: Develop Your Digital Talent, under Project MMT24-IIIA-02. References [1] P. He and J. Hao (2022-06) Hybrid search with neighborhood reduction for the multiple traveling salesman problem. Computers & Operations Research 142, p. 105726. External Links: ISSN 0305-0548, Link, Document Cited by: §2. [2] P. He and J. Hao (2023-06) Memetic search for the minmax multiple traveling salesman problem with single and multiple depots. European Journal of Operational Research 307 (3), p. 1055–1070. External Links: ISSN 0377-2217, Link, Document Cited by: §2. [3] M. Kim, J. Park, and J. Park (2022) Neuro cross exchange: learning to cross exchange to solve realistic vehicle routing problems. arXiv. External Links: Document, Link Cited by: §2. [4] J. Li, Q. Sun, M. Zhou, and X. Dai (2013-10) A new multiple traveling salesman problem and its genetic algorithm-based solution. In 2013 IEEE International Conference on Systems, Man, and Cybernetics, p. 627–632. External Links: Link, Document Cited by: §2. [5] S. Mahmoudinazlou and C. Kwon (2024-02) A hybrid genetic algorithm for the min–max multiple traveling salesman problem. Computers & Operations Research 162, p. 106455. External Links: ISSN 0305-0548, Link, Document Cited by: §2, §2, §4.2, §4. [6] J. Park, S. Bakhtiyar, and J. Park (2021) ScheduleNet: learn to solve multi-agent scheduling problems with reinforcement learning. arXiv. External Links: Document, Link Cited by: §2. [7] Y. Park (2001-09) A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines. International Journal of Production Economics 73 (2), p. 175–188. External Links: ISSN 0925-5273, Link, Document Cited by: §1. [8] J. Reixach and C. Blum (2024-09) How to improve “construct, merge, solve and adapt"? use reinforcement learning!. Annals of Operations Research. External Links: ISSN 1572-9338, Link, Document Cited by: §1. [9] C. C. Sartori, C. Blum, and G. Ochoa (2023) STNWeb: A new visualization tool for analyzing optimization algorithms. Software Impacts 17, p. 100558. Cited by: §4.3. [10] B. Soylu (2015-12) A general variable neighborhood search heuristic for multiple traveling salesmen problem. Computers & Industrial Engineering 90, p. 390–401. External Links: ISSN 0360-8352, Link, Document Cited by: §2, §2. [11] L. Tang, J. Liu, A. Rong, and Z. Yang (2000-07) A multiple traveling salesman problem model for hot rolling scheduling in shanghai baoshan iron & steel complex. European Journal of Operational Research 124 (2), p. 267–282. External Links: ISSN 0377-2217, Link, Document Cited by: §1. [12] M. Tong, Z. Peng, and Q. Wang (2025-01) A hybrid artificial bee colony algorithm with high robustness for the multiple traveling salesman problem with multiple depots. Expert Systems with Applications 260, p. 125446. External Links: ISSN 0957-4174, Link, Document Cited by: §2. [13] P. Venkatesh and A. Singh (2015-01) Two metaheuristic approaches for the multiple traveling salesperson problem. Applied Soft Computing 26, p. 74–89. External Links: ISSN 1568-4946, Link, Document Cited by: §2, §2. [14] Y. Wang, Y. Chen, and Y. Lin (2017-04) Memetic algorithm based on sequential variable neighborhood descent for the minmax multiple traveling salesman problem. Computers & Industrial Engineering 106, p. 105–122. External Links: ISSN 0360-8352, Link, Document Cited by: §1, §2. [15] M. Yousefikhoshbakh and M. Sedighpour (2012) A combination of sweep algorithm and elite ant colony optimization for solving the multiple traveling salesman problem. Proceedings of the Romanian Academy, Series A 13 (4), p. 295–301. Cited by: §2. [16] J. Zheng, Y. Hong, W. Xu, W. Li, and Y. Chen (2022-07) An effective iterated two-stage heuristic algorithm for the multiple traveling salesmen problem. Computers & Operations Research 143, p. 105772. External Links: ISSN 0305-0548, Link, Document Cited by: §2.

Instant research discovery