| 摘要: |
| 近年来，时空众包平台正逐步走入人们的生活，并受到研究者的广泛关注.在时空众包平台中，任务分配是一个核心问题，即在满足时间和空间的条件约束下，如何为不同用户分配合适的工人来进行服务.现有的工作往往将最大化任务匹配个数或效用值之和作为研究目标，这些方法关注全局的解决方案，但是没有考虑用户和工人的偏好来提高他们对于分配的满意程度.此外，现有工作大多只考虑用户和工人两种角色，即工人移动到用户当前位置进行服务.但是，新型时空众包平台的中往往包含用户、工人和工作点三种角色，即为用户和工人分配一个工作点来进行服务.基于以上不足，三维时空稳定分配问题被提出.但是，此问题只关注了静态场景，而时空众包平台往往是在线的，即工人和用户发出的任务都是实时出现的.因此，提出了面向新型时空众包平台的三维在线稳定匹配问题和一种基础算法.通过分析基础算法的不足，结合人工智能的方法提出一种改进算法来解决这个问题.采用大量的真实数据和合成数据集来验证算法的高效性和有效性. |
| 关键词: 时空数据 众包 稳定匹配 在线算法 预测 |
| DOI：10.13328/j.cnki.jos.005969 |
| 分类号: |
| 基金项目:国家重点研发计划（2016YFC1401900）；国家自然科学基金（U1811262，61902023，61932004，61572119，61622202，61672145，61732003，61572121，61972077）；中央高校基础科研业务费（N181605012，N171604007）；中国博士后科学基金（2018M631358） |
|
| 3D-online Stable Matching Problem for New Spatial Crowdsourcing Platforms |
|
LI Bo-Yang1, CHENG Yu-Rong2, WANG Guo-Ren2, YUAN Ye2, SUN Yong-Jiao1
|
|
1.School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China;2.School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China
|
| Abstract: |
| In recent years, spatial crowdsourcing platforms attract more and more attention. One of the core issues is to assign proper workers to users to finish their tasks under the temporal and spatial constraints. Most existing works aim to maximize the number of tasks that are finished or the sum of utility score. These approaches ignore the preference of users and workers. Moreover, existing works usually only focus on two roles, workers and users. Workers travel to the location of users to finish the tasks. However, new spatial crowdsourcing platforms contain three types of roles, workers, users, and workplaces. The platforms assign workplaces for workers and users to finish the tasks. Thus, the stable matching problem in the three-dimensional platforms is proposed to solve the static scenarios. However, most spatial crowdsourcing platforms are online scenarios. Workers and tasks issued by the users appear in real time. Therefore, a three-dimensional online stable matching problem is formalized in new spatial crowdsourcing platforms. A baseline algorithm and an improved algorithm are proposed which benefit from the advantages of artificial intelligence to solve this problem. Finally, extensive experiments are conducted on real datasets and synthetic datasets to verify the efficiency and effectiveness of the proposed algorithms. |
| Key words: spatial database crowdsourcing stable matching online algorithm prediction |
