{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T20:24:59Z","timestamp":1769631899689,"version":"3.49.0"},"reference-count":38,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003400","name":"Ontario Ministry of Research and Innovation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003400","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Un. Sys."],"published-print":{"date-parts":[[2017,4]]},"abstract":"<jats:p> This paper focuses on decentralized task allocation and sequencing for multiple heterogeneous robots. Each task is defined as visiting a point in a subset of the robot configuration space \u2014 this definition captures a variety of tasks including inspection and servicing. The robots are heterogeneous in that they may be subject to different differential motion constraints. Our approach is to transform the problem into a multi-vehicle generalized traveling salesman problem (GTSP). To solve the GTSP, we propose a novel decentralized implementation of large-neighborhood search (LNS). Our solution approach leverages the GTSP insertion methods proposed in Fischetti et al. [A branch-and-cut algorithm for the symmetric generalized traveling salesman problem, Oper. Res. 45(3) (1997) 378\u2013394]. to repeatedly remove and reinsert tasks from each robot path. Decentralization is achieved using combinatorial-auctions between the robots on tasks removed from robot\u2019s path. We provide bounds on the length of the dynamically feasible robot paths produced by the insertion methods. We also show that the number of bids in each combinatorial auction, a crucial factor in the runtime, scales linearly with the number of tasks. Finally, we present extensive benchmarking results to characterize both solution quality and runtime, which show improvements over existing decentralized task allocation methods. <\/jats:p>","DOI":"10.1142\/s2301385017500066","type":"journal-article","created":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T02:25:10Z","timestamp":1497579910000},"page":"79-95","source":"Crossref","is-referenced-by-count":30,"title":["Heterogeneous Task Allocation and Sequencing via Decentralized Large Neighborhood Search"],"prefix":"10.1142","volume":"05","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5244-367X","authenticated-orcid":false,"given":"Armin","family":"Sadeghi","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Waterloo, Waterloo ON, N2L 3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen L.","family":"Smith","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Waterloo, Waterloo ON, N2L 3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2017,8,2]]},"reference":[{"key":"S2301385017500066BIB001","doi-asserted-by":"publisher","DOI":"10.1287\/opre.45.3.378"},{"key":"S2301385017500066BIB002","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045564"},{"key":"S2301385017500066BIB003","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913496484"},{"key":"S2301385017500066BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00284-2"},{"key":"S2301385017500066BIB005","series-title":"Algorithmics and Combinatorics","volume-title":"Combinatorial Optimization: Theory and Algorithms","volume":"21","author":"Korte B.","year":"2007","edition":"4"},{"key":"S2301385017500066BIB006","doi-asserted-by":"publisher","DOI":"10.1137\/0206041"},{"key":"S2301385017500066BIB007","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2005.847567"},{"key":"S2301385017500066BIB008","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2008.925814"},{"key":"S2301385017500066BIB009","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2011.2166311"},{"issue":"1","key":"S2301385017500066BIB010","first-page":"39","volume":"31","author":"Noon C. E.","year":"1993","journal-title":"INFOR"},{"key":"S2301385017500066BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2010.08.011"},{"key":"S2301385017500066BIB013","author":"Smith S. L.","year":"2016","journal-title":"Comput. Oper. Res."},{"key":"S2301385017500066BIB014","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906061705"},{"key":"S2301385017500066BIB015","doi-asserted-by":"publisher","DOI":"10.3390\/a6010084"},{"key":"S2301385017500066BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16595-0_36"},{"key":"S2301385017500066BIB020","doi-asserted-by":"publisher","DOI":"10.1002\/rob.20384"},{"key":"S2301385017500066BIB021","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2009.2022423"},{"key":"S2301385017500066BIB022","doi-asserted-by":"publisher","DOI":"10.1142\/S230138501450006X"},{"key":"S2301385017500066BIB023","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2005.I.045"},{"key":"S2301385017500066BIB024","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-013-9351-2"},{"key":"S2301385017500066BIB025","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2009.2026926"},{"key":"S2301385017500066BIB030","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.44.8.1131"},{"key":"S2301385017500066BIB031","doi-asserted-by":"publisher","DOI":"10.1023\/B:HEUR.0000045322.51784.2a"},{"key":"S2301385017500066BIB032","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.09.012"},{"key":"S2301385017500066BIB033","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1050.0135"},{"key":"S2301385017500066BIB034","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.06.044"},{"key":"S2301385017500066BIB035","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913515307"},{"key":"S2301385017500066BIB037","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2006.872110"},{"key":"S2301385017500066BIB038","doi-asserted-by":"publisher","DOI":"10.1007\/978-90-481-9707-1_16"},{"key":"S2301385017500066BIB039","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21711-5"},{"key":"S2301385017500066BIB040","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"S2301385017500066BIB041","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"S2301385017500066BIB042","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915577958"},{"key":"S2301385017500066BIB043","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.10.008"},{"key":"S2301385017500066BIB045","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2014.2380593"},{"key":"S2301385017500066BIB046","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.5.848"},{"key":"S2301385017500066BIB048","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-014-9395-y"},{"key":"S2301385017500066BIB049","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.4.376"}],"container-title":["Unmanned Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S2301385017500066","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:17:21Z","timestamp":1565137041000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S2301385017500066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4]]},"references-count":38,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2017,8,2]]},"published-print":{"date-parts":[[2017,4]]}},"alternative-id":["10.1142\/S2301385017500066"],"URL":"https:\/\/doi.org\/10.1142\/s2301385017500066","relation":{},"ISSN":["2301-3850","2301-3869"],"issn-type":[{"value":"2301-3850","type":"print"},{"value":"2301-3869","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4]]}}}