第6期 潘庆先，等：基于禁忌搜索的时空众包任务分配算法 ·1041· 在现有的时空众包研究中，任务分配是最核 求最长的子线路距离最短（时间最短），也就是 心的研究问题之一1。在当前的时空众包问题 VRP问题中经典的最小最大车辆路径问题。苏 中，大部分问题场景都是基于动态场景，众包任 畅等6提出了一种改进模型，通过自适应地改进 务4和众包工人是动态出现的，随着时间推 状态转移规则、权系数等条件使得解决方案效果 移，不断有新的对象出现和旧的对象消失。相比 得到了提升。Bai等)和Yu等8分别提出车辆 于传统的静态场景下的时空众包问题，动态场 路径问题的模型与算法，通过在仿真数据的实验 景更符合实际情况，在实际生活中更有应用价 对该问题进行了理论分析。Ren对于MMRVP 值。但是，现有的在线任务分配大多只考虑到众 问题，通过对问题模型的分析提出优化效果更好 包任务和工人，研究的重点主要集中在工人完成 的混合算法。 任务的质量上，对于空间中的位置和工人执行任 由于车辆路径问题是NP难问题，通过算法 务时的路径规划研究得比较少，而三类对象的研 得到精确的结果是十分困难的，需通过寻找近似 究，通常只考虑距离范围，未考虑路径规划和移 算法来获得近似最优解，因此目前学者们在构造 动成本的问题，对距离和时间的转换问题也研究 高质量的启发式算法上做了大量的工作。 较少。为将任务推荐给合适的工人1，本文将众 包任务、众包工人和它们所对应的时空属性结合 2问题描述 起来，提出了基于自适应阈值的禁忌搜索算法， 本节给出形式化的问题描述，首先对问题以 在满足时间约束和地理位置约束的条件下使得任 及对象进行定义，然后介绍一下问题模型，并进 务分配数最大化，同时保证众包工人能获得更多 行动态场景下的复杂性分析。 的收益。 2.1基本定义 1相关工作 定义1众包任务。众包任务定义为t=<a, l,(x,y,rP,d,D,>,a表示到达时刻，l,表示位置 1.1时空众包 其中x、y分别为欧氏空间中的横、纵坐标，，表示 众包指的是一个公司或机构把过去由员工执 范围，p,为完成任务所获得的的报酬，d,表示任务 行的工作任务，以自由自愿的形式外包给非特定 截止时间，D,表示任务对应的顾客，需要工人将 的（而且通常是大型的）大众志愿者的做法山。随 任务送到任务对应地点执行。 着众包应用的不断发展，众包形式由传统众包转 定义2众包工人。众包工人定义为w=<a, 变为了如今的时空众包，研究的内容也更加多样 1(x,y以，rr,qe>,aw表示到达时间，ln表示位置，w表 化。Boutsis等9首次提出了动态场景下的三类对 示范围，9表示工人具有的评价值，作为工人任 象的在线任务分配问题，面向众包任务、众包工 务完成质量的评估。 人以及任务执行地点的合理匹配。可以看出目前 定义3任务对应地点。任务对应地点定义 研究更多的是三类对象条件下的问题。刘辉等山 为c=<id,l(x,y)>,地点c在任务t到达的同时出现， 提出了一种能够对任务分配的当前情况自动调整 id对应任务的序号，l.表示任务对应地点的位置。 阈值的算法，但分配总效用不高；Hassan等a提 定义4任务分配问题。给定任务集T、工人 出一种基于统计预测的自适应阈值算法，进一步 集W和任务所对应的地点集C,众包工人和众包 提高了分配总效用。不难看出，自适应阈值的应 任务随机动态出现，地点C伴随着对应任务的出 用能使问题解决方案得到优化。 现而出现，求解的目标是找到一个任务t、工人w 1.2车辆路径规划问题(VRP) 和地点c的顺序集，在该顺序下，使得任务的平均 随着科技的迅速发展，路径规划在众多领域 分配时间最小化，式(1)和式(2)为优化的目标函数： 内发挥着关键作用。比如：无人机驾驶、机器人 避障行驶、GPS卫星导航等。 WT 旅行商问题)是车辆路径规划问题的典型 Minavg(R)= (1) n 案例，Gaeryl4已经证明旅行商问题是NP难问 题，因此可以推出车辆路径规划问题也属于NP MaxC=>CouplewT (2) 难问题。 在真实环境中，通常VRP问题的优化目标 (3) al<dr,dist(w,t)<min(rw,r) 不是要求整个行车路程最短（费用最少），而是要 Arrive<Arrivewe (4)在现有的时空众包研究中，任务分配是最核 心的研究问题之一[2-3]。在当前的时空众包问题 中，大部分问题场景都是基于动态场景，众包任 务 [4-5] 和众包工人是动态出现的[6] ，随着时间推 移，不断有新的对象出现和旧的对象消失。相比 于传统的静态场景下的时空众包问题[7] ，动态场 景更符合实际情况，在实际生活中更有应用价 值。但是，现有的在线任务分配大多只考虑到众 包任务和工人，研究的重点主要集中在工人完成 任务的质量上，对于空间中的位置和工人执行任 务时的路径规划研究得比较少，而三类对象的研 究，通常只考虑距离范围，未考虑路径规划和移 动成本的问题，对距离和时间的转换问题也研究 较少。为将任务推荐给合适的工人[8] ，本文将众 包任务、众包工人和它们所对应的时空属性结合 起来，提出了基于自适应阈值的禁忌搜索算法， 在满足时间约束和地理位置约束的条件下使得任 务分配数最大化，同时保证众包工人能获得更多 的收益。 1 相关工作 1.1 时空众包 众包指的是一个公司或机构把过去由员工执 行的工作任务，以自由自愿的形式外包给非特定 的 (而且通常是大型的) 大众志愿者的做法[1]。随 着众包应用的不断发展，众包形式由传统众包转 变为了如今的时空众包，研究的内容也更加多样 化。Boutsis 等 [9] 首次提出了动态场景下的三类对 象的在线任务分配问题，面向众包任务、众包工 人以及任务执行地点的合理匹配。可以看出目前 研究更多的是三类对象条件下的问题[10]。刘辉等[11] 提出了一种能够对任务分配的当前情况自动调整 阈值的算法，但分配总效用不高；Hassan 等 [12] 提 出一种基于统计预测的自适应阈值算法，进一步 提高了分配总效用。不难看出，自适应阈值的应 用能使问题解决方案得到优化。 1.2 车辆路径规划问题 (VRP) 随着科技的迅速发展，路径规划在众多领域 内发挥着关键作用。比如：无人机驾驶、机器人 避障行驶、GPS 卫星导航等。 旅行商问题[13] 是车辆路径规划问题的典型 案例，Gaery[14] 已经证明旅行商问题是 NP 难问 题，因此可以推出车辆路径规划问题也属于 NP 难问题。 在真实环境中，通常 VRP 问题[15] 的优化目标 不是要求整个行车路程最短 (费用最少),而是要 求最长的子线路距离最短 (时间最短)，也就是 VRP 问题中经典的最小最大车辆路径问题。苏 畅等[16] 提出了一种改进模型，通过自适应地改进 状态转移规则、权系数等条件使得解决方案效果 得到了提升。Bai 等 [17] 和 Yu 等 [18] 分别提出车辆 路径问题的模型与算法，通过在仿真数据的实验 对该问题进行了理论分析。Ren[19] 对于 MMRVP 问题，通过对问题模型的分析提出优化效果更好 的混合算法。 由于车辆路径问题是 NP 难问题，通过算法 得到精确的结果是十分困难的，需通过寻找近似 算法来获得近似最优解，因此目前学者们在构造 高质量的启发式算法上做了大量的工作。 2 问题描述 本节给出形式化的问题描述，首先对问题以 及对象进行定义，然后介绍一下问题模型，并进 行动态场景下的复杂性分析。 2.1 基本定义 t =< at , lt(x, y),rt , pt ,dt ,IDt > at lt x y rt pt dt IDt 定义 1 众包任务。众包任务定义为 ， 表示到达时刻， 表示位置， 其中 、 分别为欧氏空间中的横、纵坐标， 表示 范围， 为完成任务所获得的的报酬， 表示任务 截止时间， 表示任务对应的顾客，需要工人将 任务送到任务对应地点执行。 w =< aw, lw(x, y),rw,qw > aw lw rw qw 定义 2 众包工人。众包工人定义为 ， 表示到达时间， 表示位置， 表 示范围， 表示工人具有的评价值，作为工人任 务完成质量的评估。 c =< idc ,lc(x, y) > c t idc lc 定义 3 任务对应地点。任务对应地点定义 为 ，地点 在任务 到达的同时出现， 对应任务的序号， 表示任务对应地点的位置。 T W C c t w c 定义 4 任务分配问题。给定任务集 、工人 集 和任务所对应的地点集 ，众包工人和众包 任务随机动态出现，地点 伴随着对应任务的出 现而出现，求解的目标是找到一个任务 、工人 和地点 的顺序集，在该顺序下，使得任务的平均 分配时间最小化，式 (1) 和式 (2) 为优化的目标函数： Minavg(R) = ∑n i=1 WTi n (1) MaxC = ∑n i=1 CoupleWTi (2) Couplewt = { 0 1, alwt < dt ,dist(w,t) < min(rw , rt) (3) Arrivewt < Arrivewc (4) 第 6 期 潘庆先，等：基于禁忌搜索的时空众包任务分配算法 ·1041·