{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T03:06:35Z","timestamp":1768532795557,"version":"3.49.0"},"reference-count":66,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,11,9]],"date-time":"2021-11-09T00:00:00Z","timestamp":1636416000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Robotics"],"abstract":"<jats:p>In this paper, we study the \u201cMulti-Robot Routing problem\u201d with min\u2013max objective (MRR-MM) in detail. It involves the assignment of sequentially ordered tasks to robots such that the maximum cost of the slowest robot is minimized. The problem description, the different types of formulations, and the methods used across various research communities are discussed in this paper. We propose a new problem formulation by treating this problem as a permutation matrix. A comparative study is done between three methods: Stochastic simulated annealing, deterministic mean-field annealing, and a heuristic-based graph search method. Each method is investigated in detail with several data sets (simulation and real-world), and the results are analysed and compared with respect to scalability, computational complexity, optimality, and its application to real-world scenarios. The paper shows that the heuristic method produces results very quickly with good scalability. However, the solution quality is sub-optimal. On the other hand, when optimal or near-optimal results are required with considerable computational resources, the simulated annealing method proves to be more efficient. However, the results show that the optimal choice of algorithm depends on the dataset size and the available computational budget. The contribution of the paper is three-fold: We study the MRR-MM problem in detail across various research communities. This study also shows the lack of inter-research terminology that has led to different names for the same problem. Secondly, formulating the task allocation problem as a permutation matrix formulation has opened up new approaches to solve this problem. Thirdly, we applied our problem formulation to three different methods and conducted a detailed comparative study using real-world and simulation data.<\/jats:p>","DOI":"10.3390\/robotics10040122","type":"journal-article","created":{"date-parts":[[2021,11,9]],"date-time":"2021-11-09T21:39:07Z","timestamp":1636493947000},"page":"122","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Multi-Robot Routing Problem with Min\u2013Max Objective"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5258-0105","authenticated-orcid":false,"given":"Jennifer","family":"David","sequence":"first","affiliation":[{"name":"Center for Applied Intelligent Systems Research, School of ITE, Halmstad University, SE-30118 Halmstad, Sweden"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5163-2997","authenticated-orcid":false,"given":"Thorsteinn","family":"R\u00f6gnvaldsson","sequence":"additional","affiliation":[{"name":"Center for Applied Intelligent Systems Research, School of ITE, Halmstad University, SE-30118 Halmstad, Sweden"}]}],"member":"1968","published-online":{"date-parts":[[2021,11,9]]},"reference":[{"key":"ref_1","unstructured":"Claes, D., Oliehoek, F., Baier, H., and Tuyls, K. (2017, January 8\u201312). Decentralised online planning for multi-robot warehouse commissioning. Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems, S\u00e3o Paulo, Brazil."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Baxter, J.L., Burke, E., Garibaldi, J.M., and Norman, M. (2007). Multi-robot search and rescue: A potential field based approach. Autonomous Robots and Agents, Springer.","DOI":"10.1007\/978-3-540-73424-6_2"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1109\/TRO.2004.839232","article-title":"Coordinated multi-robot exploration","volume":"21","author":"Burgard","year":"2005","journal-title":"IEEE Trans. Robot."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1325","DOI":"10.1109\/JPROC.2006.876927","article-title":"Distributed multirobot exploration and mapping","volume":"94","author":"Fox","year":"2006","journal-title":"Proc. IEEE"},{"key":"ref_5","unstructured":"Groth, C., and Henrich, D. (2014, January 2\u20133). Single-shot learning and scheduled execution of behaviors for a robotic manipulator. Proceedings of the ISR\/Robotik 2014, 41st International Symposium on Robotics, Munich, Germany."},{"key":"ref_6","unstructured":"Lemaire, T., Alami, R., and Lacroix, S. (May, January 26). A distributed tasks allocation scheme in multi-UAV context. Proceedings of the IEEE International Conference on Robotics and Automation, New Orleans, LA, USA."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Gini, M. (2017, January 4\u20139). Multi-robot allocation of tasks with temporal and ordering constraints. Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, San Francisco, CA, USA.","DOI":"10.1609\/aaai.v31i1.11145"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Zhang, Y., and Parker, L.E. (2013, January 6\u201310). Multi-robot task scheduling. Proceedings of the 2013 IEEE International Conference on Robotics and Automation, Karlsruhe, Germany.","DOI":"10.1109\/ICRA.2013.6630992"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1002\/rob.21601","article-title":"Exploiting spatial locality and heterogeneity of agents for search and rescue teamwork","volume":"33","author":"Parker","year":"2016","journal-title":"J. Field Robot."},{"key":"ref_10","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_11","unstructured":"McIntire, M., Nunes, E., and Gini, M. (2016, January 9\u201313). Iterated multi-robot auctions for precedence-constrained task scheduling. Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, Singapore."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Sarkar, C., Paul, H.S., and Pal, A. (2018, January 21\u201325). A scalable multi-robot task allocation algorithm. Proceedings of the 2018 IEEE International Conference on Robotics and Automation ICRA, Brisbane, QLD, Australia.","DOI":"10.1109\/ICRA.2018.8460886"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Gombolay, M., Wilcox, R., and Shah, J. (2013, January 24\u201328). Fast Scheduling of Multi-Robot Teams with Temporospatial Constraints. Proceedings of the Robotics: Science and Systems IX, Berlin, Germany.","DOI":"10.15607\/RSS.2013.IX.049"},{"key":"ref_14","unstructured":"Clausen, J. (1999). Branch and Bound Algorithms-Principles and Examples, Department of Computer Science, University of Copenhagen."},{"key":"ref_15","unstructured":"Liu, C., and Kroll, A. (May, January 29). A centralized multi-robot task allocation for industrial plant inspection by using a* and genetic algorithms. Proceedings of the International Conference on Artificial Intelligence and Soft Computing, Zakopane, Poland."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2160","DOI":"10.4304\/jcp.7.9.2160-2167","article-title":"Multi-robot task allocation based on ant colony algorithm","volume":"7","author":"Wang","year":"2012","journal-title":"J. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Li, X., and Ma, H.x. (2008, January 20\u201323). Particle swarm optimization based multi-robot task allocation using wireless sensor network. Proceedings of the 2008 International Conference on Information and Automation, Changsha, China.","DOI":"10.1109\/ICINFA.2008.4608201"},{"key":"ref_18","unstructured":"Mosteo, A.R., and Montano, L. (2006, January 9\u201315). Simulated annealing for multi-robot hierarchical task allocation with flexible constraints and objective functions. Proceedings of the Workshop on Network Robot Systems: Toward Intelligent Robotic Systems Integrated with Environments, IROS, Beijing, China."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Mitiche, H., Boughaci, D., and Gini, M. (2015, January 8\u20139). Efficient heuristics for a time-extended multi-robot task allocation problem. Proceedings of the 2015 First International Conference on New Technologies of Information and Communication (NTIC), Mila, Algeria.","DOI":"10.1109\/NTIC.2015.7368756"},{"key":"ref_20","unstructured":"Maheswaran, R.T., Tambe, M., Bowring, E., Pearce, J.P., and Varakantham, P. (2004, January 23\u201323). Taking DCOP to the real world: Efficient complete solutions for distributed multi-event scheduling. Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, New York, NY, USA."},{"key":"ref_21","first-page":"343","article-title":"Auction-Based Multi-Robot Routing","volume":"5","author":"Lagoudakis","year":"2005","journal-title":"Robot. Sci. Syst."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/s10514-014-9403-2","article-title":"From selfish auctioning to incentivized marketing","volume":"37","author":"Liu","year":"2014","journal-title":"Auton. Robot."},{"key":"ref_23","unstructured":"Ma, H., and Koenig, S. (2016). Optimal target assignment and path finding for teams of agents. arXiv."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1080\/03052150600917128","article-title":"Scheduling trucks in container terminals using a genetic algorithm","volume":"39","author":"Ng","year":"2007","journal-title":"Eng. Optim."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Parker, L.E. (1995). L-ALLIANCE: A Mechanism for Adaptive Action Selection in Heterogeneous Multi-Robot Teams, Technical Report.","DOI":"10.2172\/211400"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Turpin, M., Michael, N., and Kumar, V. (2015). An approximation algorithm for time optimal multi-robot routing. Algorithmic Foundations of Robotics XI, Springer.","DOI":"10.1007\/978-3-319-16595-0_36"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1287\/trsc.29.3.267","article-title":"The m-Traveling Salesman Problem with Minmax Objective","volume":"29","author":"Franca","year":"1995","journal-title":"Transp. Sci. JSTOR"},{"key":"ref_28","unstructured":"Kato, S., Nishiyama, S., and Takeno, J. (1992, January 7\u201310). Coordinating Mobile Robots By Applying Traffic Rules. Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, Raleigh, NC, USA."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Van Den Berg, J.P., and Overmars, M.H. (2005, January 2\u20136). Prioritized motion planning for multiple robots. Proceedings of the 2005 IEEE\/RSJ International Conference on Intelligent Robots and Systems ICRA 2005, Edmonton, AB, Canada.","DOI":"10.1109\/IROS.2005.1545306"},{"key":"ref_30","unstructured":"Liu, M., Ma, H., Li, J., and Koenig, S. (2019, January 13\u201317). Task and path planning for multi-agent pickup and delivery. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), Montreal, QC, Canada."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1177\/0278364904045564","article-title":"A formal analysis and taxonomy of task allocation in multi-robot systems","volume":"23","author":"Gerkey","year":"2004","journal-title":"Int. J. Robot. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1495","DOI":"10.1177\/0278364913496484","article-title":"A comprehensive taxonomy for multi-robot task allocation","volume":"32","author":"Korsah","year":"2013","journal-title":"Int. J. Robot. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.robot.2016.10.008","article-title":"A taxonomy for task allocation problems with temporal and ordering constraints","volume":"90","author":"Nunes","year":"2017","journal-title":"Robot. Auton. Syst."},{"key":"ref_34","unstructured":"Gerkey, B.P., and Mataric, M.J. (2003, January 14\u201319). Multi-robot task allocation: Analyzing the complexity and optimality of key architectures. Proceedings of the 2003 IEEE International Conference on Robotics and Automation, Taipei, Taiwan."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Brucker, P. (2004). Scheduling Algorithms, Springer.","DOI":"10.1007\/978-3-540-24804-0"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1109\/70.681242","article-title":"ALLIANCE: An architecture for fault tolerant multirobot cooperation","volume":"14","author":"Parker","year":"1998","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_37","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences), W. H. Freeman."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jalgor.2005.01.007","article-title":"Approximations for Minimum and Min\u2013Max Vehicle Routing Problems","volume":"59","author":"Arkin","year":"2006","journal-title":"J. Algorithms"},{"key":"ref_39","first-page":"257","article-title":"Linear programming formulation of the multi-depot multiple traveling salesman problem with differentiated travel costs","volume":"2010","author":"Diaby","year":"2010","journal-title":"Travel. Salesm. Probl. Theory Appl."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Oberlin, P., Rathinam, S., and Darbha, S. (2009, January 10\u201312). A transformation for a heterogeneous, multiple depot, multiple traveling salesman problem. Proceedings of the 2009 American Control Conference, St. Louis, MO, USA.","DOI":"10.1109\/ACC.2009.5160666"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/j.ejor.2018.01.035","article-title":"The multi-pickup and delivery problem with time windows","volume":"269","author":"Naccache","year":"2018","journal-title":"Eur. J. Oper. Res."},{"key":"ref_42","first-page":"31","article-title":"Solving min\u2013max multi-depot vehicle routing problem","volume":"55","author":"Carlsson","year":"2009","journal-title":"Lect. Glob. Optim."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Bish, E.K., Chen, F.Y., Leong, Y.T., Nelson, B.L., Ng, J.W.C., and Simchi-Levi, D. (2007). Dispatching vehicles in a mega container terminal. Container Terminals and Cargo Systems, Springer.","DOI":"10.1007\/978-3-540-49550-5_9"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/j.dam.2011.09.014","article-title":"Approximation results for a min\u2013max location-routing problem","volume":"160","author":"Xu","year":"2012","journal-title":"Discret. Appl. Math."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1109\/SURV.2008.080403","article-title":"Max-min fairness and its applications to routing and load-balancing in communication networks: A tutorial","volume":"10","author":"Nace","year":"2008","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1287\/ijoc.14.2.132.118","article-title":"Solution of a min\u2013max vehicle routing problem","volume":"14","author":"Applegate","year":"2002","journal-title":"INFORMS J. Comput."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"1210","DOI":"10.1109\/LRA.2017.2666261","article-title":"Dubins orienteering problem","volume":"2","author":"Faigl","year":"2017","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Xu, Z., and Rodrigues, B. (2010, January 21\u201323). A 3\/2-approximation algorithm for multiple depot multiple traveling salesman problem. Proceedings of the Scandinavian Workshop on Algorithm Theory, Bergen, Norway.","DOI":"10.1007\/978-3-642-13731-0_13"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/j.orl.2003.11.010","article-title":"Min\u2013max tree covers of graphs","volume":"32","author":"Even","year":"2004","journal-title":"Oper. Res. Lett."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1287\/mnsc.21.5.591","article-title":"Note\u2014A computational survey of methods for the set covering problem","volume":"21","author":"Christofides","year":"1975","journal-title":"Manag. Sci."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1002\/net.3230110205","article-title":"A generalized assignment heuristic for vehicle routing","volume":"11","author":"Fisher","year":"1981","journal-title":"Networks"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(89)90044-8","article-title":"Approximation algorithms for the shortest common superstring problem","volume":"83","author":"Turner","year":"1989","journal-title":"Inf. Comput."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s10479-007-0170-8","article-title":"The dial-a-ride problem: Models and algorithms","volume":"153","author":"Cordeau","year":"2007","journal-title":"Ann. Oper. Res."},{"key":"ref_54","unstructured":"Luo, L., Chakraborty, N., and Sycara, K. (2018). A distributed algorithm for constrained multi-robot task assignment for grouped tasks. J. Contrib."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1002\/rob.21823","article-title":"Unsupervised learning-based flexible framework for surveillance planning with aerial vehicles","volume":"36","author":"Faigl","year":"2019","journal-title":"J. Field Robot."},{"key":"ref_56","unstructured":"(2021, November 09). Mohamed Bin Zayed International Robotics Challenge (MBZIRC) 2017. Available online: http:\/\/www.mbzirc.com."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","article-title":"The Hungarian method for the assignment problem","volume":"2","author":"Kuhn","year":"1995","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"Burkard, R.E., and Cela, E. (1999). Linear assignment problems and extensions. Handbook of Combinatorial Optimization, Springer.","DOI":"10.1007\/978-1-4757-3023-4_2"},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"970","DOI":"10.1109\/72.857776","article-title":"Local routing algorithms based on Potts neural networks","volume":"11","author":"Hakkinen","year":"2000","journal-title":"IEEE Trans. Neural Netw."},{"key":"ref_60","unstructured":"Soderberg, B., and Jonsson, H. (2001). Deterministic annealing and nonlinear assignment. arXiv."},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1162\/neco.1993.5.2.331","article-title":"Neural networks for optimization problems with inequality constraints: The knapsack problem","volume":"5","author":"Ohlsson","year":"1993","journal-title":"Neural Comput."},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"343","DOI":"10.2140\/pjm.1967.21.343","article-title":"Concerning nonnegative matrices and doubly stochastic matrices","volume":"21","author":"Sinkhorn","year":"1967","journal-title":"Pac. J. Math."},{"key":"ref_64","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1109\/TRO.2006.889486","article-title":"Improved techniques for grid mapping with rao-blackwellized particle filters","volume":"23","author":"Grisetti","year":"2007","journal-title":"IEEE Trans. Robot."},{"key":"ref_65","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_66","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/s10514-013-9351-2","article-title":"An anytime assignment algorithm: From local task swapping to global optimality","volume":"35","author":"Liu","year":"2013","journal-title":"Auton. Robot."}],"container-title":["Robotics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2218-6581\/10\/4\/122\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:28:03Z","timestamp":1760167683000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2218-6581\/10\/4\/122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,9]]},"references-count":66,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["robotics10040122"],"URL":"https:\/\/doi.org\/10.3390\/robotics10040122","relation":{},"ISSN":["2218-6581"],"issn-type":[{"value":"2218-6581","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,9]]}}}