新型时空众包平台中的在线三维稳定匹配问题
作者:
作者单位:

作者简介:

李博扬(1992-),男,博士生,CCF学生会员,主要研究领域为社交网络数据分析,时空数据分析,机器学习.
成雨蓉(1989-),女,博士后,CCF专业会员,主要研究领域为图数据查询处理与分析,时空众包数据分析,社交网络数据分析.
王国仁(1966-),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为不确定数据管理,数据密集型计算,可视媒体数据管理与分析,非结构化数据管理,分布式查询处理与优化技术(主要包括传感器网络和P2P对等计算),生物信息学.
袁野(1981-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为云计算,大数据管理(包括图数据管理,不确定数据管理,数据隐私保护),P2P计算.
孙永佼(1983-),男,博士,副教授,CCF专业会员,主要研究领域为云计算,大数据管理,数据分析,机器学习,不确定数据管理,分布式数据管理.

通讯作者:

成雨蓉,E-mail:yrcheng@bit.edu.cn

中图分类号:

基金项目:

国家重点研发计划(2016YFC1401900);国家自然科学基金(U1811262,61902023,61932004,61572119,61622202,61672145,61732003,61572121,61972077);中央高校基础科研业务费(N181605012,N171604007);中国博士后科学基金(2018M631358)


3D-online Stable Matching Problem for New Spatial Crowdsourcing Platforms
Author:
Affiliation:

Fund Project:

National Key Research and Development Program of China (2016YFC1401900); National Natural Science Foundation of China (U1811262, 61902023, 61932004, 61572119, 61622202, 61672145, 61732003, 61572121, 61972077); Fundamental Research Funds for the Central Universities (N181605012, N171604007); China Postdoctoral Science General Program Foundation (2018M631358)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    近年来,时空众包平台正逐步走入人们的生活,并受到研究者的广泛关注.在时空众包平台中,任务分配是一个核心问题,即在满足时间和空间的条件约束下,如何为不同用户分配合适的工人来进行服务.现有的工作往往将最大化任务匹配个数或效用值之和作为研究目标,这些方法关注全局的解决方案,但是没有考虑用户和工人的偏好来提高他们对于分配的满意程度.此外,现有工作大多只考虑用户和工人两种角色,即工人移动到用户当前位置进行服务.但是,新型时空众包平台的中往往包含用户、工人和工作点三种角色,即为用户和工人分配一个工作点来进行服务.基于以上不足,三维时空稳定分配问题被提出.但是,此问题只关注了静态场景,而时空众包平台往往是在线的,即工人和用户发出的任务都是实时出现的.因此,提出了面向新型时空众包平台的三维在线稳定匹配问题和一种基础算法.通过分析基础算法的不足,结合人工智能的方法提出一种改进算法来解决这个问题.采用大量的真实数据和合成数据集来验证算法的高效性和有效性.

    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.

    参考文献
    相似文献
    引证文献
引用本文

李博扬,成雨蓉,王国仁,袁野,孙永佼.新型时空众包平台中的在线三维稳定匹配问题.软件学报,2020,31(12):3836-3851

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2015-04-22
  • 最后修改日期:2015-08-11
  • 录用日期:
  • 在线发布日期: 2020-12-03
  • 出版日期: 2020-12-06
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号