第15卷第6期 智能系统学报 Vol.15 No.6 2020年11月 CAAI Transactions on Intelligent Systems Nov.2020 D0L:10.11992tis.202006055 基于禁忌搜索的时空众包任务分配算法 潘庆先2，般增轩2，董红斌'，高照龙3，童向荣2 (1.哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001,2.烟台大学计算机与控制工程学院，山 东烟台264005,3.德拉萨大学达斯玛里纳斯校区科学与计算机学院，甲米地达斯玛里纳斯999005) 摘要：为了在时空众包任务分配过程中减少移动成本、缩短任务完成时间，本文将时空众包和路径规划问题 结合起来，提出了一种基于自适应阈值的禁忌搜索算法，该算法通过在线学习的方式，进行路径规划设计，计 算出每个任务合理的预估等待时间，匹配区域内的众包任务，并在最短的时间内完成任务。通过实验对比，本 文所提算法在任务耗费时间上平均比Adaptive RT算法降低I3%,比ASPT算法降低23.3%。在移动成本上比 Adaptive RT算法降低了6.99%.比ASPT算法降低了25.9%。 关键词：时空众包：任务分配；路径规划；禁忌搜索算法；自适应阈值：3类对象；服务质量；报酬 中图分类号：TP311文献标志码：A 文章编号：1673-4785(2020)06-1040-09 中文引用格式：潘庆先，殷增轩，董红斌，等.基于禁忌搜索的时空众包任务分配算法.智能系统学报，2020,15(6)： 1040-1048. 英文引用格式：PAN Qingxian,.YIN Zengxuan,DONG Hongbin,etal.Spatiotemporal crowdsourcing task assignment algorithm based on tabu search[Jl.CAAI transactions on intelligent systems,2020,15(6):1040-1048. Spatiotemporal crowdsourcing task assignment algorithm based on tabu search PAN Qingxian,YIN Zengxuan',DONG Hongbin',GAO Zhaolong,TONG Xiangrong (1.College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China;2.College of Computer and Control Engineering,Yantai University,Yantai 264005,China;3.College of Science and Computer Studies,DE la Salle University- Dasmarinas,Dasmarinas 999005,Philippines) Abstract:To reduce the moving cost and task completion time of the distribution process in a spatiotemporal crowd- sourcing task,in this paper,by combining spatiotemporal crowdsourcing and path planning,a tabu search algorithm based on adaptive threshold is proposed.This algorithm uses online learning for path planning and designs a reasonable estimated waiting time for each task by matching crowdsourcing tasks in the area,thus,completing tasks in the shortest time.Through experimental comparison,we concluded that the average task time of the algorithm proposed in this pa- per is 13%and 23.3%lower than that of the Adaptive RT and ASPT algorithms,respectively,and the moving cost of the proposed algorithm is 6.99%and 25.9%lower than that of the Adaptive RT and ASPT algorithms,respectively. Keywords:spatiotemporal crowdsourcing;task assignment;route planning;tabu search;adaptive threshold;three types of objects;service quality;reward 随着移动互联网的飞速发展，众包任务山开 模式一时空众包应运而生。VRP(vehicle route 始出现时间上和空间上的约束，一种新型的众包 planning)路径规划是一个经典问题，其目的是寻 找一条从起点到目标终点能满足各种时间、空间 收稿日期：2020-06-30. 基金项目：国家自然科学基金项目(60903098.61502140. 约束的行驶路线，与时空众包中的任务分配问题 61572418,61472095):黑龙江自然科学基金项目 具有很多相似性，因此本文考虑将两者结合起 (LH2020F023). 通信作者：殷增轩.E-mail:yzxytu@163.com 来，以解决任务分配问题
DOI: 10.11992/tis.202006055 基于禁忌搜索的时空众包任务分配算法 潘庆先1,2，殷增轩2 ，董红斌1 ，高照龙3 ，童向荣2 （1. 哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001; 2. 烟台大学 计算机与控制工程学院，山 东 烟台 264005; 3. 德拉萨大学达斯玛里纳斯校区 科学与计算机学院，甲米地 达斯玛里纳斯 999005） 摘 要：为了在时空众包任务分配过程中减少移动成本、缩短任务完成时间，本文将时空众包和路径规划问题 结合起来，提出了一种基于自适应阈值的禁忌搜索算法，该算法通过在线学习的方式，进行路径规划设计，计 算出每个任务合理的预估等待时间，匹配区域内的众包任务，并在最短的时间内完成任务。通过实验对比，本 文所提算法在任务耗费时间上平均比 Adaptive RT 算法降低 13%，比 ASPT 算法降低 23.3%。在移动成本上比 Adaptive RT 算法降低了 6.99%，比 ASPT 算法降低了 25.9%。 关键词：时空众包；任务分配；路径规划；禁忌搜索算法；自适应阈值；3 类对象；服务质量；报酬 中图分类号：TP311 文献标志码：A 文章编号：1673−4785(2020)06−1040−09 中文引用格式：潘庆先, 殷增轩, 董红斌, 等. 基于禁忌搜索的时空众包任务分配算法 [J]. 智能系统学报, 2020, 15(6): 1040–1048. 英文引用格式：PAN Qingxian, YIN Zengxuan, DONG Hongbin, et al. Spatiotemporal crowdsourcing task assignment algorithm based on tabu search[J]. CAAI transactions on intelligent systems, 2020, 15(6): 1040–1048. Spatiotemporal crowdsourcing task assignment algorithm based on tabu search PAN Qingxian1,2 ，YIN Zengxuan2 ，DONG Hongbin1 ，GAO Zhaolong3 ，TONG Xiangrong2 (1. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China; 2. College of Computer and Control Engineering, Yantai University, Yantai 264005, China; 3. College of Science and Computer Studies, DE la Salle UniversityDasmarinas, Dasmarinas 999005, Philippines) Abstract: To reduce the moving cost and task completion time of the distribution process in a spatiotemporal crowdsourcing task, in this paper, by combining spatiotemporal crowdsourcing and path planning, a tabu search algorithm based on adaptive threshold is proposed. This algorithm uses online learning for path planning and designs a reasonable estimated waiting time for each task by matching crowdsourcing tasks in the area, thus, completing tasks in the shortest time. Through experimental comparison, we concluded that the average task time of the algorithm proposed in this paper is 13% and 23.3% lower than that of the Adaptive RT and ASPT algorithms, respectively, and the moving cost of the proposed algorithm is 6.99% and 25.9% lower than that of the Adaptive RT and ASPT algorithms, respectively. Keywords: spatiotemporal crowdsourcing; task assignment; route planning; tabu search; adaptive threshold; three types of objects; service quality; reward 随着移动互联网的飞速发展，众包任务[1] 开 始出现时间上和空间上的约束，一种新型的众包 模式−时空众包应运而生。VRP(vehicle route planning) 路径规划是一个经典问题，其目的是寻 找一条从起点到目标终点能满足各种时间、空间 约束的行驶路线，与时空众包中的任务分配问题 具有很多相似性，因此本文考虑将两者结合起 来，以解决任务分配问题。 收稿日期：2020−06−30. 基金项目：国家自然科学基金项 目 (60903098， 61502140， 61572418， 61472095)；黑龙江自然科学基金项目 (LH2020F023). 通信作者：殷增轩.E-mail：yzxytu@163.com. 第 15 卷第 6 期 智 能 系 统 学 报 Vol.15 No.6 2020 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2020
第6期 潘庆先，等：基于禁忌搜索的时空众包任务分配算法 ·1041· 在现有的时空众包研究中，任务分配是最核 求最长的子线路距离最短（时间最短），也就是 心的研究问题之一1。在当前的时空众包问题 VRP问题中经典的最小最大车辆路径问题。苏 中，大部分问题场景都是基于动态场景，众包任 畅等6提出了一种改进模型，通过自适应地改进 务4和众包工人是动态出现的，随着时间推 状态转移规则、权系数等条件使得解决方案效果 移，不断有新的对象出现和旧的对象消失。相比 得到了提升。Bai等)和Yu等8分别提出车辆 于传统的静态场景下的时空众包问题，动态场 路径问题的模型与算法，通过在仿真数据的实验 景更符合实际情况，在实际生活中更有应用价 对该问题进行了理论分析。Ren对于MMRVP 值。但是，现有的在线任务分配大多只考虑到众 问题，通过对问题模型的分析提出优化效果更好 包任务和工人，研究的重点主要集中在工人完成 的混合算法。 任务的质量上，对于空间中的位置和工人执行任 由于车辆路径问题是NP难问题，通过算法 务时的路径规划研究得比较少，而三类对象的研 得到精确的结果是十分困难的，需通过寻找近似 究，通常只考虑距离范围，未考虑路径规划和移 算法来获得近似最优解，因此目前学者们在构造 动成本的问题，对距离和时间的转换问题也研究 高质量的启发式算法上做了大量的工作。 较少。为将任务推荐给合适的工人1，本文将众 包任务、众包工人和它们所对应的时空属性结合 2问题描述 起来，提出了基于自适应阈值的禁忌搜索算法， 本节给出形式化的问题描述，首先对问题以 在满足时间约束和地理位置约束的条件下使得任 及对象进行定义，然后介绍一下问题模型，并进 务分配数最大化，同时保证众包工人能获得更多 行动态场景下的复杂性分析。 的收益。 2.1基本定义 1相关工作 定义1众包任务。众包任务定义为t=,a表示到达时刻，l,表示位置 1.1时空众包 其中x、y分别为欧氏空间中的横、纵坐标，，表示 众包指的是一个公司或机构把过去由员工执 范围，p,为完成任务所获得的的报酬，d,表示任务 行的工作任务，以自由自愿的形式外包给非特定 截止时间，D,表示任务对应的顾客，需要工人将 的（而且通常是大型的）大众志愿者的做法山。随 任务送到任务对应地点执行。 着众包应用的不断发展，众包形式由传统众包转 定义2众包工人。众包工人定义为w=,aw表示到达时间，ln表示位置，w表 化。Boutsis等9首次提出了动态场景下的三类对 示范围，9表示工人具有的评价值，作为工人任 象的在线任务分配问题，面向众包任务、众包工 务完成质量的评估。 人以及任务执行地点的合理匹配。可以看出目前 定义3任务对应地点。任务对应地点定义 研究更多的是三类对象条件下的问题。刘辉等山 为c=,地点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 定义 1 众包任务。众包任务定义为 ， 表示到达时刻， 表示位置， 其中 、 分别为欧氏空间中的横、纵坐标， 表示 范围， 为完成任务所获得的的报酬， 表示任务 截止时间， 表示任务对应的顾客，需要工人将 任务送到任务对应地点执行。 w = aw lw rw qw 定义 2 众包工人。众包工人定义为 ， 表示到达时间， 表示位置， 表 示范围， 表示工人具有的评价值，作为工人任 务完成质量的评估。 c = 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·
·1042· 智能系统学报 第15卷 cpe T 任务的执行速度都是相同的，可以通过计算完成 (5) 所有任务的总路程，来换算出执行完成所有任务 式中：WT:为每个工人完成所有被分配任务所耗 的平均时间，优化的最终目标就是最小化平均任 费的时间；n为完成的任务数；R为完成所有任务 务执行时间。 的平均耗费时间；Couple,,是一个匹配参数，当工 人w和任务1匹配成功并且完成时间早于任务的 9 截止时间并且距离范围符合要求时，则任务完 8 成，Couple=l,否则视为任务未完成，Couple=O。 C为任务完成数量，希望尽可能地完成所有任务， 6 5 同时满足以下约束条件： 号 1)每个任务都有最后的结束时间，要求工人 必须在任务结束前将任务带到任务执行地点并完 成任务，假设工人们的技术水平相同，并且任务 到达任务执行地点便视为任务完成，如式(3)所示。 0 2345678910 2)任务完成具有先后顺序，必须先领取任 相对距离km 务，才能将任务带到执行地点，未领取任务之前 图1任务、工人和任务执行地点位置示意 便到达任务执行地点则不能视为任务完成，即式 Fig.1 Locations of tasks,workers,and customers (4)中工人领取任务的时间必须早于工人到达任 表1任务、工人和任务执行地点信息表 务t对应的地点c的时间。 Table 1 Information of tasks,workers,and customers 3)同一个工人执行的任务数不可过多，为保 对象 坐标km 报酬 服务质量 证总体的执行时间较少，在保证时间约束和总路 t (3.1,8.7 1 程最小化的前提下，将任务平均地分配给工人， t2 (5.5,4.7 1 使得每个工人都能凭劳动力获得报酬。如式 (2.82.3) 1 (5)所示，等号左边为工人w完成任务的数量， 5 W和T分别为该地区工人和任务的总数。 CL (10.0,9.7) 4)众包任务、工人以及任务执行地点要求在 C2 (7.7,6.0) 一定的区域范围内，距离过远的对象将不能进行 S (6.1,1.4) 任务分配，如式(3)所示。 WI (4.6,9.5) 0.635153 例1描述了任务分配的执行过程。 W2 (1.5,4.0) 0.469222 例1假设众包工作环境中有3个众包任务 、2、3,2个众包工人w和w2,以及每个众包任 由于问题的背景为动态情景，为了避免出现 务所对应的任务地点c、c2、c3,它们的位置如图1 局部最优的情况，设置了时间窗，即在一定的时 所示，每个点的信息如表1所示。众包工人和众 间段内，该时间段出现的3类对象的所有信息都 包任务随机散落在各个位置，当有任务出现的时 是可知的。众包工人和众包任务随机散落在各个 候，其所对应的执行地点也会相应地出现，此时 位置，当有任务出现的时候，其所对应的执行地 首先出现的任务就会分配给符合条件的工人去执 点也会相应地出现，此时首先出现的任务就会分 行，工人需要前往任务地点领取任务，随后再前 配给符合条件的工人。 往任务对应的执行地点完成任务。在对象出现的 假设工人%首先上班，此时任务出现，其 过程中，一般会进行两种决策过程：第1种是直接 所对应的任务执行地点c同时出现，系统将任务 将任务分配给最近的众包工人；第2种是暂不对 分配给工人w,工人需要前往1所在地点领取任 任务和工人进行分配，而是设置一个时间窗，在 务并送达c1。在工人w1前往领取任务的过程中， 时间窗内出现的全部对象进行整体的合理匹配。 任务2以及其所对应的任务执行地点c2出现。 众包任务、众包工人以及任务执行地点都有自己 在一定时间窗内，系统判断如果工人w,在领取了 对应的属性信息，包括地理位置，通过地理位置 任务后，再前往领取任务2，之后再送达也可以 可以计算出各个对象之间的距离，假设所有的众 满足时间约束的条件。那么系统会在保证先领取 包工人具有同等的技术水平，包括行进速度以及 任务后执行的前提下，在t、2、c、c2几个对象之
∑ |w| i=1 Couplewti ≈ |T| |W| (5) WTi n R Couplewt w t Couplewt Couplewt C 式中： 为每个工人完成所有被分配任务所耗 费的时间； 为完成的任务数； 为完成所有任务 的平均耗费时间； 是一个匹配参数，当工 人 和任务 匹配成功并且完成时间早于任务的 截止时间并且距离范围符合要求时，则任务完 成， =1，否则视为任务未完成， =0。 为任务完成数量，希望尽可能地完成所有任务， 同时满足以下约束条件： 1) 每个任务都有最后的结束时间，要求工人 必须在任务结束前将任务带到任务执行地点并完 成任务，假设工人们的技术水平相同，并且任务 到达任务执行地点便视为任务完成，如式 (3) 所示。 t c 2) 任务完成具有先后顺序，必须先领取任 务，才能将任务带到执行地点，未领取任务之前 便到达任务执行地点则不能视为任务完成，即式 (4) 中工人领取任务的时间必须早于工人到达任 务 对应的地点 的时间。 w W T 3) 同一个工人执行的任务数不可过多，为保 证总体的执行时间较少，在保证时间约束和总路 程最小化的前提下，将任务平均地分配给工人， 使得每个工人都能凭劳动力获得报酬。如式 (5) 所示，等号左边为工人 完成任务的数量， | |和| |分别为该地区工人和任务的总数。 4) 众包任务、工人以及任务执行地点要求在 一定的区域范围内，距离过远的对象将不能进行 任务分配，如式 (3) 所示。 例 1 描述了任务分配的执行过程。 t1、t2、t3 w1 w2 c1、c2、c3 例 1 假设众包工作环境中有 3 个众包任务 ，2 个众包工人 和 ，以及每个众包任 务所对应的任务地点 ，它们的位置如图 1 所示，每个点的信息如表 1 所示。众包工人和众 包任务随机散落在各个位置，当有任务出现的时 候，其所对应的执行地点也会相应地出现，此时 首先出现的任务就会分配给符合条件的工人去执 行，工人需要前往任务地点领取任务，随后再前 往任务对应的执行地点完成任务。在对象出现的 过程中，一般会进行两种决策过程：第 1 种是直接 将任务分配给最近的众包工人；第 2 种是暂不对 任务和工人进行分配，而是设置一个时间窗，在 时间窗内出现的全部对象进行整体的合理匹配。 众包任务、众包工人以及任务执行地点都有自己 对应的属性信息，包括地理位置，通过地理位置 可以计算出各个对象之间的距离，假设所有的众 包工人具有同等的技术水平，包括行进速度以及 任务的执行速度都是相同的，可以通过计算完成 所有任务的总路程，来换算出执行完成所有任务 的平均时间，优化的最终目标就是最小化平均任 务执行时间。 t1 t2 t3 c1 c2 c3 w1 w2 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 0 相对距离/km 相对距离/km 图 1 任务、工人和任务执行地点位置示意 Fig. 1 Locations of tasks,workers, and customers 表 1 任务、工人和任务执行地点信息表 Table 1 Information of tasks,workers, and customers 对象 坐标/km 报酬 服务质量 t1 (3.1,8.7) 1 t2 (5.5,4.7) 1 t3 (2.8,2.3) 1 c1 (10.0,9.7) c2 (7.7,6.0) c3 (6.1,1.4) w1 (4.6,9.5) 0.635 153 w2 (1.5,4.0) 0.469 222 由于问题的背景为动态情景，为了避免出现 局部最优的情况，设置了时间窗，即在一定的时 间段内，该时间段出现的 3 类对象的所有信息都 是可知的。众包工人和众包任务随机散落在各个 位置，当有任务出现的时候，其所对应的执行地 点也会相应地出现，此时首先出现的任务就会分 配给符合条件的工人。 w1 t1 c1 w1 t1 c1 w1 t2 c2 w1 t1 t2 t1 t2 c1 c2 假设工人 首先上班，此时任务 出现，其 所对应的任务执行地点 同时出现，系统将任务 分配给工人 ，工人需要前往 所在地点领取任 务并送达 。在工人 前往领取任务的过程中， 任务 以及其所对应的任务执行地点 出现。 在一定时间窗内，系统判断如果工人 在领取了 任务 后，再前往领取任务 ，之后再送达也可以 满足时间约束的条件。那么系统会在保证先领取 任务后执行的前提下，在 、 、 、 几个对象之 ·1042· 智 能 系 统 学 报 第 15 卷
第6期 潘庆先，等：基于禁忌搜索的时空众包任务分配算法 ·1043· 间合理安排一个总距离最短的线路顺序，从而使 前解m继续搜索，假如邻域搜索过程中只有比当 工人在最短的时间内完成更多的任务，同时行驶 前解更优的解才能被接受，搜索过程便可能陷入 最短的路程；在任务2出现后，工人w2以及任务 死循环和局部最优。为避免以上情况的发生，设 :和其所对应的任务执行地点c3出现。假设所有 计禁忌表(Tabu List),来存放刚刚进行过的移动， 的对象都出现在同一时间窗内，根据条件属性判 禁忌表的长度T需要提前设定，这些移动称作禁 断，如果工人w1再前去领取任务3，会超出前面 忌移动(Tabu Move)。对于当前的移动，在以后的 所领取任务的时间约束，而工人w?2更加符合分配 T次搜索过程便不再选取，以避免陷入死循环，T 条件，那么系统会将任务分配给工人2。从而 次以后释放该移动。禁忌表在搜索过程中会不 使得在一定时间窗内，完成所有任务所耗费的平 断修改，使得禁忌表始终保存着T个移动。虽 均任务完成时间最小化。 然设置了禁忌表，禁忌搜索算法仍有可能出现死 2.2问题复杂性 循环。因此必须设置停止条件，当算法无法找到 禁忌搜索算法被广泛地用来解决组合优化问 更好的解或者一个最优解反复出现的时候则算法 题，如调度问题、TSP问题等。在此用组合优化 停止。 的思想来简单介绍禁忌搜索算法的计算复杂度。 3.2基于随机阈值的禁忌搜索算法 对于n元素的置换问题，其所有排列状态数为n 算法输人迭代次数、禁忌搜索次数、禁忌表 的阶乘，当n较大时搜索空间的大小将变得非常 长度、循环次数以及工人集、任务集和地点集。 庞大，禁忌搜索则避免对所有的解空间进行搜 索，仅通过搜索少量的空间来得到近似最优的结 为了提高搜索效率，采用贪婪的策略获取初始 解，将总体迭代次数设置为100次，禁忌表的长度 果，但是用禁忌搜索算法来解决3类对象任务分 配问题仍然需要大量的计算。 设置为10，输入任务集、工人集和地点集合。得 到初始解后，进行下一步移动，迭代次数用来控 3 解决方案 制邻域搜索的次数，当所有任务都被分配后，迭 代结束。将获取的局部最优解与禁忌表中的解进 本文提出禁忌搜索算法与自适应阈值算法 相结合的方法来解决基于路径规划的时空众包 行对比，如果表中不存在，则填入禁忌表中，当禁 任务分配问题，首先分别对两种算法进行简单的 忌表的长度达到10时，将表中的第一个解去掉， 介绍。 反复进行上述过程，在算法迭代100次后输出最 优候选集，输出的结果为三类对象的顺序集合以 3.1禁忌搜索算法 禁忌搜索算法是在局部邻域搜索算法的基础 及最小的总时间耗费。 上发展而来的，它的特点是采用了“禁忌表”的概 对于众包工人的任务完成质量以及众包任务 念，利用了人类短时记忆的特点，从而避免重复 的预计等待时间，我们希望通过在线学习的方式 性搜索，所谓禁忌0就是防止重复之前已经进行 训练出最理想的数值，在本小节借鉴自适应阈值 的工作，避免算法陷入局部最优，将搜索过程中 的算法思想，来对工人服务质量进行设计。 出现的局部最优点记录在禁忌表中，在之后的搜 质量控制是众包中的一个核心问题24，众包 索过程中，禁忌表中存在的信息便不再搜索，这 工人初始都具有自己的服务质量属性，但是这个 样便可以跳出局部最优点。 属性不是一成不变的，工人在完成任务过程中的 禁忌搜索算法在最大车辆路径问题中应用较 表现，将会影响他们的服务质量：在规定的时间 多。刘霞等四对禁忌搜索算法进行了改进，并通 内更快地完成任务，工人的服务质量将获得提 过一些典型的算法对最大最小车辆路径问题进行 升，而不能在规定的时间内完成任务将受到差 了研究；对车辆路径静态子问题，提出了蚁群算法四。 评，工人的服务质量将会相应地降低，虽然工人 为求解带时间窗和多配送人员的车辆路径问题， 服务质量不会影响单个任务的报酬，但在任务分 苏欣欣等1对该问题进行了数学建模，并用禁忌 配过程中，在相似距离的条件下，系统将会优先 搜索算法来求解。 把任务分配给服务质量更高的工人。 对于组合优化问题min f(x)xeX,首先通过贪 AWT, X 8 (6) 婪的计算方式得到初始解s,定义m(x)为初始解 s的邻域移动集，然后从该集合中挑选一个移动 式(6)用来计算每次完成任务后，工人w的 m∈m(x),如果该移动能够得到更优的解，便从当 服务质量变化，其中EWT,表示任务的预计等待
t2 w2 t3 c3 w1 t3 w2 t3 w2 间合理安排一个总距离最短的线路顺序，从而使 工人在最短的时间内完成更多的任务，同时行驶 最短的路程；在任务 出现后，工人 以及任务 和其所对应的任务执行地点 出现。假设所有 的对象都出现在同一时间窗内，根据条件属性判 断，如果工人 再前去领取任务 ，会超出前面 所领取任务的时间约束，而工人 更加符合分配 条件，那么系统会将任务 分配给工人 。从而 使得在一定时间窗内，完成所有任务所耗费的平 均任务完成时间最小化。 2.2 问题复杂性 n n n 禁忌搜索算法被广泛地用来解决组合优化问 题，如调度问题、TSP 问题等。在此用组合优化 的思想来简单介绍禁忌搜索算法的计算复杂度。 对于 元素的置换问题，其所有排列状态数为 的阶乘，当 较大时搜索空间的大小将变得非常 庞大，禁忌搜索则避免对所有的解空间进行搜 索，仅通过搜索少量的空间来得到近似最优的结 果，但是用禁忌搜索算法来解决 3 类对象任务分 配问题仍然需要大量的计算。 3 解决方案 本文提出禁忌搜索算法与自适应阈值算法 相结合的方法来解决基于路径规划的时空众包 任务分配问题，首先分别对两种算法进行简单的 介绍。 3.1 禁忌搜索算法 禁忌搜索算法是在局部邻域搜索算法的基础 上发展而来的，它的特点是采用了“禁忌表”的概 念，利用了人类短时记忆的特点，从而避免重复 性搜索，所谓禁忌[20] 就是防止重复之前已经进行 的工作，避免算法陷入局部最优，将搜索过程中 出现的局部最优点记录在禁忌表中，在之后的搜 索过程中，禁忌表中存在的信息便不再搜索，这 样便可以跳出局部最优点。 禁忌搜索算法在最大车辆路径问题中应用较 多。刘霞等[21] 对禁忌搜索算法进行了改进，并通 过一些典型的算法对最大最小车辆路径问题进行 了研究；对车辆路径静态子问题，提出了蚁群算法[22]。 为求解带时间窗和多配送人员的车辆路径问题， 苏欣欣等[23] 对该问题进行了数学建模，并用禁忌 搜索算法来求解。 min f(x)|x ∈ X s m(x) s m ∈ m(x) 对于组合优化问题 ，首先通过贪 婪的计算方式得到初始解 ，定义 为初始解 的邻域移动集，然后从该集合中挑选一个移动 ，如果该移动能够得到更优的解，便从当 m ′ T T T T 前解 继续搜索，假如邻域搜索过程中只有比当 前解更优的解才能被接受，搜索过程便可能陷入 死循环和局部最优。为避免以上情况的发生，设 计禁忌表 (Tabu List)，来存放刚刚进行过的移动， 禁忌表的长度 需要提前设定，这些移动称作禁 忌移动 (Tabu Move)。对于当前的移动，在以后的 次搜索过程便不再选取，以避免陷入死循环， 次以后释放该移动。禁忌表在搜索过程中会不 断修改，使得禁忌表始终保存着 个移动。虽 然设置了禁忌表，禁忌搜索算法仍有可能出现死 循环。因此必须设置停止条件，当算法无法找到 更好的解或者一个最优解反复出现的时候则算法 停止。 3.2 基于随机阈值的禁忌搜索算法 算法输入迭代次数、禁忌搜索次数、禁忌表 长度、循环次数以及工人集、任务集和地点集。 为了提高搜索效率，采用贪婪的策略获取初始 解，将总体迭代次数设置为 100 次，禁忌表的长度 设置为 10，输入任务集、工人集和地点集合。得 到初始解后，进行下一步移动，迭代次数用来控 制邻域搜索的次数，当所有任务都被分配后，迭 代结束。将获取的局部最优解与禁忌表中的解进 行对比，如果表中不存在，则填入禁忌表中，当禁 忌表的长度达到 10 时，将表中的第一个解去掉， 反复进行上述过程，在算法迭代 100 次后输出最 优候选集，输出的结果为三类对象的顺序集合以 及最小的总时间耗费。 对于众包工人的任务完成质量以及众包任务 的预计等待时间，我们希望通过在线学习的方式 训练出最理想的数值，在本小节借鉴自适应阈值 的算法思想，来对工人服务质量进行设计。 质量控制是众包中的一个核心问题[24] ，众包 工人初始都具有自己的服务质量属性，但是这个 属性不是一成不变的，工人在完成任务过程中的 表现，将会影响他们的服务质量：在规定的时间 内更快地完成任务，工人的服务质量将获得提 升，而不能在规定的时间内完成任务将受到差 评，工人的服务质量将会相应地降低，虽然工人 服务质量不会影响单个任务的报酬，但在任务分 配过程中，在相似距离的条件下，系统将会优先 把任务分配给服务质量更高的工人。 qw = qw + ( 1− AWTt EWTt ) ×ε (6) w EWTt 式 (6) 用来计算每次完成任务后，工人 的 服务质量变化，其中 表示任务的预计等待 第 6 期 潘庆先，等：基于禁忌搜索的时空众包任务分配算法 ·1043·
·1044· 智能系统学报 第15卷 时间，AWT,表示完成任务所耗费的时间，ε是一 示。当工人数量较多的时候，每个工人分配到的 个调整系数，设置大小为0.001。当EWT,≥AWT, 任务数较少，任务可以更早完成：当工人数量较 时，表示任务完成，通过式(6)直接进行工人的服 少时，每个工人将分配更多任务，导致一定数量 务质量变化。当EWT,<AWT,表示工人没有按 的任务较迟执行。其中a和B为调整系数，α设 时完成任务，分别按照超时和未完成任务给予不 置为5，B设置为0.3，用以控制计算结果的数值大 同程度服务质量的扣除。 小。当预计等待时间接近dist(L,)/mw时，工人必 须前往执行该任务，为工人的行驶速度，统一 设置为30。 i=1 σ= (7) 4实验分析 通过式（⑦）计算出一个阈值，每个工人必须大 于该阈值才能参与任务分配。式(7)中的9：为工 4.1实验设置 人w:的服务质量，通过求出当前区域所有工人的 实验环境：处理器为AMD Athlon(tm)Quad- 平均服务质量并适当调整，使得服务质量不够理 Core Processor2.79GHz,内存容量为8GB,Win- 想的工人也能被允许参与任务分配，同时剔除服 dows7操作系统，编程语言为Python3.7。 务质量过低的工人。 为验证本文算法的有效性，从时空众包平台 gMission2获取了8000条记录，并在此数据的基 Pi=Px(1+)(cost-cost/cost (8) 础上进行了模拟数据的实验。该数据集包括工 阈值的自适应变化过程具体如下：0从0.10、 人、任务和任务对应地点3部分数据组成，每一 0.12、0.14、0.16、0.18、0.20六个值中以每个值对 个对象用一列数据表示，所包含的属性包括该对 应的概率P:进行选取，每个值的初始概率相等， 象出现的时间、截止的时间、对象所在的地理坐 并且和为1。当出现新的move时，按概率随机选 标、可匹配的半径范围以及每个对象所特有的属 取O的值并计算阈值σ，同时计算当前move的时 性，例如：任务有其所对应的报酬，而工人具有服 间耗费cost。通过历史实验得出单个move的最 务质量的属性。将任务、工人以及任务对应的执 大cost不会超过300，因此设置COStmax为300。通 行地点映射在100×100的网格中，对象的位置以 过式(8)对被选取的0值的概率进行更新，其他值 二维坐标表示。 被选取的概率相应变小。设置t=0.01用以调整 本实验从多方面与基于统计预测的自适应阈 数值大小。 值算法(ASPT)、自适应随机阈值算法(Adaptive 不同的任务由于与所分配工人的距离不同， RT)o进行比较。 所以预计等待完成的时间也不相同，每个任务在 4.2实验结果 分配的时候都要计算出一个预计等待时间，工人 4.2.1改变工人数、任务数 要求在这个预计等待时间内完成任务。预计等待 在本组实验中，通过改变工人和任务的数量， 时间过长，则工人的效率就会降低，总体所耗费 对比3个算法在任务的行驶的总路程、平均耗费 的时间便会增加，并影响到最终的优化目标；如 的时间以及匹配数3个方面的对比情况，设置工 果预计等待时间过短，那么工.人便无法在短时间 人数分别为10、20、30，实验结果分别如表2~4 内同时执行多个任务，工人不能顺路接取任务， 所示。 也会造成一定的时间浪费，同样无法达到优化平 表2为3个算法的任务总行驶距离的对比结 均任务完成时间的目的，所以预计等待时间的选 果。从表中可以看出，随着任务数的增加，3个算 取需要经过认真考虑。 法的总行驶距离都在不断增加。随着工人数量的 EWT=ITI Fj而×a+[dist.)+dist0,l月×B(9) 增加，总行驶距离随之增加，当工人数量为30人 时，3个算法的行驶总距离趋于稳定或者有所下 预计等待时间的计算式(9)所示，影响预计等 降，这是因为当工人数较多时，本文所提算法能 待时间的因素包括任务与地点之间的距离以及任 够进行更广泛的候选项搜索，并得出行驶总路径 务与工人之间的距离，当这两个距离过长时，意 较少的结果，而Adaptive RT算法和ASPT算法较 味着工人耗费在路程上的时间更多，需要更多的 多地考虑匹配对象之间的距离和效用是否满足阈 时间来执行该任务。另一个影响因素是当前区域 值，因此匹配约束较多。 工人密度，本文使用任务数与工人数的比值来表 表3和表4分别为算法的平均耗费时间和匹
AWTt ε EWTt ⩾ AWTt EWTt < AWTt 时间， 表示完成任务所耗费的时间， 是一 个调整系数，设置大小为 0.001。当 时，表示任务完成，通过式（6）直接进行工人的服 务质量变化。当 ，表示工人没有按 时完成任务，分别按照超时和未完成任务给予不 同程度服务质量的扣除。 σ = ∑ |W| i=1 qi |W| −θ (7) qi wi 通过式 (7) 计算出一个阈值，每个工人必须大 于该阈值才能参与任务分配。式（7）中的 为工 人 的服务质量，通过求出当前区域所有工人的 平均服务质量并适当调整，使得服务质量不够理 想的工人也能被允许参与任务分配，同时剔除服 务质量过低的工人。 Pi = Pi ×(1+τ) (costmax−cost)/costmax (8) θ Pi move θ σ move cost move cost costmax θ τ 阈值的自适应变化过程具体如下： 从 0.10、 0.12、0.14、0.16、0.18、0.20 六个值中以每个值对 应的概率 进行选取，每个值的初始概率相等， 并且和为 1。当出现新的 时，按概率随机选 取 的值并计算阈值 ，同时计算当前 的时 间耗费 。通过历史实验得出单个 的最 大 不会超过 300，因此设置 为 300。通 过式 (8) 对被选取的 值的概率进行更新，其他值 被选取的概率相应变小。设置 =0.01 用以调整 数值大小。 不同的任务由于与所分配工人的距离不同， 所以预计等待完成的时间也不相同，每个任务在 分配的时候都要计算出一个预计等待时间，工人 要求在这个预计等待时间内完成任务。预计等待 时间过长，则工人的效率就会降低，总体所耗费 的时间便会增加，并影响到最终的优化目标；如 果预计等待时间过短，那么工人便无法在短时间 内同时执行多个任务，工人不能顺路接取任务， 也会造成一定的时间浪费，同样无法达到优化平 均任务完成时间的目的，所以预计等待时间的选 取需要经过认真考虑。 EWTi = |T| |W| ×α+[dist(lt ,lc)+dist(lt ,lw)]×β (9) 预计等待时间的计算式 (9) 所示，影响预计等 待时间的因素包括任务与地点之间的距离以及任 务与工人之间的距离，当这两个距离过长时，意 味着工人耗费在路程上的时间更多，需要更多的 时间来执行该任务。另一个影响因素是当前区域 工人密度，本文使用任务数与工人数的比值来表 α β α β dist(lw,lt)/vw vw 示。当工人数量较多的时候，每个工人分配到的 任务数较少，任务可以更早完成；当工人数量较 少时，每个工人将分配更多任务，导致一定数量 的任务较迟执行。其中 和 为调整系数， 设 置为 5， 设置为 0.3，用以控制计算结果的数值大 小。当预计等待时间接近 时，工人必 须前往执行该任务， 为工人的行驶速度，统一 设置为 30。 4 实验分析 4.1 实验设置 实验环境：处理器为 AMD Athlon(tm) QuadCore Processor 2.79 GHz，内存容量为 8 GB，Windows 7 操作系统，编程语言 为 Python3.7。 为验证本文算法的有效性，从时空众包平台 gMission[25] 获取了 8 000 条记录，并在此数据的基 础上进行了模拟数据的实验。该数据集包括工 人、任务和任务对应地点 3 部分数据组成，每一 个对象用一列数据表示，所包含的属性包括该对 象出现的时间、截止的时间、对象所在的地理坐 标、可匹配的半径范围以及每个对象所特有的属 性，例如：任务有其所对应的报酬，而工人具有服 务质量的属性。将任务、工人以及任务对应的执 行地点映射在 100×100 的网格中，对象的位置以 二维坐标表示。 本实验从多方面与基于统计预测的自适应阈 值算法 (ASPT)[11] 、自适应随机阈值算法 (Adaptive RT)[10] 进行比较。 4.2 实验结果 4.2.1 改变工人数、任务数 在本组实验中，通过改变工人和任务的数量， 对比 3 个算法在任务的行驶的总路程、平均耗费 的时间以及匹配数 3 个方面的对比情况，设置工 人数分别为 10、20、30，实验结果分别如表 2~4 所示。 表 2 为 3 个算法的任务总行驶距离的对比结 果。从表中可以看出，随着任务数的增加，3 个算 法的总行驶距离都在不断增加。随着工人数量的 增加，总行驶距离随之增加，当工人数量为 30 人 时，3 个算法的行驶总距离趋于稳定或者有所下 降，这是因为当工人数较多时，本文所提算法能 够进行更广泛的候选项搜索，并得出行驶总路径 较少的结果，而 Adaptive RT 算法和 ASPT 算法较 多地考虑匹配对象之间的距离和效用是否满足阈 值，因此匹配约束较多。 表 3 和表 4 分别为算法的平均耗费时间和匹 ·1044· 智 能 系 统 学 报 第 15 卷
第6期 潘庆先，等：基于禁忌搜索的时空众包任务分配算法 ·1045· 配数的对比结果。从表中可以看出：随着任务数 断增加的：随着工人数量的增加，平均耗费的时 增加，3个算法的平均耗费时间和匹配数都是不 间是不断减少的。 表23种算法在行驶总距离的对比结果 Table 2 Comparison results of the three algorithms in terms of the total distance traveled km 禁忌搜索算法 自适应随机阈值算法 统计预测算法 任务数量 10 20 30 10 20 30 10 20 30 30 2738 3645 2805 2958 3306 3306 3756 3805 3787 50 4842 4852 3862 3705 4389 4423 6917 6829 6895 80 7844 7278 5697 6762 8006 7969 10653 10359 9987 100 9856 9965 9908 9035 10312 10371 12914 12749 12787 200 20391 21310 20458 19764 22985 21995 27228 26907 27026 表33种算法在平均耗费时间的对比结果 Table 3 Comparison results of the three algorithms in terms of the average time consumption 禁忌搜索算法 自适应随机阈值算法 统计预测算法 任务数量 10 20 30 10 20 30 10 20 30 30 91.26 60.75 31 140.857 122.4 122.4 197.3 167.31 135.9 50 161.4 80.86 42.5 154.375 146.3 153.3 230.567 226.81 167.34 80 261.467 121.3 63.3 281.75 242.6 197.2 339.86 270.6 233.7 100 328.533 161.1 110.9 376.458 289.5 214.2 457.24 382.8 311.76 200 679.7 338.5 227.3 823.5 582.4 261.84 887.23 698.23 617.3 表43种算法在匹配数的对比结果 Table 4 Comparison results of the three algorithms in terms of the number of allocations 个 禁忌搜索算法 自适应随机阈值算法 统计预测算法 任务数量 10 20 30 10 20 30 10 20 30 29 30 30 25 28 28 25 27 28 50 50 50 50 41 46 46 40 43 45 80 79 呢 65 76 76 65 74 76 100 98 100 100 84 94 95 83 91 96 200 197 200 200 171 194 192 165 192 194 由于本文算法目标是优化平均任务执行时 效果。 间，因此希望更多的工人参与，为此本文设定了 4.2.2半径对比 工作质量阈值，目的是使略微低于平均工作质 设置工人数量为20，任务数量为50，通过改 量的工人能够在保证整体任务完成质量的前提 变任务和工人的有效半径，对比3种算法在任务 下也能参与进来，从而增加工人数量。因此本 的分配数、耗费的总时间以及行驶的总路程几个 文算法在匹配数和平均耗时方面取得了较好的 方面的情况，实验结果如图2~4所示
配数的对比结果。从表中可以看出：随着任务数 增加，3 个算法的平均耗费时间和匹配数都是不 断增加的；随着工人数量的增加，平均耗费的时 间是不断减少的。 表 2 3 种算法在行驶总距离的对比结果 Table 2 Comparison results of the three algorithms in terms of the total distance traveled km 任务数量 禁忌搜索算法 自适应随机阈值算法 统计预测算法 10 20 30 10 20 30 10 20 30 30 2 738 3 645 2 805 2958 3306 3 306 3 756 3 805 3 787 50 4 842 4 852 3 862 3705 4389 4 423 6 917 6 829 6 895 80 7 844 7 278 5 697 6762 8006 7 969 10 653 10 359 9 987 100 9 856 9 965 9 908 9035 10312 10 371 12 914 12 749 12 787 200 20 391 21 310 20 458 19764 22985 21 995 27 228 26 907 27 026 表 3 3 种算法在平均耗费时间的对比结果 Table 3 Comparison results of the three algorithms in terms of the average time consumption s 任务数量 禁忌搜索算法 自适应随机阈值算法 统计预测算法 10 20 30 10 20 30 10 20 30 30 91.26 60.75 31 140.857 122.4 122.4 197.3 167.31 135.9 50 161.4 80.86 42.5 154.375 146.3 153.3 230.567 226.81 167.34 80 261.467 121.3 63.3 281.75 242.6 197.2 339.86 270.6 233.7 100 328.533 161.1 110.9 376.458 289.5 214.2 457.24 382.8 311.76 200 679.7 338.5 227.3 823.5 582.4 261.84 887.23 698.23 617.3 表 4 3 种算法在匹配数的对比结果 Table 4 Comparison results of the three algorithms in terms of the number of allocations 个 任务数量 禁忌搜索算法 自适应随机阈值算法 统计预测算法 10 20 30 10 20 30 10 20 30 30 29 30 30 25 28 28 25 27 28 50 50 50 50 41 46 46 40 43 45 80 79 80 80 65 76 76 65 74 76 100 98 100 100 84 94 95 83 91 96 200 197 200 200 171 194 192 165 192 194 由于本文算法目标是优化平均任务执行时 间，因此希望更多的工人参与，为此本文设定了 工作质量阈值，目的是使略微低于平均工作质 量的工人能够在保证整体任务完成质量的前提 下也能参与进来，从而增加工人数量。因此本 文算法在匹配数和平均耗时方面取得了较好的 效果。 4.2.2 半径对比 设置工人数量为 20，任务数量为 50，通过改 变任务和工人的有效半径，对比 3 种算法在任务 的分配数、耗费的总时间以及行驶的总路程几个 方面的情况，实验结果如图 2~4 所示。 第 6 期 潘庆先，等：基于禁忌搜索的时空众包任务分配算法 ·1045·
·1046· 智能系统学报 第15卷 200 oASPT 人数量增加提高了算法邻域搜索的多样性，总行 175 x-Tabu-Search 驶距离有小幅度减少。 150 *Adaptive RT 从上述实验可以看出，工人和任务有效半径 125 100 的大小对ASPT算法和Adaptive RT算法具有较 75 大的影响，对本文所提算法的影响较小，原因是 50 本文算法更多地考虑时间约束，并且追求匹配 25 数量的优化，同时禁忌搜索算法本身的搜索优 化能力较强，能够在相同条件下产生更多的有 0.5 1.01.52.02.53.0 半径/km 效匹配。 图23种算法在半径变化时平均耗费时间的对比结果 4.2.3参数设置 Fig.2 Comparison of the average calculation time-consuming 在计算预计等待时间时，设置α的值等于图5 results of the three algorithms when the radius changes 中的横坐标的10倍，B的值等于横坐标，通过对 比实验确定在α=5和B=0.3时优化效果最好，但 整体变化幅度较小。 通过对比试验可以看出，改进后的禁忌搜索 算法在行驶的总距离、耗费的平均时间以及对象 的匹配数等方面都取得了相比于ASPT和Adapt- ive RT算法更理想的效果：本文所提算法在任务 o-ASPT x-Tabu-Search 耗费时间上平均比Adaptive RT算法降低I3%, Adaptive RT 比ASPT算法降低23.3%。在移动成本上比Ad- 0.5 1.01.52.02.53.0 aptive RT算法降低了6.99%，比ASPT算法降低 半径/km 了25.9%。但是在算法的运行时间方面，本文所 图33种算法在半径变化时总行驶路程的对比结果 提算法具有较高的复杂度，运行时间较长，需要 Fig.3 Comparison of the total distance of the three al- gorithms when the radius changes 进行改进。 95 60 50 0 93 30 92 20 oASPT 91 10 Tabu-Search Adaptive RT 90 0 0.1 0.20.30.40.50.60.70.8 0.5 1.01.52.02.53.0 a和B数值 半径km 图5a和B的变化对比结果 图43种算法在半径变化时分配数的对比结果 Fig.5 Comparison result of the changes in a and B Fig.4 Comparison results of the allocation numbers of the three algorithms when the radius changes 5 结束语 从图2和图4可以看出，ASPT算法的平均耗 费时间是在不断增加的，在半径为2km时达到 本文提出了众包工人需要携带任务到指定 最佳匹配数。Adaptive RT算法同样在半径为 地点完成的工作模式，首次考虑了三类对象条件 2km时达到最佳匹配数，由于工人数量充足，在 下众包工人的路径规划问题和移动成本问题；将 半径为3km时得到了更少的平均时间耗费。从图3 空间上的距离成本换算成时间成本，分析了时间 和图4可以看出由于工人数量增加，在半径为 约束对任务分配过程的影响，提出了基于自适应 1km时ASPT和Adaptive RT算法的匹配数都更 阈值的禁忌搜索算法，并通过在线学习的方式， 多一些，因此在总行驶路程上有了一定的增加。 计算出每个任务合理的预估等待时间，通过合理 而本文所提算法由于已达到最大任务数，并且工 的匹配使得区域内的众包任务能在最短的时间
200 175 150 125 100 75 50 25 0 0.5 1.0 1.5 2.0 2.5 3.0 平均耗费时间/min 半径/km ASPT Tabu-Search Adaptive RT 图 2 3 种算法在半径变化时平均耗费时间的对比结果 Fig. 2 Comparison of the average calculation time-consuming results of the three algorithms when the radius changes ASPT Tabu-Search Adaptive RT 6 7 5 4 3 2 1 0 行驶总路程/km 0.5 1.0 1.5 2.0 2.5 3.0 半径/km 图 3 3 种算法在半径变化时总行驶路程的对比结果 Fig. 3 Comparison of the total distance of the three algorithms when the radius changes ASPT Tabu-Search Adaptive RT 60 50 40 30 20 10 0 分配数/pcs 0.5 1.0 1.5 2.0 2.5 3.0 半径/km 图 4 3 种算法在半径变化时分配数的对比结果 Fig. 4 Comparison results of the allocation numbers of the three algorithms when the radius changes 从图 2 和图 4 可以看出，ASPT 算法的平均耗 费时间是在不断增加的，在半径为 2 km 时达到 最佳匹配数。Adaptive RT 算法同样在半径为 2 km 时达到最佳匹配数，由于工人数量充足，在 半径为 3 km 时得到了更少的平均时间耗费。从图 3 和图 4 可以看出由于工人数量增加，在半径为 1 km 时 ASPT 和 Adaptive RT 算法的匹配数都更 多一些，因此在总行驶路程上有了一定的增加。 而本文所提算法由于已达到最大任务数，并且工 人数量增加提高了算法邻域搜索的多样性，总行 驶距离有小幅度减少。 从上述实验可以看出，工人和任务有效半径 的大小对 ASPT 算法和 Adaptive RT 算法具有较 大的影响，对本文所提算法的影响较小，原因是 本文算法更多地考虑时间约束，并且追求匹配 数量的优化，同时禁忌搜索算法本身的搜索优 化能力较强，能够在相同条件下产生更多的有 效匹配。 4.2.3 参数设置 α β α β 在计算预计等待时间时，设置 的值等于图 5 中的横坐标的 10 倍， 的值等于横坐标，通过对 比实验确定在 =5 和 =0.3 时优化效果最好，但 整体变化幅度较小。 通过对比试验可以看出，改进后的禁忌搜索 算法在行驶的总距离、耗费的平均时间以及对象 的匹配数等方面都取得了相比于 ASPT 和 Adaptive RT 算法更理想的效果:本文所提算法在任务 耗费时间上平均比 Adaptive RT 算法降低 13%， 比 ASPT 算法降低 23.3%。在移动成本上比 Adaptive RT 算法降低了 6.99%，比 ASPT 算法降低 了 25.9%。但是在算法的运行时间方面，本文所 提算法具有较高的复杂度，运行时间较长，需要 进行改进。 95 94 93 92 91 90 0 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.1 平均耗费时间/min α 和 β 数值 α β 图 5 α 和 β 的变化对比结果 Fig. 5 Comparison result of the changes in α and β 5 结束语 本文提出了众包工人需要携带任务到指定 地点完成的工作模式，首次考虑了三类对象条件 下众包工人的路径规划问题和移动成本问题；将 空间上的距离成本换算成时间成本，分析了时间 约束对任务分配过程的影响，提出了基于自适应 阈值的禁忌搜索算法，并通过在线学习的方式， 计算出每个任务合理的预估等待时间，通过合理 的匹配使得区域内的众包任务能在最短的时间 ·1046· 智 能 系 统 学 报 第 15 卷
第6期 潘庆先，等：基于禁忌搜索的时空众包任务分配算法 ·1047· 内得到分配。最后通过在真实数据集实验，验证 real-time reliable crowdsourcing[C]//2014 IEEE 34th Inter- 了该算法在降低任务分配时间、提高匹配效率上 national Conference on Distributed Computing Systems 具有高效性。在未来工作中，还要进行更多研究 (ICDCS).Madrid,Spain,2014:1-10. 来降低算法的复杂度。同时，我们将继续研究路 [10]宋天舒，童咏昕，王立斌，等.空间众包环境下的3类对 径规划中其他的经典算法，并将之应用到众包 象在线任务分配).软件学报，2017,28(3)：611-630. 领域。 SONG Tianshu,TONG Yongxin,WANG Libin,et al. 参考文献： Online task assignment for three types of objects under spatial crowdsourcing environment[J].Journal of soft- [1]LAW E,VON AHN L.Human computation[J].Synthesis ware,2017,28(3):611-630. lectures on artificial intelligence and machine learning, [11]刘辉，李盛恩.时空众包环境下基于统计预测的自适应 2011,5(3):1-121. 阈值算法U.计算机应用，2018,38(2)415-420 [2]童咏昕，袁野，成雨蓉，等.时空众包数据管理技术研究 LIU Hui,LI Shengen.Adaptive threshold algorithm based 综述[).软件学报，2017,28(1)：35-58 on statistical prediction under spatial crowdsourcing en- TONG Yongxin,YUAN Ye,CHENG Yurong,et al.Sur- vironment[J].Journal of computer applications,2018, vey on spatiotemporal crowdsourced data management 38(2:415-420 techniques[J].Journal of software,2017,28(1):35-58. [12]HASSAN UU,CURRY E.Efficient task assignment for [3]刘辉.时控众包环境下在线任务分配策略的研究D].济 spatial crowdsourcing:a combinatorial fractional optimiz- 南：山东建筑大学，2018. ation approach with semi-bandit learning[J].Expert sys- LIU Hui.Research of online task allocation strategy in spa- tio-temporal crowdsourcing environment[D].Jinan:Shan- tems with applications,2016,58:36-56. [13]GAREY M R,JOHNSON D S.Computers and intractab- dong Jianzhu University,2018. [4]KAZEMI L.SHAHABI C.Geocrowd:enabling query an- ility:a guide to the theory of NP-completeness[M].New swering with spatial crowdsourcing[C]/Proceedings of the York:W.H.Freeman Co.,1979:79-87 [14]DANTZIG G B,RAMSER J H.The truck dispatching 20th International Conference on Advances in Geographic Information Systems.Redondo Beach,USA,2012: problem[J].Management science,1959,6(1):80-91 189-199 [15]毕国通.车辆路径问题及其优化算法研究综述)物流 [5]TONG Yongxin,SHE Jieying,DING Bolin,et al.Online 科技，2016,39(6)：95-97 mobile micro-task allocation in spatial crowdsourcing[C]// BI Guotong.The review of vehicle routing problem and 2016 IEEE 32nd International Conference on Data Engin- its optimization algorithm[J].Logistics sci-tech,2016. eering (ICDE).Helsinki,Finland.2016:49-60 396):95-97 [6]LI Yu,YIU ML,XU Wenjian.Oriented online route re- [16]苏畅，徒君.一种自适应最大最小蚁群算法[.模式识 commendation for spatial crowdsourcing task workers[Cl// 别与人工智能2007,20(5)：688-691 Proceedings of the 14th International Symposium on Spa- SU Chang,TU Jun.An adaptive max-min ant colony al- tial and Temporal Databases.Hong Kong,China,2015: gorithm[J].Pattern recognition and artificial intelligence, 137-156. 2007.20(5:688-691. [7]LI Guoliang,WANG Jiannan,ZHENG Yudian,et al. [17]BAI Jie,YANG Genke,CHEN Yuwang,et al.A model Crowdsourced data management:a survey[J].IEEE trans- induced max-min ant colony optimization for asymmetric actions on knowledge and data engineering,2016,28(9): traveling salesman problem[J].Applied soft computing, 2296-2319 2013.13(3:1365-1375. [8]PAN Qingxian,DONG Hongbin,WANG Yingjie,et al. [18]YU Jiapeng,WANG Chengen.A max-min ant colony Recommendation of crowdsourcing tasks based on system for assembly sequence planning[J].The interna- word2vec semantic tags[J].Wireless communications and tional journal of advanced manufacturing technology, mobile computing,2019,2019:2121850. 2013.67(9/10/11/12):2819-2835 [9]BOUTSIS I,KALOGERAKI V.On task assignment for [19]REN Chunyu.Solving min-max vehicle routing
内得到分配。最后通过在真实数据集实验，验证 了该算法在降低任务分配时间、提高匹配效率上 具有高效性。在未来工作中，还要进行更多研究 来降低算法的复杂度。同时，我们将继续研究路 径规划中其他的经典算法，并将之应用到众包 领域。 参考文献： LAW E, VON AHN L. Human computation[J]. Synthesis lectures on artificial intelligence and machine learning, 2011, 5(3): 1–121. [1] 童咏昕, 袁野, 成雨蓉, 等. 时空众包数据管理技术研究 综述 [J]. 软件学报, 2017, 28(1): 35–58. TONG Yongxin, YUAN Ye, CHENG Yurong, et al. Survey on spatiotemporal crowdsourced data management techniques[J]. Journal of software, 2017, 28(1): 35–58. [2] 刘辉. 时空众包环境下在线任务分配策略的研究 [D]. 济 南: 山东建筑大学, 2018. LIU Hui. Research of online task allocation strategy in spatio-temporal crowdsourcing environment[D]. Jinan: Shandong Jianzhu University, 2018. [3] KAZEMI L, SHAHABI C. Geocrowd: enabling query answering with spatial crowdsourcing[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. Redondo Beach, USA, 2012: 189−199. [4] TONG Yongxin, SHE Jieying, DING Bolin, et al. Online mobile micro-task allocation in spatial crowdsourcing[C]// 2016 IEEE 32nd International Conference on Data Engineering (ICDE). Helsinki, Finland, 2016: 49−60. [5] LI Yu, YIU M L, XU Wenjian. Oriented online route recommendation for spatial crowdsourcing task workers[C]// Proceedings of the 14th International Symposium on Spatial and Temporal Databases. Hong Kong, China, 2015: 137−156. [6] LI Guoliang, WANG Jiannan, ZHENG Yudian, et al. Crowdsourced data management: a survey[J]. IEEE transactions on knowledge and data engineering, 2016, 28(9): 2296–2319. [7] PAN Qingxian, DONG Hongbin, WANG Yingjie, et al. Recommendation of crowdsourcing tasks based on word2vec semantic tags[J]. Wireless communications and mobile computing, 2019, 2019: 2121850. [8] [9] BOUTSIS I, KALOGERAKI V. On task assignment for real-time reliable crowdsourcing[C]//2014 IEEE 34th International Conference on Distributed Computing Systems (ICDCS). Madrid, Spain, 2014: 1−10. 宋天舒, 童咏昕, 王立斌, 等. 空间众包环境下的 3 类对 象在线任务分配 [J]. 软件学报, 2017, 28(3): 611–630. SONG Tianshu, TONG Yongxin, WANG Libin, et al. Online task assignment for three types of objects under spatial crowdsourcing environment[J]. Journal of software, 2017, 28(3): 611–630. [10] 刘辉, 李盛恩. 时空众包环境下基于统计预测的自适应 阈值算法 [J]. 计算机应用, 2018, 38(2): 415–420. LIU Hui, LI Shengen. Adaptive threshold algorithm based on statistical prediction under spatial crowdsourcing environment[J]. Journal of computer applications, 2018, 38(2): 415–420. [11] HASSAN U U, CURRY E. Efficient task assignment for spatial crowdsourcing: a combinatorial fractional optimization approach with semi-bandit learning[J]. Expert systems with applications, 2016, 58: 36–56. [12] GAREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M]. New York: W. H. Freeman & Co., 1979: 79−87. [13] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management science, 1959, 6(1): 80–91. [14] 毕国通. 车辆路径问题及其优化算法研究综述 [J]. 物流 科技, 2016, 39(6): 95–97. BI Guotong. The review of vehicle routing problem and its optimization algorithm[J]. Logistics sci-tech, 2016, 39(6): 95–97. [15] 苏畅, 徒君. 一种自适应最大最小蚁群算法 [J]. 模式识 别与人工智能, 2007, 20(5): 688–691. SU Chang, TU Jun. An adaptive max-min ant colony algorithm[J]. Pattern recognition and artificial intelligence, 2007, 20(5): 688–691. [16] BAI Jie, YANG Genke, CHEN Yuwang, et al. A model induced max-min ant colony optimization for asymmetric traveling salesman problem[J]. Applied soft computing, 2013, 13(3): 1365–1375. [17] YU Jiapeng, WANG Chengen. A max-min ant colony system for assembly sequence planning[J]. The international journal of advanced manufacturing technology, 2013, 67(9/10/11/12): 2819–2835. [18] [19] REN Chunyu. Solving min-max vehicle routing 第 6 期 潘庆先，等：基于禁忌搜索的时空众包任务分配算法 ·1047·
·1048· 智能系统学报 第15卷 problem[J].Journal of software,2011,6(9):1851-1856 spatio-temporal crowdsourcing[J].IEEE access,2019,7: [20]李阳，李文芳，马骊，等.混合退火算法求解旅行商问 170292-170303 题).计算机应用，2014,34S1):110-113. [25]CHEN Zhao,FU Rui,ZHAO Ziyuan,et al.gMission:a LI Yang,LI Wenfang,MA Li,et al.Hybrid annealing al- general spatial crowdsourcing platform[J].Proceedings of gorithm for solving travellling salesman problem[J]. the VLDB endowment,2014,7(13):1629-1632 Journal of computer applications,2014,34(S1):110-113. 作者简介： [21]刘霞，齐欢.最小-最大车辆路径问题的禁忌搜索算 潘庆先，副教授.博士研究生，主 法.系统工程，2007,25(1)：49-52. 要研究方向为人工智能和机器学习。 LIU Xia,QI Huan.Tabu search algorithm of min-max vehicle routing problems[J].Systems engineering,2007, 25(1:49-52. [22]刘霞，杨超.最小-最大车辆路径问题的蚁群算法几.解 放军理工大学学报（自然科学版），2012,13(3：336-341. 殷增轩，硕士研究生，主要研究方 LIU Xia,YANG Chao.Min-max vehicle routing prob- 向为人工智能和机器学习。 lem based on ant colony algorithm[J].Journal of PLA University of Science and Technology (Natural Science Edition),2012,13(3):336-341. [23]苏欣欣，秦虎，王恺.禁忌搜索算法求解带时间窗和多 配送人员的车辆路径问题.重庆师范大学学报（自然 董红斌，教授，博士生导师，博士， 科学版)，2020,371)：22-30. 中国计算机学会高级会员，主要研究 SU Xinxin,QIN Hu,WANG Kai.Tabu search algorithm 方向为机器学习、人工智能、多智能体 for the vehicle routing problem with time windows and 系统和数据挖掘。主持或参加国家级 和省部级项目5项，其中，国家级 multiple deliverymen[J].Journal of Chongqing Normal 3项，省级2项，曾获黑龙江省高校科 University (Natural Science Edition),2020,37(1):22-30. 学技术奖、黑龙江省优秀高等教育科 [24]PAN Qingxian,PAN Tingwei,DONG Hongbin,et al.An 学成果奖。发表学术论文90余篇，出版专著1部，主编教 online task assignment based on quality constraint for 材2部
problem[J]. Journal of software, 2011, 6(9): 1851–1856. 李阳, 李文芳, 马骊, 等. 混合退火算法求解旅行商问 题 [J]. 计算机应用, 2014, 34(S1): 110–113. LI Yang, LI Wenfang, MA Li, et al. Hybrid annealing algorithm for solving travellling salesman problem[J]. Journal of computer applications, 2014, 34(S1): 110–113. [20] 刘霞, 齐欢. 最小−最大车辆路径问题的禁忌搜索算 法 [J]. 系统工程, 2007, 25(1): 49–52. LIU Xia, QI Huan. Tabu search algorithm of min-max vehicle routing problems[J]. Systems engineering, 2007, 25(1): 49–52. [21] 刘霞, 杨超. 最小−最大车辆路径问题的蚁群算法 [J]. 解 放军理工大学学报(自然科学版), 2012, 13(3): 336–341. LIU Xia, YANG Chao. Min-max vehicle routing problem based on ant colony algorithm[J]. Journal of PLA University of Science and Technology (Natural Science Edition), 2012, 13(3): 336–341. [22] 苏欣欣, 秦虎, 王恺. 禁忌搜索算法求解带时间窗和多 配送人员的车辆路径问题 [J]. 重庆师范大学学报 (自然 科学版), 2020, 37(1): 22–30. SU Xinxin, QIN Hu, WANG Kai. Tabu search algorithm for the vehicle routing problem with time windows and multiple deliverymen[J]. Journal of Chongqing Normal University (Natural Science Edition), 2020, 37(1): 22–30. [23] PAN Qingxian, PAN Tingwei, DONG Hongbin, et al. An online task assignment based on quality constraint for [24] spatio-temporal crowdsourcing[J]. IEEE access, 2019, 7: 170292–170303. CHEN Zhao, FU Rui, ZHAO Ziyuan, et al. gMission: a general spatial crowdsourcing platform[J]. Proceedings of the VLDB endowment, 2014, 7(13): 1629 –1632. [25] 作者简介： 潘庆先，副教授，博士研究生，主 要研究方向为人工智能和机器学习。 殷增轩，硕士研究生，主要研究方 向为人工智能和机器学习。 董红斌，教授，博士生导师，博士， 中国计算机学会高级会员，主要研究 方向为机器学习、人工智能、多智能体 系统和数据挖掘。主持或参加国家级 和省部级项目 5 项，其中，国家级 3 项，省级 2 项，曾获黑龙江省高校科 学技术奖、黑龙江省优秀高等教育科 学成果奖。发表学术论文 90 余篇，出版专著 1 部，主编教 材 2 部。 ·1048· 智 能 系 统 学 报 第 15 卷