{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T23:58:33Z","timestamp":1768348713559,"version":"3.49.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T00:00:00Z","timestamp":1652918400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T00:00:00Z","timestamp":1652918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100019290","name":"Halmstad University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100019290","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Intel Serv Robotics"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A deterministic annealing (DA) method is presented for solving the multi-robot routing problem with min\u2013max objective. This is an NP-hard problem belonging to the multi-robot task allocation set of problems where robots are assigned to a group of sequentially ordered tasks such that the cost of the slowest robot is minimized. The problem is first formulated in a matrix form where the optimal solution of the problem is the minimum-cost permutation matrix without any loops. The solution matrix is then found using the DA method is based on mean field theory applied to a Potts spin model which has been proven to yield near-optimal results for NP-hard problems. Our method is bench-marked against simulated annealing and a heuristic search method. The results show that the proposed method is promising for small-medium sized problems in terms of computation time and solution quality compared to the other two methods.<\/jats:p>","DOI":"10.1007\/s11370-022-00424-8","type":"journal-article","created":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T13:03:41Z","timestamp":1652965421000},"page":"321-334","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Deterministic annealing with Potts neurons for multi-robot routing"],"prefix":"10.1007","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5258-0105","authenticated-orcid":false,"given":"Jennifer","family":"David","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thorsteinn","family":"R\u00f6gnvaldsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bo","family":"S\u00f6derberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mattias","family":"Ohlsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,19]]},"reference":[{"issue":"1","key":"424_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2005.01.007","volume":"59","author":"EM Arkin","year":"2006","unstructured":"Arkin EM, Hassin R, Levin A (2006) Approximations for minimum and min-max vehicle routing problems. J. Algorithms 59(1):1\u201318","journal-title":"J. Algorithms"},{"key":"424_CR2","doi-asserted-by":"publisher","unstructured":"Bae J, Lee J, Chung W (2019) A heuristic for task allocation and routing of heterogeneous robots while minimizing maximum travel cost. In: 2019 international conference on robotics and automation (ICRA), pp. 4531\u20134537. https:\/\/doi.org\/10.1109\/ICRA.2019.8794257","DOI":"10.1109\/ICRA.2019.8794257"},{"issue":"2","key":"424_CR3","doi-asserted-by":"publisher","first-page":"4064","DOI":"10.1109\/LRA.2021.3067286","volume":"6","author":"J Bae","year":"2021","unstructured":"Bae J, Park M (2021) A heuristic for efficient coordination of multiple heterogeneous mobile robots considering workload balance. IEEE Robot Automat Lett 6(2):4064\u20134070","journal-title":"IEEE Robot Automat Lett"},{"key":"424_CR4","doi-asserted-by":"crossref","unstructured":"Baxter JL, Burke E, Garibaldi JM, Norman M (2007) Multi-robot search and rescue: a potential field based approach. In: Autonomous robots and agents, pp 9\u201316. Springer","DOI":"10.1007\/978-3-540-73424-6_2"},{"issue":"3","key":"424_CR5","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":"4","key":"424_CR6","doi-asserted-by":"publisher","first-page":"122","DOI":"10.3390\/robotics10040122","volume":"10","author":"J David","year":"2021","unstructured":"David J, R\u00f6gnvaldsson T (2021) Multi-robot routing problem with min-max objective. Robotics 10(4):122","journal-title":"Robotics"},{"key":"424_CR7","doi-asserted-by":"publisher","unstructured":"Ding L, Zhao D, Ma H, Wang H, Liu L (2018) Energy-efficient min\u2013max planning of heterogeneous tasks with multiple uavs. In: 2018 IEEE 24th international conference on parallel and distributed systems (ICPADS), pp 339\u2013346. https:\/\/doi.org\/10.1109\/PADSW.2018.8644625","DOI":"10.1109\/PADSW.2018.8644625"},{"issue":"4","key":"424_CR8","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/0893-6080(91)90039-8","volume":"4","author":"SP Eberhardt","year":"1991","unstructured":"Eberhardt SP, Daud T, Kerns D, Brown TX, Thakoor A (1991) Competitive neural architecture for hardware solution to the assignment problem. Neural Netw 4(4):431\u2013442","journal-title":"Neural Netw"},{"issue":"1","key":"424_CR9","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1002\/rob.21823","volume":"36","author":"J Faigl","year":"2019","unstructured":"Faigl J, V\u00e1\u0148a P, P\u011bni\u010dka R, Saska M (2019) Unsupervised learning-based flexible framework for surveillance planning with aerial vehicles. J Field Robot 36(1):270\u2013301","journal-title":"J Field Robot"},{"issue":"2","key":"424_CR10","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1002\/net.3230110205","volume":"11","author":"ML Fisher","year":"1981","unstructured":"Fisher ML, Jaikumar R (1981) A generalized assignment heuristic for vehicle routing. Networks 11(2):109\u2013124","journal-title":"Networks"},{"key":"424_CR11","doi-asserted-by":"crossref","unstructured":"Gerkey BP, Mataric MJ (2003) Multi-robot task allocation: Analyzing the complexity and optimality of key architectures. In: 2003 IEEE international conference on robotics and automation (Cat. No. 03CH37422), vol\u00a03, pp 3862\u20133868. IEEE","DOI":"10.1109\/ROBOT.2003.1242189"},{"key":"424_CR12","doi-asserted-by":"publisher","first-page":"1587","DOI":"10.1162\/089976698300017322","volume":"10","author":"J H\u00e4kkinen","year":"1998","unstructured":"H\u00e4kkinen J, Lagerholm M, Peterson C, S\u00f6derberg B (1998) A Potts neuron approach to communication routing. Neural Comput 10:1587\u20131599","journal-title":"Neural Comput"},{"issue":"4","key":"424_CR13","doi-asserted-by":"publisher","first-page":"970","DOI":"10.1109\/72.857776","volume":"11","author":"J H\u00e4kkinen","year":"2000","unstructured":"H\u00e4kkinen J, Lagerholm M, Peterson C, S\u00f6derberg B (2000) Local routing algorithms based on Potts neural networks. IEEE Trans Neural Netw 11(4):970\u2013977","journal-title":"IEEE Trans Neural Netw"},{"issue":"8","key":"424_CR14","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1073\/pnas.79.8.2554","volume":"79","author":"JJ Hopfield","year":"1982","unstructured":"Hopfield JJ (1982) Neural networks and physical systems with emergent collective computational abilities. Proc Natl Acad Sci 79(8):2554\u20132558","journal-title":"Proc Natl Acad Sci"},{"issue":"3","key":"424_CR15","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF00339943","volume":"52","author":"JJ Hopfield","year":"1985","unstructured":"Hopfield JJ, Tank DW (1985) Neural computation of decisions in optimization problems. Biol Cybern 52(3):141\u2013152","journal-title":"Biol Cybern"},{"issue":"5","key":"424_CR16","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1016\/S0893-6080(96)00106-2","volume":"10","author":"S Ishii","year":"1997","unstructured":"Ishii S, Ma Sato (1997) Chaotic Potts spin model for combinatorial optimization problems. Neural Netw 10(5):941\u2013963","journal-title":"Neural Netw"},{"key":"424_CR17","unstructured":"J\u00f6nsson H, S\u00f6derberg B (2001) Deterministic annealing and nonlinear assignment. arXiv preprint cond-mat\/0105321"},{"key":"424_CR18","doi-asserted-by":"crossref","unstructured":"Kuhn HW (1955) The hungarian method for the assignment problem. Naval Res Log Quart 2(1-2):83\u201397","DOI":"10.1002\/nav.3800020109"},{"key":"424_CR19","doi-asserted-by":"crossref","unstructured":"Lagerholm M, Peterson C, S\u00f6derberg B (1997) Airline crew scheduling with Potts neurons. Neural Comput 9(7):1589\u20131599","DOI":"10.1162\/neco.1997.9.7.1589"},{"issue":"1","key":"424_CR20","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0377-2217(98)00387-7","volume":"120","author":"M Lagerholm","year":"2000","unstructured":"Lagerholm M, Peterson C, S\u00f6derberg B (2000) Airline crew scheduling using Potts mean field techniques. Eur J Oper Res 120(1):81\u201396","journal-title":"Eur J Oper Res"},{"key":"424_CR21","doi-asserted-by":"crossref","unstructured":"Lagoudakis MG, Markakis E, Kempe D, Keskinocak P, Kleywegt AJ, Koenig S, Tovey CA, Meyerson A, Jain S (2005) Auction-based multi-robot routing In: Robotics: Science and Systems, vol. 5, pp. 343\u2013350","DOI":"10.15607\/RSS.2005.I.045"},{"key":"424_CR22","doi-asserted-by":"crossref","unstructured":"Luo L, Chakraborty N, Sycara K (2012) A distributed algorithm for constrained multi-robot task assignment for grouped tasks","DOI":"10.1109\/ICRA.2013.6630994"},{"key":"424_CR23","unstructured":"Ma H, Koenig S (2016) Optimal target assignment and path finding for teams of agents. arXiv:1612.05693"},{"key":"424_CR24","doi-asserted-by":"publisher","unstructured":"Narasimha KSV, Kivelevitch E, Kumar M (2012) Ant colony optimization technique to solve the min-max multi depot vehicle routing problem. In: 2012 American control conference (ACC), pp 3980\u20133985. https:\/\/doi.org\/10.1109\/ACC.2012.6315583","DOI":"10.1109\/ACC.2012.6315583"},{"issue":"1","key":"424_CR25","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1080\/03052150600917128","volume":"39","author":"W Ng","year":"2007","unstructured":"Ng W, Mak K, Zhang Y (2007) Scheduling trucks in container terminals using a genetic algorithm. Eng Optim 39(1):33\u201347","journal-title":"Eng Optim"},{"issue":"3","key":"424_CR26","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/S0377-2217(00)00205-8","volume":"133","author":"M Ohlsson","year":"2001","unstructured":"Ohlsson M, Peterson C, S\u00f6derberg B (2001) An efficient mean field approach to the set covering problem. Eur J Oper Res 133(3):583\u2013595","journal-title":"Eur J Oper Res"},{"key":"424_CR27","doi-asserted-by":"crossref","unstructured":"Parker LE (1995) L-alliance: a mechanism for adaptive action selection in heterogeneous multi-robot teams. Tech. rep., Oak Ridge National Lab., TN (United States)","DOI":"10.2172\/211400"},{"issue":"2","key":"424_CR28","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1109\/70.681242","volume":"14","author":"LE Parker","year":"1998","unstructured":"Parker LE (1998) Alliance: an architecture for fault tolerant multirobot cooperation. IEEE Trans Robot Automat 14(2):220\u2013240","journal-title":"IEEE Trans Robot Automat"},{"issue":"01","key":"424_CR29","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1142\/S0129065789000414","volume":"1","author":"C Peterson","year":"1989","unstructured":"Peterson C, S\u00f6derberg B (1989) A new method for mapping optimization problems onto neural networks. Int J Neural Syst 1(01):3\u201322","journal-title":"Int J Neural Syst"},{"key":"424_CR30","doi-asserted-by":"publisher","unstructured":"Scott D, Manyam SG, Casbeer DW, Kumar M (2020) Market approach to length constrained min-max multiple depot multiple traveling salesman problem. In: 2020 American Control Conference (ACC), pp 138\u2013143. https:\/\/doi.org\/10.23919\/ACC45564.2020.9147207","DOI":"10.23919\/ACC45564.2020.9147207"},{"issue":"2","key":"424_CR31","doi-asserted-by":"publisher","first-page":"343","DOI":"10.2140\/pjm.1967.21.343","volume":"21","author":"R Sinkhorn","year":"1967","unstructured":"Sinkhorn R, Knopp P (1967) Concerning nonnegative matrices and doubly stochastic matrices. Pac J Math 21(2):343\u2013348","journal-title":"Pac J Math"},{"issue":"1","key":"424_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(89)90044-8","volume":"83","author":"JS Turner","year":"1989","unstructured":"Turner JS (1989) Approximation algorithms for the shortest common superstring problem. Inf Comput 83(1):1\u201320","journal-title":"Inf Comput"},{"key":"424_CR33","doi-asserted-by":"crossref","unstructured":"Turpin M, Michael N, Kumar V (2015) An approximation algorithm for time optimal multi-robot routing. In: Algorithmic foundations of robotics XI, pp 627\u2013640. Springer","DOI":"10.1007\/978-3-319-16595-0_36"},{"key":"424_CR34","unstructured":"Young D (2020) Sinkhorn-knopp algorithm for matrix normalisation. MATLAB Central File Exchange Retrieved October 23"}],"container-title":["Intelligent Service Robotics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11370-022-00424-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11370-022-00424-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11370-022-00424-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,25]],"date-time":"2024-09-25T14:48:56Z","timestamp":1727275736000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11370-022-00424-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,19]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["424"],"URL":"https:\/\/doi.org\/10.1007\/s11370-022-00424-8","relation":{},"ISSN":["1861-2776","1861-2784"],"issn-type":[{"value":"1861-2776","type":"print"},{"value":"1861-2784","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,19]]},"assertion":[{"value":"24 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}