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

李博扬 等:新型时空众包平台中的在线三维稳定匹配问题 3837

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

[1]
近年来,随着移动网络技术和 O2O 商业模式的发展,时空众包平台正逐步走入人们的生活 .常见的时空众
包平台包括出行服务平台(例如滴滴(https://www.didiglobal.com/))、外卖派送平台(例如饿了么(https://www.
ele.me/))等等.在这些平台中,用户通过互联网在线上发布自己的任务或需求,平台为用户安排合适的众包工人
在线下完成任务.区别于传统的众包平台,时空众包平台同时受线上因素和线下的时空因素的约束.以滴滴平台
为例,用户发布用车服务的订单,平台将订单派给司机到指定地点接送乘客.用户所在区域的交通状况和供需情
况,会很大程度上决定用户的等待时间.
在时空众包平台中,一个经典的问题是:在满足时空约束的前提下,为用户安排合适的工人来完成其发布的
任务.现有的研究工作 [2−4] 往往只关注用户和工人两种角色,他们将用户发布任务的位置视为工人完成任务的
地点.在这种模型下,工人从其当前的位置移动到任务的地点来服务用户.以外卖配送平台为例,配送人员需要
将外卖送到用户给定的地址.这些工作的求解目标是最大化匹配个数或效用值值之和(用户满意度、平台收入
等),或者最小化分配成本(距离成本等).
例 1:图 1 描述了一个二维任务分配策略的情景.在地图中存在 5 个用户和 5 个工人,用户和工人的地理位
置分别标注在地图上.任意两个位置之间的距离采用欧式距离计算.当系统为用户分配工人后,工人从当前位置
移动到用户的任务位置.本例中,以最小化工人移动距离为求解目标,红线表示了任务的分配结果和工人的移动
距离.
y
8
u 1(4,7)
7
u 5(1,6)
6 u 4(2,5) w 5(8,7)
5
4 u 2(6,3) w 1(6,5)
3
w 4(3,3)
2
1 w 2 (1,2) u 3(6,2)
w 3(8,1)
1 2 3 4 5 6 7 8 9 10 x
Fig.1 Two-dimensional work assignment strategy
图 1 二维任务分配策略

然而,一些新的众包平台的出现也带来了新的挑战.这些新平台不再局限于两种用户和工人两种角色.在这
些平台中,用户不再原地等待工人上门服务,而是与工人约定一个地点来完成任务,例如南瓜车(http://www.
nanguache.com/).这些平台为用户和工人提供专业的场地,所以用户和工人需要从当前位置移动到平台安排的
场地来完成任务.这样,平台中的角色由用户和工人两种角色转变为用户、工人、工作点这 3 种角色.由于角色
[5]
的增加,原有的研究无法直接扩展到新的平台中.针对新的挑战,Song 等人 提出了面向三维的任务分配问题,
根据用户、工人、地点的不同组合方式,会有不同的效用值,研究如何将这个效用值最大化.
例 2:图 2(a)中描述了一个三维任务分配策略的情景.在地图中共存在 3 个用户、3 个工人和 3 个工作点.
当用户和工人被分配工作点后,他们将移动到工作点的位置来完成任务.采用文献[5]的策略,将最小化用户和工
人的移动距离作为求解目标,红线表示了用户和工人的移动距离.