计算机工程与应用2024，Vol.60Issue(17)：252-262,11.DOI:10.3778/j.issn.1002-8331.2309-0118
空间众包中隔离敏感的任务匹配算法
Isolation-Sensitive Task Assignment in Spatial Crowdsourcing
摘要
Abstract
With the popularity of mobile Internet access and the growth of the sharing economy,space crowdsourcing platforms have gained in widespread popularity.There exists a class of crowdsourcing applications that tries to make the crowdsourcing tasks spatially localized in scope,which is to reduce the movement of people between spatial regions when performing spatial tasks.Based on this requirement,this paper presents the spatially isolation-sensitive task matching problem,which minimizes the sum of the cross-regional costs incurred by the movement of workers for all matched tasks,given the set of workers and the set of tasks with the locations of the spatial regions to which they belong,provided that all tasks can be completed.Efficient spatial isolation-sensitive task assignment algorithms in online platforms are the research objectives.This paper proposes matching algorithm based on spatial hierarchical merging and grouping,which transforms tasks and workers distributed in spatial regions to regional adjacency graph nodes,proposes the concept of δ-clique for grouping regional nodes,and then performs overall matching of grouped nodes,which improves the efficiency of the matching algorithm to a greater extent.Finally,the effectiveness of the proposed algorithm is verified by conducting full comparison experiments on real datasets in terms of both cross-region cost and running time,which the proposed algo-rithms reduce cross regional costs by an average of nearly 16%and improve matching efficiency by an average of nearly 5 times.关键词
空间众包/区域划分/跨区域代价/KM算法Key words
spatial crowdsourcing/regional division/cross region cost/Kuhn-Munkres(KM)algorithm分类
信息技术与安全科学引用本文复制引用
刘俊岭,高新宇,孙焕良,许景科..空间众包中隔离敏感的任务匹配算法[J].计算机工程与应用,2024,60(17):252-262,11.基金项目
国家自然科学基金(62073227) （62073227）
国家重点研发计划课题(2021YFF0306303) （2021YFF0306303）
辽宁省自然科学基金(2019-MS-264) （2019-MS-264）
辽宁省教育厅资助项目(LJZ2021008). （LJZ2021008）
