{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:31:05Z","timestamp":1760236265901,"version":"build-2065373602"},"reference-count":27,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2021,11,5]],"date-time":"2021-11-05T00:00:00Z","timestamp":1636070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61807008, 61806053, 61932007, 62076060, 61703097"],"award-info":[{"award-number":["61807008, 61806053, 61932007, 62076060, 61703097"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Natural Science Foundation of Jiangsu Province of China","award":["BK20180369, BK20180356, BK20201394, BK20171363"],"award-info":[{"award-number":["BK20180369, BK20180356, BK20201394, BK20171363"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Principal\u2013assistant agent teams are often employed to solve tasks in multiagent collaboration systems. Assistant agents attached to the principal agents are more flexible for task execution and can assist them to complete tasks with complex constraints. However, how to employ principal\u2013assistant agent teams to execute time-critical tasks considering the dependency between agents and the constraints among tasks is still a challenge so far. In this paper, we investigate the principal\u2013assistant collaboration problem with deadlines, which is to allocate tasks to suitable principal\u2013assistant teams and construct routes satisfying the temporal constraints. Two cases are considered in this paper, including single principal\u2013assistant teams and multiple principal\u2013assistant teams. The former is formally formulated in an arc-based integer linear programming model. We develop a hybrid combination algorithm for adapting larger scales, the idea of which is to find an optimal combination of partial routes generated by heuristic methods. The latter is defined in a path-based integer linear programming model, and a branch-and-price-based (BP-based) algorithm is proposed that introduces the number of assistant-accessible tasks surrounding a task to guide the route construction. Experimental results validate that the hybrid combination algorithm and the BP-based algorithm are superior to the benchmarks in terms of the number of served tasks and the running time.<\/jats:p>","DOI":"10.3390\/a14110327","type":"journal-article","created":{"date-parts":[[2021,11,5]],"date-time":"2021-11-05T10:33:09Z","timestamp":1636108389000},"page":"327","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Hybrid Multiagent Collaboration for Time-Critical Tasks: A Mathematical Model and Heuristic Approach"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1095-3580","authenticated-orcid":false,"given":"Yifeng","family":"Zhou","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Southeast University, Nanjing 211189, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7929-0682","authenticated-orcid":false,"given":"Kai","family":"Di","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Southeast University, Nanjing 211189, China"}]},{"given":"Haokun","family":"Xing","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Southeast University, Nanjing 211189, China"}]}],"member":"1968","published-online":{"date-parts":[[2021,11,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2700327","article-title":"Reliable task allocation with load balancing in multiplex networks","volume":"10","author":"Jiang","year":"2015","journal-title":"ACM Trans. Auton. Adapt. Syst. (TAAS)"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1007\/s10458-014-9273-1","article-title":"High reliable and efficient task allocation in networked multi-agent systems","volume":"29","author":"Rahimzadeh","year":"2015","journal-title":"Auton. Agents-Multi-Agent Syst."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1671","DOI":"10.1109\/TPDS.2012.249","article-title":"Task allocation for undependable multiagent systems in social networks","volume":"24","author":"Jiang","year":"2012","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1287\/trsc.2017.0791","article-title":"Optimization approaches for the traveling salesman problem with drone","volume":"52","author":"Agatz","year":"2018","journal-title":"Transp. Sci."},{"key":"ref_5","first-page":"63","article-title":"Daimler to work with Matternet to develop delivery van drones","volume":"45","author":"Sloat","year":"2016","journal-title":"Wall Str. J."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Scott, J., and Scott, C. (2017, January 4\u20137). Drone delivery models for healthcare. Proceedings of the Hawaii International Conference on System Sciences, Hilton Waikoloa Village, HI, USA.","DOI":"10.24251\/HICSS.2017.399"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.trc.2015.03.005","article-title":"The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery","volume":"54","author":"Murray","year":"2015","journal-title":"Transp. Res. Part Emerg. Technol."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1016\/j.trc.2017.11.015","article-title":"On the min-cost traveling salesman problem with drone","volume":"86","author":"Ha","year":"2018","journal-title":"Transp. Res. Part Emerg. Technol."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"2241","DOI":"10.1109\/TITS.2018.2865893","article-title":"Joint ground and aerial package delivery services: A stochastic optimization approach","volume":"20","author":"Sawadsitang","year":"2018","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.tcs.2018.11.016","article-title":"Deadline TSP","volume":"771","author":"Farbstein","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1287\/trsc.1050.0118","article-title":"A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection","volume":"40","author":"Righini","year":"2006","journal-title":"Transp. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.cor.2017.01.020","article-title":"Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows","volume":"83","author":"Parragh","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Bansal, N., Blum, A., Chawla, S., and Meyerson, A. (2004, January 13\u201315). Approximation algorithms for deadline-TSP and vehicle routing with time-windows. Proceedings of the Annual ACM Symposium on Theory of Computing, Chicago, IL, USA.","DOI":"10.1145\/1007352.1007385"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1016\/j.trb.2019.03.005","article-title":"Vehicle routing problem with drones","volume":"122","author":"Wang","year":"2019","journal-title":"Transp. Res. Part Methodol."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Gunawan, A., Lau, H.C., and Lu, K. (2015, January 8\u201310). An iterated local search algorithm for solving the orienteering problem with time windows. Proceedings of the European Conference on Evolutionary Computation in Combinatorial Optimization, Copenhagen, Denmark.","DOI":"10.1007\/978-3-319-16468-7_6"},{"key":"ref_16","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"49191","DOI":"10.1109\/ACCESS.2019.2910134","article-title":"A hybrid genetic algorithm on routing and scheduling for vehicle-assisted multi-drone parcel delivery","volume":"7","author":"Peng","year":"2019","journal-title":"IEEE Access"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF00940812","article-title":"Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm","volume":"45","year":"1985","journal-title":"J. Optim. Theory Appl."},{"key":"ref_19","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_20","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1109\/34.295910","article-title":"Simulated annealing: A proof of convergence","volume":"16","author":"Granville","year":"1994","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.ejor.2016.04.059","article-title":"Orienteering problem: A survey of recent variants, solution approaches and applications","volume":"255","author":"Gunawan","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","article-title":"Equation of state calculations by fast computing machines","volume":"21","author":"Metropolis","year":"1953","journal-title":"J. Chem. Phys."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1016\/j.cor.2012.07.008","article-title":"On an exact method for the constrained shortest path problem","volume":"40","author":"Lozano","year":"2013","journal-title":"Comput. Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Applegate, D., Bixby, R., Chv\u00e1tal, V., and Cook, W. (2001). TSP Cuts Which Do Not Conform to the Template Paradigm. Computational Combinatorial Optimization, Springer.","DOI":"10.1007\/3-540-45586-8_7"},{"key":"ref_25","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erdos","year":"1960","journal-title":"Publ. Math. Inst. Hung. Acad. Sci"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1287\/opre.12.4.568","article-title":"Scheduling of vehicles from a central depot to a number of delivery points","volume":"12","author":"Clarke","year":"1964","journal-title":"Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1057\/jors.1992.88","article-title":"The orienteering problem with time windows","volume":"43","author":"Kantor","year":"1992","journal-title":"J. Oper. Res. Soc."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/11\/327\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:26:32Z","timestamp":1760167592000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/11\/327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,5]]},"references-count":27,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2021,11]]}},"alternative-id":["a14110327"],"URL":"https:\/\/doi.org\/10.3390\/a14110327","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,11,5]]}}}