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

3840 Journal of Software 软件学报 Vol.31, No.12, December 2020

在实际应用中,也可以使用最短路距离等,这些结果是等价的.
三维在线稳定匹配问题的离线版本与在线版本问题相同,只是在线问题中平台只知道当前已经到达的用
户和工人信息;而在离线问题中,所有用户、工人和工作点的时空信息都是已知的.
定理 1. 三维在线稳定匹配问题的离线版本是 NP-难.
证明:考虑离线问题中的一个特殊情况,假设用户和工人的出现时间都是 0 时刻(即开始时刻全部出现),用
户等待时间为无穷大.那么我们可以将文献[6]中的三维稳定匹配(3D-SSM)问题归约到这个特殊情况.所以,三
维在线稳定匹配问题的离线版本是 NP-难. □
鉴于问题的困难性以及在线问题具有很强的未知性和不确定性,在后面的章节中,本文先后提出两个近似
算法对该问题进行求解.

2 相关工作

本节从 3 个角度总结与本文相关的现有工作:(1) 时空众包;(2) 在线匹配;(3) 离线稳定婚姻匹配.
2.1 时空众包
随着移动互联网和 O2O 商业模式的发展,时空众包正逐渐成为研究领域的热点话题.时空众包平台中的用
户指通过互联网发布时空众包任务,并通过众包工人在现实世界中完成该任务.区别于互联网众包平台,时空众
包平台同时受线上和线下的时空属性的约束.任务分配是时空众包领域的一个核心问题,即,如何为众包任务安
排合适的众包工人.按照问题类别划分,任务分配问题被分为任务匹配和任务规划两种问题.
[7]
• 任务匹配问题通常将众包工人和众包任务进行一对一或一对多的匹配.Xing 等人 将匹配问题和博弈
[8]
论相结合,以此来提高用户对匹配的满意程度.Zhang 等人 根据工人的可靠程度和雇佣成本,提出了
一个可靠任务分配问题;
[9]
• 任务规划问题则是为工人规划路径来完成多个任务.Deng 等人 研究在离线任务下为工人规划路径
来尽可能地完成更多的任务.Tao 等人 [10] 面向在线场景研究当工人和任务在线到达时如何最大化完成
任务的总效用值.
文献[11,12]研究了基于事件的社交网络(EBSN)中用户行程规划问题,考虑了时间冲突、行程预算以及活动
人数等约束来为用户安排最满意的行程安排.在此基础上,Cheng 等人 [13] 也提出了一个基于事件的社交网络中
的稳定规划算法,该算法同时考虑了用户和活动举办者的双向偏好.文献[6]首次提出一个面向三维的稳定匹配
问题,证明该为题为 NP 难,并提出两种近似算法(DSM 和 Path Swap)进行求解:DSM 算法采用拆分的思想动态
的为用户进行匹配;Path Swap 算法构建一个索引,通过此索引为用户匹配任务.虽然这些研究工作都对时空众
包平台中的任务分配问题作出了研究,但大部分研究都只考虑用户和工人两种角色,与本研究中关注用户、工
人和工作点的 3 种角色的问题模型具有很大的区别.
2.2 在线匹配
相较于离线算法,在线算法中无法事先获得用户和工人出现的时间以及位置,所以具有很强的不确定性.以
经典的最大权二分图匹配问题为基础的在线匹配问题已经被广泛研究 [14−16] .近年来,研究人员也开使用在线算
法来解决时空众包平台中的动态匹配问题.在 Hassan 等人 [17] 研究的问题中,用户提交任务是实时的,平台通过
分析工人的历史接单行为和地理信息来为任务安排合适的工人.更进一步,Tong 等人 [18] 研究了工人和任务同时
动态出现的场景,通过分析预测的方法指导工人的接单行为.文献[19]同时考虑距离和订单价值两个因素,提出
一个以最大化收益和用户满意度的稳定在线匹配问题.文献[20]研究通过降低用户最长等待时间来提高用户的
满意程度.
2.3 离线稳定婚姻匹配问题
在稳定婚姻问题 [21] 中,假设分别存在 n 个男人和女人,每个人对另一个性别的全体成员具有一个偏好排序.
一个稳定的婚姻指不存在任意两对情侣,他们都喜欢对方的伴侣胜过当前的伴侣.研究证明:稳定婚姻问题的解