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

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

现有方法还存在另一个问题:现有的研究只关注了全局最优的问题,但是并不能同时根据用户和工人的个
人情况来考虑分配结果.如例 2 中所示:虽然取得了全局移动距离最短,但是对于用户 u 3 和工人 w 2 来说,p 2 比 p 1
同时距离他们两个更近,没有分配到 p 2 会让他们对让当前分配产生不满的情绪.为解决这个问题,文献[6]提出了
面向三维的稳定匹配问题,该问题保证每一个任务分配的结果都处在一个稳定的状态.即:对于一组匹配的工人
和用户,不存在一个对于工人和用户都更适合的工作点.如图 2(b)所示,虽然该方案并不是全局移动距离最小的
分配,但是当前的每一个分配都处于稳定的状态,降低了用户和工人的不满情绪.但是,该工作面向的是静态匹
配问题,现有的平台要具有动态处理问题的能力,用户的任务和工人的状态都是实时变化的,该工作并不能很好
地解决在线问题.

y y
8 8
u 1(6,7) u 1(6,7)
7 7
6 6
p 3(8,5) p 3(8,5)
5 5
w 2(4,4) w 2(4,4)
4 4
u 2(1,3) p 1(7,4) u 2(1,3) p 1(7,4)
3 3
w 3(9,3)
2 p 2 (3,2) w 3 (9,3) 2 p 2(3,2)
u 3 (5,2) u 3(5,2)
1 1
w 1(1,1) w 1(1,1)
1 2 3 4 5 6 7 8 9 10 x 1 2 3 4 5 6 7 8 9 10 x
(a) 最小化移动距离分配策略 (b) 稳定分配策略
Fig.2 Three-dimensional work assignment strategy
图 2 三维任务分配策略

综上所述,在时空众包平台的任务分配问题中,根据用户和工人的实际情况考虑分配结果更加合理,同时要
具有处理在线任务的能力.因此,定义一种在线的三维稳定匹配问题是本文要解决的问题之一.另外,由于现有
的研究人员为研究过在线的三维稳定匹配问题,因此,现有的工作能够提供的参考性有限.而在线的三维稳定匹
配问题更加复杂,不确定性因素更多,从而更加难以解决.为此,本文提出了时空众包平台中的在线三维稳定匹
配问题,既保证任务分配的质量,又具有实时性,弥补了现有工作的不足.为解决该问题,本文首先提出一种基础
算法.基础算法采用贪心的思想,当用户到达最长等待时间的时候,根据距离来为用户和工人安排工作点.由于
在线问题具有很强的未知性和不确定性,本文提出了一种改进算法,结合人工智能中的预测技术,为在线匹配提
供指导.最后,本文在真实数据集和合成数据集上验证了算法的有效性和高效性.
本文第 1 节对时空众包平台中的实时三维稳定匹配问题进行定义.第 2 节对相关工作加以总结.第 3 节介
绍一个基础算法,并分析其正确性和复杂度.第 4 节分析基础算法的不足,并提出一种改进的方法.第 5 节通过真
实数据集和合成数据集上的实验,验证本文提出算法的高效性和有效性.第 6 节对全文加以总结,并提出对未来
工作的设想.
1 问题定义

本节中,我们先介绍时空众包平台中的一些基本概念,然后给出时空众包平台中的在线三维稳定匹配问题
正式定义.
一个时空众包平台由用户、工人和工作点组成.平台中的用户会发布一系列的任务,给定由 n 个用户组成
的用户集 U,每个用户 u∈U,通常被定义为以下形式:u=(l u ,D u ,S u ,T u ),l u 是用户当前的位置,D u 是用户对于所有工作
点根据距离的升序排序,S u 是用户发出任务的时刻,T u 是用户可以等待的最长时间.如果用户发出的任务在
S u +T u 时刻之前还没有被安排合适的工人来服务,那么这个任务将会失效.平台中的工人会响应用户发出的任