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

Robotic systems often require a team of robots to collectively visit multiple targets while optimizing competing objectives, such as total travel cost and makespan. This setting can be formulated as the Multi-Objective Multiple Traveling Salesman Problem (MOMTSP). Although learning-based methods have shown strong performance on the single-agent TSP and multi-objective TSP variants, they rarely address the combined challenges of multi-agent coordination and multi-objective trade-offs, which introduce dual sources of complexity. To bridge this gap, we propose CAMO, a conditional neural solver for MOMTSP that generalizes across varying numbers of targets, agents, and preference vectors, and yields high-quality approximations to the Pareto front (PF). Specifically, CAMO consists of a conditional encoder to fuse preferences into instance representations, enabling explicit control over multi-objective trade-offs, and a collaborative decoder that coordinates all agents by alternating agent selection and node selection to construct multi-agent tours autoregressively. To further improve generalization, we train CAMO with a REINFORCE-based objective over a mixed distribution of problem sizes. Extensive experiments show that CAMO outperforms both neural and conventional heuristics, achieving a closer approximation of PFs. In addition, ablation results validate the contributions of CAMO's key components, and real-world tests on a mobile robot platform demonstrate its practical applicability.

Evolutionary multitasking allows several related problems to be solved in a single run of an algorithm. In this paper, we investigate integrating evolutionary multitasking with Edge Assembly Crossover (MT-EAX) to solve the classical Travelling Salesperson Problem (TSP). To fairly compare MT-EAX against standard EAX under strict compute budgets, we evaluate three scaling methods: generation scaling, population scaling, and balanced scaling. Our results show that generationally scaled MT-EAX is highly effective compute-wise in the early stages of the search, saving $60\%$ to $90\%$ of compute for equal or better solution quality. We observe that instance geometry has a significant impact, with clustered, normally distributed instances securing larger improvements than uniformly distributed ones. However, when scaling by population or utilising explicit solution transfer, the results are negative due to population starvation and incompatible cross-instance parent selection. We demonstrate that the advantage of MT-EAX derives from increased diversity through parallel search in early generations, which can be successfully preserved using a decoupled configuration to often strictly outperform or match standard EAX performance at final convergence.

The Traveling Salesman Problem (TSP) is a classical NP-hard combinatorial optimization problem that aims to find the shortest Hamiltonian cycle visiting each city exactly once and returning to the starting point. This paper proposes a hybrid metaheuristic for the TSP by combining the Dragonfly Algorithm (DA), a swarm-intelligence-based global search method, with Tabu Search (TS), a memory-based local search technique. The proposed method follows a High-Level Relay Hybridization (HRH) scheme, in which DA is first used to explore the solution space and generate a promising initial tour, while TS subsequently refines this solution through neighbourhood-based improvement and tabu memory. The hybrid approach is evaluated on standard TSPLIB benchmark instances, including burma14, att48, and ch150, and compared with standalone DA, standalone TS, and several classical metaheuristics such as Genetic Algorithm, Ant Colony Optimization, Particle Swarm Optimization, and Random Search. A systematic grid-search procedure is also conducted to study the influence of the main hyperparameters on solution quality and execution time. The experimental results indicate that the proposed hybrid can improve tour quality compared with the standalone DA and TS on the tested instances, highlighting the benefit of combining global exploration with local exploitation. However, the results also suggest that performance remains sensitive to parameter settings and problem size, motivating further validation on larger benchmarks and stronger TSP-specific baselines.