Particle swarm optimization methods and local heuristics for solving the multiple traveling salesman problem

This paper presents the development and evaluation of a method for solving the Multiple Traveling Salesman Problem (mTSP), with the objective of minimizing the maximum route length (“minimax” optimization). The study addresses the combinatorial route-space arising from distributing cities among multiple agents, requiring balanced workload distribution to avoid overloading individual routes. The novelty of the proposed approach lies in creating a discrete analogue of the classical Particle Swarm Optimization (PSO) algorithm adapted specifically for permutation-based route representations, and integrating it with local heuristic procedures and the Ant Colony Optimization (ACO) algorithm. The proposed method transforms the original mTSP into a classical single-agent Traveling Salesman Problem (TSP) by introducing artificial (dummy) depots, thus allowing an unambiguous separation of the overall route into individual segments for each agent. A key element of the solution involves adapting the PSO algorithm through novel discrete operations, such as computing the minimal sequence of exchanges (transpositions) between permutations, scaling velocity, and applying this velocity to routes. This approach ensures efficient exploration of the combinatorial solution space and prevents premature convergence of the algorithm. The experimental study was conducted on benchmark instances from the TSPLIB library (eil51.tsp, berlin52.tsp, eil76.tsp, rat99.tsp) for the TSP, comparing two scenarios: a classical PSO with random initialization and a hybrid PSO_ACO method where the ACO algorithm is used to generate the initial population. The results demonstrate a significant improvement in the minimax criterion compared to CPLEX, LKH3, OR-Tools as well as state-of-the-art approaches DAN, NCE, and EA, confirming the effectiveness of the proposed solution. The practical importance of this research lies in potential applications of the developed algorithm in logistics, transport planning, network traffic management, and other domains where optimal resource allocation is crucial. The proposed method is valuable for specialists in optimization, algorithmic modeling, and practitioners developing planning and management systems.

1. Carter A.E., Ragsdale C.T. A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European Journal of Operational Research, 2006, vol. 175, no. 1, pp. 246–257. https://doi.org/10.1016/j.ejor.2005.04.027

2. Smirnov A.V. Investigation of influence of objective function valley ratio on the determination error of its minimum coordinates. Russian Technological Journal, vol. 11, no. 6, pp. 57–67. (in Russian). https://doi.org/10.32362/2500-316X-2023-11-6-57-67

3. Boudjelaba K., Ros F., Chikouche D. Potential of particle swarm optimization and genetic algorithms for FIR filter design. Circuits, Systems, and Signal Processing, 2014, vol. 33, no. 10, pp. 3195–3222. https://doi.org/10.1007/s00034-014-9800-y

4. Soylu B. A general variable neighborhood search heuristic for multiple traveling salesmen problem. Computers & Industrial Engineering, 2015, vol. 90, pp. 390–401. https://doi.org/10.1016/j.cie.2015.10.010

5. Elloumi W., Abeda H.E., Abraham A., Alimi A.M. A comparative study of the improvement of performance using a PSO modified by ACO applied to TSP. Applied Soft Computing, 2014, vol. 25, pp. 234–241. https://doi.org/10.1016/j.asoc.2014.09.031

6. Tang L., Liu J., Rong A., Yang Z. A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex. European Journal of Operational Research, 2000, vol. 124, no. 2, pp. 267–282. https://doi.org/10.1016/S0377-2217(99)00380-X

7. Lu L.C., Yue T.W. Mission-oriented ant-team ACO for min–max MTSP. Applied Soft Computing, 2019, vol. 76, pp. 436–444. https://doi.org/10.1016/j.asoc.2018.11.048

8. Eberhart R.C., Shi Y. Comparison between genetic algorithms and particle swarm optimization. Lecture Notes in Computer Science, 1998, vol. 1447, pp. 611–616. https://doi.org/10.1007/BFb0040812

9. Lupoaie V.-I., Chili I.-A., Breaban M.E., Raschip M. SOM-guided evolutionary search for solving MinMax Multiple-TSP. Proc. of the IEEE Congress on Evolutionary Computation (CEC), 2019, pp. 73–80. https://doi.org/10.1109/cec.2019.8790276

10. Kim M., Park J., Park J. Learning to CROSS exchange to solve min-max vehicle routing problems. Proc. of the 11^th International Conference on Learning Representations (ICLR), 2023, pp. 1–12.

11. Tasgetiren M.F., Sevkli M., Liang Y.C., Gencyilmaz G. Particle swarm optimization algorithm for permutation flowshop sequencing problem. Lecture Notes in Computer Science, 2004, vol. 3172, pp. 382–389. https://doi.org/10.1007/978-3-540-28646-2_38

12. Liao C.J., Tseng C.T., Luarn P. A discrete version of particle swarm optimization for flowshop scheduling problems. Computers and Operations Research, 2007, vol. 34, no. 10, pp. 3099–3111. https://doi.org/10.1016/j.cor.2005.11.017

13. Junjie P., Dingwei W. An ant colony optimization algorithm for Multiple Travelling Salesman Problem. Proc. of the First International Conference on Innovative Computing, Information and Control (ICICIC'06), 2006, vol. 1, pp. 210–213. https://doi.org/10.1109/icicic.2006.40

14. Necula R., Breaban M., Raschip M. Tackling the Bi-criteria facet of Multiple Traveling Salesman Problem with Ant Colony Systems. Proc. of the IEEE 27^th International Conference on Tools with Artificial Intelligence (ICTAI), 2015, pp. 873–880. https://doi.org/10.1109/ICTAI.2015.127

15. Helsgaun K. An Extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems. Occasional Paper of the Roskilde University, International Development Studies, 2017, vol. 12, pp. 966–980.

16. Perron L., Furnon V. OR-Tools v9.6б2019. Available at : https://developers.google.com/optimization/

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License