{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T18:44:20Z","timestamp":1775328260020,"version":"3.50.1"},"reference-count":48,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2023,1,7]],"date-time":"2023-01-07T00:00:00Z","timestamp":1673049600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A new algorithm based on the ant colony optimization (ACO) method for the multiple traveling salesman problem (mTSP) is presented and defined as ACO-BmTSP. This paper addresses the problem of solving the mTSP while considering several salesmen and keeping both the total travel cost at the minimum and the tours balanced. Eleven different problems with several variants were analyzed to validate the method. The 20 variants considered three to twenty salesmen regarding 11 to 783 cities. The results were compared with best-known solutions (BKSs) in the literature. Computational experiments showed that a total of eight final results were better than those of the BKSs, and the others were quite promising, showing that with few adaptations, it will be possible to obtain better results than those of the BKSs. Although the ACO metaheuristic does not guarantee that the best solution will be found, it is essential in problems with non-deterministic polynomial time complexity resolution or when used as an initial bound solution in an integer programming formulation. Computational experiments on a wide range of benchmark problems within an acceptable time limit showed that compared with four existing algorithms, the proposed algorithm presented better results for several problems than the other algorithms did.<\/jats:p>","DOI":"10.3390\/a16010037","type":"journal-article","created":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T04:47:08Z","timestamp":1673239628000},"page":"37","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Ant-Balanced Multiple Traveling Salesmen: ACO-BmTSP"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5439-287X","authenticated-orcid":false,"given":"S\u00edlvia","family":"de Castro Pereira","sequence":"first","affiliation":[{"name":"Instituto Polit\u00e9cnico de Bragan\u00e7a, Campus de Santa Apol\u00f3nia, 5300\u2013253 Bragan\u00e7a, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3224-4926","authenticated-orcid":false,"given":"Eduardo J.","family":"Solteiro Pires","sequence":"additional","affiliation":[{"name":"Departamento de Engenharias, Universidade de Tr\u00e1s-os-Montes e Alto Douro, 5000\u2013811 Vila Real, Portugal"},{"name":"INESC TEC\u2014INESC Technology and Science, Rua Dr. Roberto Frias, 4200\u2013465 Porto, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4283-1243","authenticated-orcid":false,"given":"Paulo B.","family":"de Moura Oliveira","sequence":"additional","affiliation":[{"name":"Departamento de Engenharias, Universidade de Tr\u00e1s-os-Montes e Alto Douro, 5000\u2013811 Vila Real, Portugal"},{"name":"INESC TEC\u2014INESC Technology and Science, Rua Dr. Roberto Frias, 4200\u2013465 Porto, Portugal"}]}],"member":"1968","published-online":{"date-parts":[[2023,1,7]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1109\/MCI.2006.329691","article-title":"Ant colony optimization","volume":"1","author":"Dorigo","year":"2006","journal-title":"IEEE Comput. Intell. Mag."},{"key":"ref_2","first-page":"381","article-title":"The optimal selection on the parameters of the ant colony algorithm","volume":"19","author":"Zhan","year":"2003","journal-title":"Bull. Sci. Technol."},{"key":"ref_3","unstructured":"Dorigo, M. (1992). Optimization, Learning and Natural Algorithms. [Ph.D. Thesis, Politecnico di Milano]."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Gambardella, L.M., and Dorigo, M. (1995). Ant-Q: A reinforcement learning approach to the traveling salesman problem. Machine Learning Proceedings 1995, Elsevier.","DOI":"10.1016\/B978-1-55860-377-6.50039-6"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/S0303-2647(97)01708-5","article-title":"Ant colonies for the travelling salesman problem","volume":"43","author":"Dorigo","year":"1997","journal-title":"Biosystems"},{"key":"ref_6","first-page":"25","article-title":"A New Rank Based Version of the Ant System\u2014A Computational Study","volume":"7","author":"Bullnheimer","year":"1999","journal-title":"Cent. Eur. J. Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Guntsch, M., and Middendorf, M. (2002, January 3\u20134). A population based approach for ACO. Proceedings of the Workshops on Applications of Evolutionary Computation, Kinsale, Ireland.","DOI":"10.1007\/3-540-46004-7_8"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Blum, C. (2004). Theoretical and Practical Aspects of Ant Colony Optimization, IOS Press.","DOI":"10.1007\/978-3-540-28646-2_11"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1016\/j.amc.2006.09.023","article-title":"Hybrid ant colony optimization and visibility studies applied to a job-shop scheduling problem","volume":"187","author":"Heinonen","year":"2007","journal-title":"Appl. Math. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1030","DOI":"10.1016\/j.cor.2006.07.003","article-title":"Ant colony optimization combined with taboo search for the job shop scheduling problem","volume":"35","author":"Huang","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"11072","DOI":"10.1016\/j.eswa.2011.02.151","article-title":"A hybrid ant colony optimization for continuous domains","volume":"38","author":"Xiao","year":"2011","journal-title":"Expert Syst. Appl."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/j.jweia.2013.10.004","article-title":"Hybrid technique of ant colony and particle swarm optimization for short term wind energy forecasting","volume":"123","author":"Rahmani","year":"2013","journal-title":"J. Wind. Eng. Ind. Aerodyn."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.enconman.2014.12.037","article-title":"A hybrid of ant colony optimization and artificial bee colony algorithm for probabilistic optimal placement and sizing of distributed energy resources","volume":"92","author":"Kefayat","year":"2015","journal-title":"Energy Convers. Manag."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/j.ins.2017.07.002","article-title":"A hybrid genetic-ant colony optimization algorithm for the word sense disambiguation problem","volume":"417","author":"Alsaeedan","year":"2017","journal-title":"Inf. Sci."},{"key":"ref_15","first-page":"651","article-title":"Hybrid ant colony optimization for continuous domains for solving emission and economic dispatch problems","volume":"39","author":"Karakonstantis","year":"2018","journal-title":"J. Inf. Optim. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.engappai.2019.04.015","article-title":"Hybrid bidirectional ant colony optimization (hybrid BACO): An algorithm for disassembly sequence planning","volume":"83","author":"Tseng","year":"2019","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"112357","DOI":"10.1016\/j.oceaneng.2022.112357","article-title":"Optimization of maintenance scheme for offshore wind turbines considering time windows based on hybrid ant colony algorithm","volume":"263","author":"Wang","year":"2022","journal-title":"Ocean. Eng."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Castro Pereira, S.D., Solteiro Pires, E.J., and Oliveira, P.M. (2021, January 25\u201327). Genetic and Ant Colony Algorithms to Solve the Multi-TSP. Proceedings of the International Conference on Intelligent Data Engineering and Automated Learning, Manchester, UK.","DOI":"10.1007\/978-3-030-91608-4_32"},{"key":"ref_19","first-page":"103","article-title":"A novel hybrid approach for solving the multiple traveling salesmen problem","volume":"26","author":"Harrath","year":"2019","journal-title":"Arab. J. Basic Appl. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Gomes, D.E., Igl\u00e9sias, M.I.D., Proen\u00e7a, A.P., Lima, T.M., and Gaspar, P.D. (2021). Applying a Genetic Algorithm to a m-TSP: Case Study of a Decision Support System for Optimizing a Beverage Logistics Vehicles Routing Problem. Electronics, 10.","DOI":"10.3390\/electronics10182298"},{"key":"ref_21","unstructured":"Greco, S., Pavone, M.F., Talbi, E.-G., and Vigo, D. (2018, January 15). A Variable Neighborhood Search Algorithm for Cost-Balanced Travelling Salesman Problem. Proceedings of the Metaheuristics Summer School, Taormina, Italy."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Mu\u00f1oz-Herrera, S., and Suchan, K. (2022). Constrained Fitness Landscape Analysis of Capacitated Vehicle Routing Problems. Entropy, 24.","DOI":"10.3390\/e24010053"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"105509","DOI":"10.1016\/j.cor.2021.105509","article-title":"Balanced dynamic multiple travelling salesmen: Algorithms and continuous approximations","volume":"136","author":"Garn","year":"2021","journal-title":"Comput. Oper. Res."},{"key":"ref_24","unstructured":"Xu, H.-L., and Zhang, C.-M. (2009, January 27\u201328). The research about balanced route MTSP based on hybrid algorithm. Proceedings of the 2009 International Conference on Communication Software and Networks, Chengdu, China."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Khoufi, I., Laouiti, A., and Adjih, C. (2019). A Survey of Recent Extended Variants of the Traveling Salesman and Vehicle Routing Problems for Unmanned Aerial Vehicles. Drones, 3.","DOI":"10.3390\/drones3030066"},{"key":"ref_26","unstructured":"Pereira, A.I., Ko\u0161ir, A., Fernandes, F.P., Pacheco, M.F., Teixeira, J.P., and Lopes, R.P. (2022, January 24\u201325). A Hybrid Approach GABC\u2013LS to Solve mTSP. Proceedings of the Optimization, Learning Algorithms and Applications, P\u00f3voa do Varzim, Portugal."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1016\/j.ejor.2005.04.027","article-title":"A new approach to solving the multiple traveling salesperson problem using genetic algorithms","volume":"175","author":"Carter","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"105772","DOI":"10.1016\/j.cor.2022.105772","article-title":"An effective iterated two-stage heuristic algorithm for the multiple Traveling Salesmen Problem","volume":"143","author":"Zheng","year":"2022","journal-title":"Comput. Oper. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1016\/j.cie.2015.10.010","article-title":"A general variable neighborhood search heuristic for multiple traveling salesmen problem","volume":"90","author":"Soylu","year":"2015","journal-title":"Comput. Ind. Eng."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"208","DOI":"10.2478\/sbe-2019-0016","article-title":"Variants of the traveling salesman problem","volume":"14","author":"Patterson","year":"2019","journal-title":"Stud. Bus. Econ."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Matai, R., Singh, S.P., and Mittal, M.L. (2010). Traveling salesman problem: An overview of applications, formulations, and solution approaches. Traveling Salesman Problem, Theory and Applications, IntechOpen.","DOI":"10.5772\/12909"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Agra, A., Cerveira, A., and Requejo, C. (2016, January 26\u201329). Lagrangian relaxation bounds for a production-inventory-routing problem. Proceedings of the International Workshop on Machine Learning, Optimization, and Big Data, Volterra, Italy.","DOI":"10.1007\/978-3-319-51469-7_20"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/s10589-012-9487-6","article-title":"A new Branch and Bound method for a discrete truss topology design problem","volume":"54","author":"Cerveira","year":"2013","journal-title":"Comput. Optim. Appl."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Cerveira, A., Pires, E.J.S., and Baptista, J. (2021). Wind Farm Cable Connection Layout Optimization with Several Substations. Energies, 14.","DOI":"10.3390\/en14123615"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Alves, R.M., and Lopes, C.R. (2015, January 25\u201328). Using genetic algorithms to minimize the distance and balance the routes for the multiple traveling salesman problem. Proceedings of the 2015 IEEE Congress on Evolutionary Computation (CEC), Sendai, Japan.","DOI":"10.1109\/CEC.2015.7257285"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","article-title":"The multiple traveling salesman problem: An overview of formulations and solution procedures","volume":"34","author":"Bektas","year":"2006","journal-title":"Omega"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"100369","DOI":"10.1016\/j.cosrev.2021.100369","article-title":"A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy","volume":"40","author":"Cheikhrouhou","year":"2021","journal-title":"Comput. Sci. Rev."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/j.cie.2016.12.017","article-title":"Memetic algorithm based on sequential variable neighborhood descent for the minmax multiple traveling salesman problem","volume":"106","author":"Wang","year":"2017","journal-title":"Comput. Ind. Eng."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1162\/106454699568728","article-title":"Ant algorithms for discrete optimization","volume":"5","author":"Dorigo","year":"1999","journal-title":"Artif. Life"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1971","DOI":"10.32604\/iasc.2023.030100","article-title":"An Efficient Allocation for Lung Transplantation Using Ant Colony Optimization","volume":"35","year":"2023","journal-title":"Intell. Autom. Soft Comput."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"17057","DOI":"10.1007\/s00521-021-06298-8","article-title":"An improved shuffled frog-leaping algorithm for the minmax multiple traveling salesman problem","volume":"33","author":"Dong","year":"2021","journal-title":"Neural Comput. Appl."},{"key":"ref_42","unstructured":"Solteiro Pires, E., and Tenreiro Machado, J. (2000, January 16\u201319). A GA perspective of the energy requirements for manipulators maneuvering in a workspace with obstacles. Proceedings of the 2000 Congress on Evolutionary Computation, La Jolla, CA, USA."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1016\/j.asoc.2005.06.009","article-title":"Manipulator trajectory planning using a MOEA","volume":"7","author":"Pires","year":"2007","journal-title":"Appl. Soft Comput."},{"key":"ref_44","unstructured":"Burkardt, J. (2022, November 24). CITIES\u2014City Distance Datasets. Available online: https:\/\/people.sc.fsu.edu\/~jburkardt\/datasets\/cities\/cities.html."},{"key":"ref_45","unstructured":"Ruprecht-Karls (2022, November 24). TSPLIB. Available online: http:\/\/comopt.ifi.uni-heidelberg.de\/software\/TSPLIB95."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.ejor.2013.01.043","article-title":"A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms","volume":"228","author":"Yuan","year":"2013","journal-title":"Eur. J. Oper. Res."},{"key":"ref_47","unstructured":"Liu, W., Li, S., Zhao, F., and Zheng, A. (2009, January 25\u201327). An ant colony optimization algorithm for the multiple traveling salesmen problem. Proceedings of the 2009 4th IEEE Conference on Industrial Electronics and Applications, Xi\u2019an, China."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1016\/j.asoc.2018.11.048","article-title":"Mission-oriented ant-team ACO for min\u2013max MTSP","volume":"76","author":"Lu","year":"2019","journal-title":"Appl. Soft Comput."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/1\/37\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:02:45Z","timestamp":1760119365000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/1\/37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,7]]},"references-count":48,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["a16010037"],"URL":"https:\/\/doi.org\/10.3390\/a16010037","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,7]]}}}