{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T13:15:56Z","timestamp":1778159756714,"version":"3.51.4"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2021,3,29]],"date-time":"2021-03-29T00:00:00Z","timestamp":1616976000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,29]],"date-time":"2021-03-29T00:00:00Z","timestamp":1616976000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["21606159"],"award-info":[{"award-number":["21606159"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013317","name":"Key Research and Development Program of Shanxi Province","doi-asserted-by":"crossref","award":["201803D121039"],"award-info":[{"award-number":["201803D121039"]}],"id":[{"id":"10.13039\/501100013317","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2021,10]]},"DOI":"10.1007\/s11227-021-03744-1","type":"journal-article","created":{"date-parts":[[2021,3,29]],"date-time":"2021-03-29T09:02:48Z","timestamp":1617008568000},"page":"11827-11852","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["A novel state transition simulated annealing algorithm for the multiple traveling salesmen problem"],"prefix":"10.1007","volume":"77","author":[{"given":"Yan","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8046-8804","authenticated-orcid":false,"given":"Xiaoxia","family":"Han","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yingchao","family":"Dong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Xie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gang","family":"Xie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xinying","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,29]]},"reference":[{"issue":"4","key":"3744_CR1","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1147\/rd.284.0476","volume":"28","author":"M Held","year":"2010","unstructured":"Held M, Hoffman AJ, Johnson EL, Wolfe P (2010) Aspects of the traveling salesman problem. IBM J Res Dev 28(4):476\u2013486","journal-title":"IBM J Res Dev"},{"issue":"3","key":"3744_CR2","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"CH Papadimitriou","year":"1977","unstructured":"Papadimitriou CH (1977) The Euclidean travelling salesman problem is NP-complete. Theor Comput Sci 4(3):237\u2013244","journal-title":"Theor Comput Sci"},{"key":"3744_CR3","first-page":"243","volume":"3","author":"U Klansek","year":"2011","unstructured":"Klansek U (2011) Using the TSP solution for optimal route scheduling in construction management. Organ Technol Manag Constr Int J 3:243\u2013249","journal-title":"Organ Technol Manag Constr Int J"},{"issue":"3","key":"3744_CR4","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1109\/TCOM.1983.1095818","volume":"31","author":"K Bharath-Kumar","year":"1983","unstructured":"Bharath-Kumar K, Jaffe J (1983) Routing to multiple destinations in computer networks. IEEE Trans Commun 31(3):351","journal-title":"IEEE Trans Commun"},{"issue":"11\u201312","key":"3744_CR5","first-page":"909","volume":"23","author":"SG Ponnambalam","year":"2004","unstructured":"Ponnambalam SG, Jagannathan H, Kataria M, Gadicherla A (2004) A TSP-GA multi-objective algorithm for flow-shop scheduling. Int J Adv Manuf Technol 23(11\u201312):909\u2013915","journal-title":"Int J Adv Manuf Technol"},{"key":"3744_CR6","doi-asserted-by":"crossref","unstructured":"Fischetti M, Salazar-Gonzalez J-J, Toth P (2007) The traveling salesman problem and its variations, vol 12, No. 13, pp 609\u2013662. Kluwer Academic Publishers, Dordrecht","DOI":"10.1007\/0-306-48213-4_13"},{"key":"3744_CR7","volume-title":"In pursuit of the traveling salesman","author":"WJ Cook","year":"2012","unstructured":"Cook WJ (2012) In pursuit of the traveling salesman. Princeton University Press, Princeton"},{"issue":"3","key":"3744_CR8","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","volume":"34","author":"T Bektas","year":"2006","unstructured":"Bektas T (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3):209\u2013219","journal-title":"Omega"},{"issue":"5","key":"3744_CR9","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1287\/opre.34.5.698","volume":"34","author":"B Gavish","year":"1986","unstructured":"Gavish B, Srikanth K (1986) An optimal solution method for large-scale multiple traveling salesmen problems. Oper Res 34(5):698\u2013717","journal-title":"Oper Res"},{"key":"3744_CR10","doi-asserted-by":"crossref","unstructured":"Saad S, Jaafar WNW, Jamil SJ (2013) Solving standard traveling salesman problem and multiple traveling salesman problem by using branch-and-bound. In: AIP Conference Proceedings, vol 1522, pp 1406\u20131411","DOI":"10.1063\/1.4801294"},{"issue":"2","key":"3744_CR11","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/j.ejor.2012.12.023","volume":"227","author":"L Xu","year":"2013","unstructured":"Xu L, Xu Z, Xu D (2013) Exact and approximation algorithms for the min-max k-traveling salesmen problem on a tree. Eur J Oper Res 227(2):284\u2013292","journal-title":"Eur J Oper Res"},{"key":"3744_CR12","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.cor.2015.12.014","volume":"70","author":"K Sundar","year":"2016","unstructured":"Sundar K, Rathinam S (2016) Generalized multiple depot traveling salesmen problem\u2014polyhedral study and exact algorithm. Comput Oper Res 70:39\u201355","journal-title":"Comput Oper Res"},{"issue":"1","key":"3744_CR13","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/j.amc.2005.09.043","volume":"176","author":"MD Toksari","year":"2006","unstructured":"Toksari MD (2006) Ant colony optimization for finding the global minimum. Appl Math Comput 176(1):308\u2013316","journal-title":"Appl Math Comput"},{"issue":"1","key":"3744_CR14","doi-asserted-by":"publisher","first-page":"1256","DOI":"10.1016\/j.asoc.2010.03.002","volume":"11","author":"S Ghafurian","year":"2011","unstructured":"Ghafurian S, Javadian N (2011) An ant colony algorithm for solving fixed destination multi-depot multiple traveling salesmen problems. Appl Soft Comput 11(1):1256\u20131262","journal-title":"Appl Soft Comput"},{"issue":"1","key":"3744_CR15","first-page":"65","volume":"16","author":"M Yousefikhoshbakht","year":"2013","unstructured":"Yousefikhoshbakht M, Didehvar F, Rahmati F (2013) Modification of the ant colony optimization for solving the multiple traveling salesman problem. Rom J Inf Sci Technol 16(1):65\u201380","journal-title":"Rom J Inf Sci Technol"},{"key":"3744_CR16","doi-asserted-by":"crossref","unstructured":"Necula R, Breaban M, Raschip M (2016) Tackling the bi-criteria facet of multiple traveling salesman problem with ant colony systems. In: 27th International Conference on Tools with Artificial Intelligence (ICTAI 2015)","DOI":"10.1109\/ICTAI.2015.127"},{"issue":"16","key":"3744_CR17","doi-asserted-by":"publisher","first-page":"4661","DOI":"10.1007\/s00500-016-2075-4","volume":"21","author":"C Changdar","year":"2017","unstructured":"Changdar C, Pal RK, Mahapatra GS (2017) A genetic ant colony optimization based algorithm for solid multiple travelling salesmen problem in fuzzy rough environment. Soft Comput 21(16):4661\u20134675","journal-title":"Soft Comput"},{"issue":"1","key":"3744_CR18","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0377-2217(95)00185-9","volume":"93","author":"CJ Malmborg","year":"1996","unstructured":"Malmborg CJ (1996) A genetic algorithm for service level based vehicle scheduling. Eur J Oper Res 93(1):121\u2013134","journal-title":"Eur J Oper Res"},{"key":"3744_CR19","first-page":"315","volume":"366","author":"A Kiraly","year":"2011","unstructured":"Kiraly A, Abonyi J (2011) Optimization of multiple traveling salesmen problem by a novel representation based genetic algorithm. Intell Comput Optim Eng 366:315\u2013326","journal-title":"Intell Comput Optim Eng"},{"issue":"1","key":"3744_CR20","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1016\/j.ejor.2005.04.027","volume":"175","author":"AE Carter","year":"2006","unstructured":"Carter AE, Ragsdale CT (2006) A new approach to solving the multiple traveling salesperson problem using genetic algorithms. Eur J Oper Res 175(1):246\u2013257","journal-title":"Eur J Oper Res"},{"key":"3744_CR21","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.asoc.2014.09.029","volume":"26","author":"P Venkatesh","year":"2015","unstructured":"Venkatesh P, Singh A (2015) Two metaheuristic approaches for the multiple traveling salesperson problem. Appl Soft Comput 26:74\u201389","journal-title":"Appl Soft Comput"},{"key":"3744_CR22","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1016\/j.asoc.2017.08.041","volume":"61","author":"Y Chen","year":"2017","unstructured":"Chen Y, Jia Z, Ai X, Yang D, Yu J (2017) A modified two-part wolf pack search algorithm for the multiple traveling salesmen problem. Appl Soft Comput 61:714\u2013725","journal-title":"Appl Soft Comput"},{"issue":"5","key":"3744_CR23","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.ipl.2007.03.010","volume":"103","author":"XH Shi","year":"2007","unstructured":"Shi XH, Liang YC, Lee HP, Lu C, Wang QX (2007) Particle swarm optimization-based algorithms for TSP and generalized TSP. Inf Process Lett 103(5):169\u2013176","journal-title":"Inf Process Lett"},{"key":"3744_CR24","first-page":"85","volume-title":"Particle swarm optimization algorithm for the traveling salesman problem","author":"EFG Goldbarg","year":"2008","unstructured":"Goldbarg EFG, Goldbarg MC, Souza GRD (2008) Particle swarm optimization algorithm for the traveling salesman problem, vol 4. InTech, London, pp 85\u201396"},{"key":"3744_CR25","doi-asserted-by":"crossref","unstructured":"Souza G, Goldbarg E, Goldbarg M, Canuto A (2012) A multiagent approach for metaheuristics hybridization applied to the traveling salesman problem. In: Proceedings-Brazilian Symposium on Neural Networks, SBRN, vol 10, pp 208\u2013213","DOI":"10.1109\/SBRN.2012.39"},{"key":"3744_CR26","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1016\/j.asoc.2017.12.031","volume":"64","author":"H Zhou","year":"2018","unstructured":"Zhou H, Song M, Pedrycz W (2018) A comparative study of improved GA and PSO in solving multiple traveling salesmen problem. Appl Soft Comput 64:564\u2013580","journal-title":"Appl Soft Comput"},{"key":"3744_CR27","doi-asserted-by":"crossref","unstructured":"Zhou X, Yang C, Gui W (2011) Initial version of state transition algorithm. In: Second International Conference on Digital Manufacturing and Automation 2011, pp 644\u2013647","DOI":"10.1109\/ICDMA.2011.160"},{"key":"3744_CR28","first-page":"1040","volume":"30","author":"C Yang","year":"2013","unstructured":"Yang C, Tang X, Zhou X, Gui W (2013) A discrete state transition algorithm for traveling salesman problem. Control Theory Appl 30:1040\u20131046","journal-title":"Control Theory Appl"},{"issue":"4598","key":"3744_CR29","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671\u2013680","journal-title":"Science"},{"issue":"4","key":"3744_CR30","doi-asserted-by":"publisher","first-page":"3680","DOI":"10.1016\/j.asoc.2011.01.039","volume":"11","author":"X Geng","year":"2011","unstructured":"Geng X, Chen Z, Yang W, Shi D, Zhao K (2011) Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Appl Soft Comput 11(4):3680\u20133689","journal-title":"Appl Soft Comput"},{"key":"3744_CR31","doi-asserted-by":"publisher","first-page":"44391","DOI":"10.1109\/ACCESS.2019.2908961","volume":"7","author":"X Han","year":"2019","unstructured":"Han X, Dong Y, Yue L, Xu Q (2019) State transition simulated annealing algorithm for discrete-continuous optimization problems. IEEE Access 7:44391\u201344403","journal-title":"IEEE Access"},{"key":"3744_CR32","first-page":"775","volume":"10","author":"X Han","year":"2020","unstructured":"Han X, Dong Y, Yue L, Xu Q, Xie G, Xu X (2020) State-transition simulated annealing algorithm for constrained and unconstrained multi-objective optimization problems. Appl Intell 10:775\u2013787","journal-title":"Appl Intell"},{"issue":"6","key":"3744_CR33","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1287\/opre.6.6.791","volume":"6","author":"GA Croes","year":"1958","unstructured":"Croes GA (1958) A method for solving traveling-salesman problems. Oper Res 6(6):791\u2013812","journal-title":"Oper Res"},{"issue":"2","key":"3744_CR34","first-page":"1","volume":"14","author":"G Peng","year":"2008","unstructured":"Peng G, Iimura I, Nakayama S (2008) An evolutionary multiple heuristic with genetic local search for solving TSP. Int J Inf Technol 14(2):1\u201311","journal-title":"Int J Inf Technol"},{"issue":"1","key":"3744_CR35","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.ejor.2003.10.016","volume":"162","author":"L Bianchi","year":"2005","unstructured":"Bianchi L, Knowles J, Bowler N (2005) Local search for the probabilistic traveling salesman problem: correction to the 2-p-opt and 1-shift algorithms. Eur J Oper Res 162(1):206\u2013219","journal-title":"Eur J Oper Res"},{"issue":"1","key":"3744_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2972953","volume":"13","author":"M Englert","year":"2016","unstructured":"Englert M, Roglin H, Vocking B (2016) Smoothed analysis of the 2-opt algorithm for the general TSP. ACM Trans Algorithms 13(1):1\u201315","journal-title":"ACM Trans Algorithms"},{"key":"3744_CR37","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.asoc.2017.04.057","volume":"58","author":"X Chen","year":"2017","unstructured":"Chen X, Zhou Y, Tang Z, Luo Q (2017) A hybrid algorithm combining glowworm swarm optimization and complete 2-opt algorithm for spherical travelling salesman problems. Appl Soft Comput 58:104\u2013114","journal-title":"Appl Soft Comput"},{"issue":"1","key":"3744_CR38","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.ejor.2005.05.027","volume":"176","author":"L Bianchi","year":"2007","unstructured":"Bianchi L, Campbell AM (2007) Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem. Eur J Oper Res 176(1):131\u2013144","journal-title":"Eur J Oper Res"},{"issue":"2","key":"3744_CR39","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1109\/TEVC.2014.2308294","volume":"19","author":"G Karafotias","year":"2015","unstructured":"Karafotias G, Hoogendoorn M, Eiben AE (2015) Parameter control in evolutionary algorithms: trends and challenges. IEEE Trans Evol Comput 19(2):167\u2013187","journal-title":"IEEE Trans Evol Comput"},{"issue":"4","key":"3744_CR40","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1080\/0305215X.2015.1025775","volume":"48","author":"X Zhou","year":"2015","unstructured":"Zhou X, Gao DY, Simpson AR (2015) Optimal design of water distribution networks by discrete state transition algorithm. Eng Optim 48(4):603\u2013628","journal-title":"Eng Optim"},{"issue":"JAN.15PT.3","key":"3744_CR41","first-page":"864","volume":"173","author":"X Zhou","year":"2015","unstructured":"Zhou X, Gao DY, Yang C, Gui W (2015) Discrete state transition algorithm for unconstrained integer optimization problems. Neurocomputing 173(JAN.15PT.3):864\u2013874","journal-title":"Neurocomputing"},{"issue":"6","key":"3744_CR42","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/s10732-008-9080-4","volume":"15","author":"S Garcia","year":"2009","unstructured":"Garcia S, Molina D, Lozano M, Herrera F (2009) A study on the use of non-parametric tests for analyzing the evolutionary algorithms behaviour: a case study on the CEC2005 special session on real parameter optimization. J Heuristics 15(6):617\u2013644","journal-title":"J Heuristics"},{"key":"3744_CR43","first-page":"92363","volume":"8","author":"X Han","year":"2020","unstructured":"Han X, Xu Q, Yue L, Dong Y, Xie G, Xu X (2020) An improved crow search algorithm based on spiral search mechanism for solving numerical and engineering optimization problems. IEEE Access 8:92363\u201392382","journal-title":"IEEE Access"},{"issue":"5","key":"3744_CR44","doi-asserted-by":"publisher","first-page":"1699","DOI":"10.1007\/s00500-017-2894-y","volume":"23","author":"S Khalilpourazari","year":"2019","unstructured":"Khalilpourazari S, Khalilpourazary S (2019) An efficient hybrid algorithm based on water cycle and Moth\u2013Flame optimization algorithms for solving numerical and constrained engineering optimization problems. Soft Comput 23(5):1699\u20131722","journal-title":"Soft Comput"},{"key":"3744_CR45","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.asoc.2019.105744","volume":"85","author":"Y Sun","year":"2019","unstructured":"Sun Y, Yang T, Liu Z (2019) A whale optimization algorithm based on quadratic interpolation for high-dimensional global optimization problems. Appl Soft Comput 85:1\u201320","journal-title":"Appl Soft Comput"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-021-03744-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-021-03744-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-021-03744-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,1]],"date-time":"2023-11-01T07:07:53Z","timestamp":1698822473000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-021-03744-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,29]]},"references-count":45,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["3744"],"URL":"https:\/\/doi.org\/10.1007\/s11227-021-03744-1","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,29]]},"assertion":[{"value":"13 March 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 March 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"Informed consent was obtained from all individual participants included in the study.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Informed consent"}}]}}