·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) Quad￾Core Processor 2.79 GHz，内存容量为 8 GB，Win￾dows 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 卷