{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T12:13:40Z","timestamp":1771330420228,"version":"3.50.1"},"reference-count":21,"publisher":"Walter de Gruyter GmbH","issue":"2","license":[{"start":{"date-parts":[[2018,12,21]],"date-time":"2018-12-21T00:00:00Z","timestamp":1545350400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,4,24]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We propose a method for task allocation to multiple physical agents that works when tasks have temporal and spatial constraints and agents have different capacities. Assuming that the problem is over-constrained, we need to find allocations that maximize the number of tasks that can be done without violating any of the constraints. The contribution of this work is the study of a new multi-robot task allocation problem and the design and the experimental evaluation of our approach, an iterated local search that is suitable for time critical applications. We created test instances on which we experimentally show that our approach outperforms a state-of-the-art approach to a related problem. Our approach improves the baseline\u2019s score on average by 2.35% and up to 10.53%, while responding in times shorter than the baseline\u2019s, on average, 1.6 s and up to 5.5 s shorter. Furthermore, our approach is robust to run replication and is not very sensitive to parameters tuning.<\/jats:p>","DOI":"10.1515\/jisys-2018-0267","type":"journal-article","created":{"date-parts":[[2018,12,20]],"date-time":"2018-12-20T04:01:39Z","timestamp":1545278499000},"page":"347-360","source":"Crossref","is-referenced-by-count":10,"title":["Iterated Local Search for Time-extended Multi-robot Task Allocation with Spatio-temporal and Capacity Constraints"],"prefix":"10.1515","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9571-7079","authenticated-orcid":false,"given":"Hakim","family":"Mitiche","sequence":"first","affiliation":[{"name":"Department of Computer Science , USTHB , BP 32 El-Alia, Babezzouar, Algiers 16111, Algeria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dalila","family":"Boughaci","sequence":"additional","affiliation":[{"name":"Department of Computer Science , USTHB , BP 32 El-Alia, Babezzouar, Algiers 16111, Algeria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Gini","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering Department , University of Minnesota , 4-192 Keller Hall, 200 Union St SE, Minneapolis , MN 55455, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2018,12,21]]},"reference":[{"key":"2025120523495621340_j_jisys-2018-0267_ref_001_w2aab3b7c11b1b6b1ab1b8b1Aa","doi-asserted-by":"crossref","unstructured":"S. Amador, S. Okamoto and R. Zivan, Dynamic multi-agent task allocation with spatial and temporal constraints, in: Proc. International Conf. on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1495\u20131503, 2014.","DOI":"10.1609\/aaai.v28i1.8889"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_002_w2aab3b7c11b1b6b1ab1b8b2Aa","doi-asserted-by":"crossref","unstructured":"I.-M. Chao, B. L. Golden and E. A. Wasil, The team orienteering problem, Eur. J. Oper. Res.88 (1996), 464\u2013474.10.1016\/0377-2217(94)00289-4","DOI":"10.1016\/0377-2217(94)00289-4"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_003_w2aab3b7c11b1b6b1ab1b8b3Aa","doi-asserted-by":"crossref","unstructured":"E. Ferrante, A. E. Turgut, E. Du\u00e9\u00f1ez-Guzm\u00e1n, M. Dorigo and T. Wenseleers, Evolution of self-organized task specialization in robot swarms, PLoS Comput. Biol.11 (2015), e1004273.10.1371\/journal.pcbi.1004273","DOI":"10.1371\/journal.pcbi.1004273"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_004_w2aab3b7c11b1b6b1ab1b8b4Aa","doi-asserted-by":"crossref","unstructured":"P. Ferreira, F. Boffo and A. Bazzan, Using swarm-GAP for distributed task allocation in complex scenarios, in: N. Jamali, P. Scerri and T. Sugawara, eds., Massively Multi-Agent Technology, Lecture Notes in Computer Science 5043, pp. 107\u2013121, Springer, Berlin\/Heidelberg, 2008.","DOI":"10.1007\/978-3-540-85449-4_8"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_005_w2aab3b7c11b1b6b1ab1b8b5Aa","doi-asserted-by":"crossref","unstructured":"B. P. Gerkey and M. J. Matari\u0107, A formal analysis and taxonomy of task allocation in multi-robot systems, Int. J. Robot. Res.23 (2004), 939\u2013954.10.1177\/0278364904045564","DOI":"10.1177\/0278364904045564"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_006_w2aab3b7c11b1b6b1ab1b8b6Aa","doi-asserted-by":"crossref","unstructured":"A. Gunawan, H. C. Lau, P. Vansteenwegen and K. Lu, Well-tuned algorithms for the team orienteering problem with time windows, J. Oper. Res. Soc.68 (2017), 861\u2013876.10.1057\/s41274-017-0244-1","DOI":"10.1057\/s41274-017-0244-1"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_007_w2aab3b7c11b1b6b1ab1b8b7Aa","doi-asserted-by":"crossref","unstructured":"Q. Hu and A. Lim, An iterative three-component heuristic for the team orienteering problem with time windows, Eur. J. Oper. Res.232 (2014), 276\u2013286.10.1016\/j.ejor.2013.06.011","DOI":"10.1016\/j.ejor.2013.06.011"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_008_w2aab3b7c11b1b6b1ab1b8b8Aa","unstructured":"H. Kitano and T. Satoshi, Robocup rescue: a grand challenge for multiagent and intelligent systems, AI Mag.22 (2001), 39\u201352."},{"key":"2025120523495621340_j_jisys-2018-0267_ref_009_w2aab3b7c11b1b6b1ab1b8b9Aa","unstructured":"M. Koes, I. Nourbakhsh and K. Sycara, Heterogeneous multirobot coordination with spatial and temporal constraints, in: Proc. 20th National Conf. on Artificial Intelligence (AAAI), pp. 1292\u20131297, June 2005."},{"key":"2025120523495621340_j_jisys-2018-0267_ref_010_w2aab3b7c11b1b6b1ab1b8c10Aa","doi-asserted-by":"crossref","unstructured":"N. Labadi, R. Mansini, J. Melechovsk\u00fd and R. W. Calvo, The team orienteering problem with time windows: an LP-based granular variable neighborhood search, Eur. J. Oper. Res.220 (2012), 15\u201327.10.1016\/j.ejor.2012.01.030","DOI":"10.1016\/j.ejor.2012.01.030"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_011_w2aab3b7c11b1b6b1ab1b8c11Aa","doi-asserted-by":"crossref","unstructured":"M. G. Lagoudakis, E. Markakis, D. Kempe, P. Keskinocak, A. Kleywegt, S. Koenig, C. Tovey, A. Meyerson and S. Jain, Auction-based multi-robot routing, in: Robotics: Science and Systems, pp. 343\u2013350, 2005.","DOI":"10.15607\/RSS.2005.I.045"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_012_w2aab3b7c11b1b6b1ab1b8c12Aa","doi-asserted-by":"crossref","unstructured":"H. R. Louren\u00e7o, O. C. Martin and T. St\u00fctzle, Iterated local search, in: M. Gendreau and J-Y. Potvin, eds., Handbook of Metaheuristics, 2nd Edition International Series in Operations Research and Management Science 146, pp. 363\u2013398, Springer, New York, USA, 2010.","DOI":"10.1007\/978-1-4419-1665-5_12"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_013_w2aab3b7c11b1b6b1ab1b8c13Aa","doi-asserted-by":"crossref","unstructured":"A. Lucena, Time-dependent traveling salesman problem \u2013 the deliveryman case, Networks20 (1990), 753\u2013763.10.1002\/net.3230200605","DOI":"10.1002\/net.3230200605"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_014_w2aab3b7c11b1b6b1ab1b8c14Aa","doi-asserted-by":"crossref","unstructured":"J. Melvin, P. Keskinocak, S. Koenig, C. Tovey and B. Y. Ozkaya, Multi-robot routing with rewards and disjoint time windows, in: Proc. IEEE\/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 2332\u20132337, San Diego, CA, USA, 2007.","DOI":"10.1109\/IROS.2007.4399625"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_015_w2aab3b7c11b1b6b1ab1b8c15Aa","unstructured":"H. Mitiche, J. Godoy and M. Gini, On the tuning and evaluation of iterated local search, in: Proc. of Metaheuristics International Conference (MIC), Agadir, Morocco, 2015."},{"key":"2025120523495621340_j_jisys-2018-0267_ref_016_w2aab3b7c11b1b6b1ab1b8c16Aa","unstructured":"R. Montemanni and L. M. Gambardella, An ant colony system for team orienteering problems with time windows, Found. Comput. Decis. Sci.34 (2009), 287\u2013306."},{"key":"2025120523495621340_j_jisys-2018-0267_ref_017_w2aab3b7c11b1b6b1ab1b8c17Aa","doi-asserted-by":"crossref","unstructured":"E. Nunes, M. Manner, H. Mitiche and M. Gini, A taxonomy for task allocation problems with temporal and ordering constraints, Robot. Auton. Syst.90 (2017), 55\u201370.10.1016\/j.robot.2016.10.008","DOI":"10.1016\/j.robot.2016.10.008"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_018_w2aab3b7c11b1b6b1ab1b8c18Aa","doi-asserted-by":"crossref","unstructured":"S. D. Ramchurn, A. Farinelli, K. S. Macarthur and N. R. Jennings, Decentralized coordination in RoboCup Rescue, Comput. J.53 (2010), 1447\u20131461.10.1093\/comjnl\/bxq022","DOI":"10.1093\/comjnl\/bxq022"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_019_w2aab3b7c11b1b6b1ab1b8c19Aa","doi-asserted-by":"crossref","unstructured":"P. Scerri, A. Farinelli, S. Okamoto and M. Tambe, Allocating tasks in extreme teams, in: Proc. International Conf. on Autonomous Agents and Multiagent Systems (AAMAS), pp. 727\u2013734, 2005.","DOI":"10.1145\/1082473.1082584"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_020_w2aab3b7c11b1b6b1ab1b8c20Aa","doi-asserted-by":"crossref","unstructured":"M. M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper. Res.35 (1987), 254\u2013265.10.1287\/opre.35.2.254","DOI":"10.1287\/opre.35.2.254"},{"key":"2025120523495621340_j_jisys-2018-0267_ref_021_w2aab3b7c11b1b6b1ab1b8c21Aa","doi-asserted-by":"crossref","unstructured":"P. Vansteenwegen, W. Souffriau, G. V. Berghe and D. V. Oudheusden, Iterated local search for the team orienteering problem with time windows, Comput. Oper. Res.36 (2009), 3281\u20133290.10.1016\/j.cor.2009.03.008","DOI":"10.1016\/j.cor.2009.03.008"}],"container-title":["Journal of Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/jisys.2019.28.issue-2\/jisys-2018-0267\/jisys-2018-0267.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jisys-2018-0267\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jisys-2018-0267\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T23:50:05Z","timestamp":1764978605000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jisys-2018-0267\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,21]]},"references-count":21,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2018,12,21]]},"published-print":{"date-parts":[[2019,4,24]]}},"alternative-id":["10.1515\/jisys-2018-0267"],"URL":"https:\/\/doi.org\/10.1515\/jisys-2018-0267","relation":{},"ISSN":["2191-026X","0334-1860"],"issn-type":[{"value":"2191-026X","type":"electronic"},{"value":"0334-1860","type":"print"}],"subject":[],"published":{"date-parts":[[2018,12,21]]}}}