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)  唯一性约束:一旦匹配成功,这个匹配中的用户、工人、工作点都不会被其他匹配占用.
             在以上的定义中,每个工作点只能匹配一个工人和一个用户.通过将工作点进行复制的方法,可以将这个约
         束直接扩展到一个地点匹配多个工人和多个用户的场景.本文采用欧几里德距离计算两个点之间的直线距离,
   168   169   170   171   172   173   174   175   176   177   178