A Discrete Swarm Optimization Modification for the Multi-Agent Traveling Salesman Problem
А. А. Akimov, Kristina A. Sapozhnikova, Yuliya A. Gnatenko · 2025
The paper presents a discrete modification of the Particle Swarm Optimization (PSO) algorithm aimed at solving the multi-agent Traveling Salesman Problem (mTSP) under a minimax objective. By representing city permutations as “positions” and exchange sequences as “velocities,” the standard PSO framework is adapted to effectively handle discrete routing tasks. Experimental results show that the proposed approach substantially reduces the longest individual route across various numbers of agents$(m)$and particle counts$(N)$, with larger swarms achieving greater improvements. The method proves both flexible and robust, capable of distributing travel loads among multiple salesmen while maintaining competitive solution quality. Future extensions may incorporate additional constraints or multi-objective formulations, further enhancing its applicability to complex logistics and scheduling problems.