Page 170 - 《软件学报》2020年第12期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2020,31(12):3836−3851 [doi: 10.13328/j.cnki.jos.005969] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
新型时空众包平台中的在线三维稳定匹配问题

1
2
2
2
李博扬 , 成雨蓉 , 王国仁 , 袁 野 , 孙永佼 1
1
(东北大学 计算机科学与工程学院,辽宁 沈阳 110819)
2 (北京理工大学 计算机学院,北京 100081)
通讯作者: 成雨蓉, E-mail: yrcheng@bit.edu.cn

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

中文引用格式: 李博扬,成雨蓉,王国仁,袁野,孙永佼.新型时空众包平台中的在线三维稳定匹配问题.软件学报,2020,31(12):
3836−3851. http://www.jos.org.cn/1000-9825/5969.htm
英文引用格式: Li BY, Cheng YR, Wang GR, Yuan Y, Sun YJ. 3D-online stable matching problem for new spatial
crowdsourcing platforms. Ruan Jian Xue Bao/Journal of Software, 2020,31(12):3836−3851 (in Chinese). http://www.jos.org.cn/
1000-9825/5969.htm

3D-online Stable Matching Problem for New Spatial Crowdsourcing Platforms
1
2
2
2
LI Bo-Yang , CHENG Yu-Rong , WANG Guo-Ren , YUAN Ye , SUN Yong-Jiao 1
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

∗ 基金项目: 国家重点研发计划(2016YFC1401900); 国家自然科学基金(U1811262, 61902023, 61932004, 61572119, 61622202,
61672145, 61732003, 61572121, 61972077); 中央高 校基础科 研业 务费 (N181605012, N171604007); 中国 博士后科 学基金
(2018M631358)
Foundation item: 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)
收稿时间: 2015-04-22; 修改时间: 2015-06-11, 2015-08-11; 采用时间: 2015-09-10