Page 173 - 《软件学报》2020年第12期
P. 173
李博扬 等:新型时空众包平台中的在线三维稳定匹配问题 3839
务,给定由 m 个工人组成的工人集 W,每个工人 w∈W 通常被定义为以下形式:w=(l w ,D w ,S w ),l w 是工人当前的位置,
D w 是工人对于所有工作点根据距离的升序排序,S w 是工人开始工作的时间.即:从 S w 开始,工人可以接受系统中
的任务.如果工人已经接收了一个任务,那么他/她将不再接收其他任务.平台中的工作点是供用户和工人完成
任务的地点,对于每个工作点 p∈P,通常被定义为以下形式:p=(l p ,DW p ,QU p ),l p 是工作点的位置,DW p 和 DU p 是工
作点对于工人和用户的距离升序排序.在最开始,所有工作点都是可用的,如果一个工作点被分配了用户和工
人,那么它将变为不可用状态.
例 3:图 3 和表 1 描述了一个在线任务分配场景,其中,图 3 描述了工人、用户和工作点的位置信息,表 1 描
述了用户和工人在线到达的时间.在 t 0 时刻,所有工作点都处于可用状态,w 1 和 u 1 出现在地图上;随后在 t 1 时刻,
w 2 出现在地图上,表示他/她可以平台分配的任务.假设 u 1 的最长等待时间为 2 个时间段,那么平台可以安排 t 2
时刻或之前出现的工人(即 w 1 或 w 2 )来完成 u 1 的任务;否则任务在 t 2 时刻到期,并在地图中消失.
y
9
w 6 u 1
8
p 5
p 6
7
w 2 u 6 w 1
6
p 4
w 3
5
p 3
u 2
4
u 3
3
p 1
2
w 4 p 2 u 5
1
u 4 w 5
1 2 3 4 5 6 7 8 9 10 x
Fig.3 Locations of workers, users and workplaces
图 3 用户、工人和工作点的位置分布
Table 1 Arrival time of workers and users
表 1 工人和用户的出现时间
t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9
w 1 u 1 w 2 u 2 w 3 u 3 w 4 u 4 u 5 w 5 w 6 u 6
当平台为用户分配工人和工作点之后,我们将这个分配称为一个元组.在本文研究的问题中,对于元组有特
殊的稳定性要求,满足这个要求的元组被称为稳定元组.
定义 1(稳定元组). 一个元组(w,u,p)被称为稳定元组,当且仅当不存在另一个工作点 p′,满足 w 和 p′的距离
小于 w 和 p 的距离,并且 u 和 p′的距离小于 u 和 p 的距离.
在例 2 中,(w 1 ,u 3 ,p 2 )是一个不稳定元组,由于 p 3 到 w 1 和 u 3 的距离小于 p 2 到 w 1 和 u 3 的距离,所以(w 1 ,u 3 ,p 2 )
是不稳定的.与之相反,(w 2 ,u 1 ,p 1 )是稳定元组,原因是不存在一个工作点,同时距离 w 2 和 u 1 更近.同理,(w 3 ,u 2 ,p 3 )和
图 2(b)中的所有元组也都是稳定元组.
基于以上的基本概念,接下来介绍三维在线稳定匹配问题的定义.
定义 2(三维在线稳定匹配问题). 给定用户集 U、工人集 W 和工作点集 P,三维在线问题匹配问题的目标
是找到一个满足以下条件的匹配数最多的结果 M(即 max|M|):
(1) 稳定约束:每个匹配的元组(w,u,p)∈M 都是稳定元组;
(2) 时间约束:每个用户都是在[S u ,S u +T u ]时间段内被匹配工人,每个工人都是在 S w 时刻后被匹配任务;
(3) 唯一性约束:一旦匹配成功,这个匹配中的用户、工人、工作点都不会被其他匹配占用.
在以上的定义中,每个工作点只能匹配一个工人和一个用户.通过将工作点进行复制的方法,可以将这个约
束直接扩展到一个地点匹配多个工人和多个用户的场景.本文采用欧几里德距离计算两个点之间的直线距离,