随着移动互联网的飞速发展，众包任务^[1]开始出现时间上和空间上的约束，一种新型的众包模式——时空众包应运而生。VRP(vehicle route planning)路径规划是一个经典问题，其目的是寻找一条从起点到目标终点能满足各种时间、空间约束的行驶路线，与时空众包中的任务分配问题具有很多相似性，因此本文考虑将两者结合起来，以解决任务分配问题。

在现有的时空众包研究中，任务分配是最核心的研究问题之一^[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 基本定义

定义1　众包任务。众包任务定义为 $t = < {a_t}, $ $ {l_t}(x,y),{r_t},{p_t},{{d}}_{t},{\rm{I}}{{\rm{D}}_{{t}}} >$ ， ${a_t}$ 表示到达时刻， ${l_t}$ 表示位置，其中 $x$ 、 $y$ 分别为欧氏空间中的横、纵坐标， ${r_t}$ 表示范围， ${p_t}$ 为完成任务所获得的的报酬， ${d_t}$ 表示任务截止时间， ${\rm{I}}{{\rm{D}}_{{t}}}$ 表示任务对应的顾客，需要工人将任务送到任务对应地点执行。

定义2　众包工人。众包工人定义为 $w = < {a_w}, $ $ {l_w}(x,y),{r_w},{q_w} > $ ， ${a_w}$ 表示到达时间， ${l_w}$ 表示位置， ${r_w}$ 表示范围， ${q_w}$ 表示工人具有的评价值，作为工人任务完成质量的评估。

定义3　任务对应地点。任务对应地点定义为 $c = < {\rm{i}}{{\rm{d}}_{{c}}},{l_c}(x,y) >$ ，地点 $c$ 在任务 $t$ 到达的同时出现， ${\rm{i}}{{\rm{d}}_{{c}}}$ 对应任务的序号， ${l_c}$ 表示任务对应地点的位置。

定义4　任务分配问题。给定任务集 $T$ 、工人集 $W$ 和任务所对应的地点集 $C$ ，众包工人和众包任务随机动态出现，地点 $c$ 伴随着对应任务的出现而出现，求解的目标是找到一个任务 $t$ 、工人 $w$ 和地点 $c$ 的顺序集，在该顺序下，使得任务的平均分配时间最小化，式(1)和式(2)为优化的目标函数：

$ {\rm{Minavg}}(R) = \frac{{\displaystyle\sum\limits_{i = 1}^n {{\rm{W}}{{\rm{T}}_i}} }}{n} $

(1)

$ {\rm{Max}}C = \sum\limits_{i = 1}^n {{\rm{Coupl}}{{\rm{e}}_{{\rm{WT}}_{i}}}} $

(2)

$ {\rm{Coupl}}{{\rm{e}}_{{{wt}}}}=\left\{ \begin{array}{l} 0 \\ 1,\;\quad{\kern 1pt} {\rm{ a}}{{\rm{l}}_{wt}} < {d_t},{\rm{dist}}(w,t) <{\rm{min}}\left( { {r_w}\;{\rm{, }}\;{r_t}} \right) \\ \end{array} \right. $

(3)

$ {\rm{Arriv}}{{\rm{e}}_{{{wt}}}} < {\rm{Arriv}}{{\rm{e}}_{{\rm{wc}}}} $

(4)

$ \sum\limits_{i = 1}^{|w|} {{\rm{Coupl}}{{\rm{e}}_{{\rm{wt}}_i}} \approx \frac{{|T|}}{{|W|}}} $

(5)

式中： ${\rm{W}}{{\rm{T}}_{{i}}}$ 为每个工人完成所有被分配任务所耗费的时间； $n$ 为完成的任务数； $R$ 为完成所有任务的平均耗费时间； ${\rm{Coupl}}{{\rm{e}}_{{{wt}}}}$ 是一个匹配参数，当工人 $w$ 和任务 $t$ 匹配成功并且完成时间早于任务的截止时间并且距离范围符合要求时，则任务完成， ${\rm{Coupl}}{{\rm{e}}_{{{wt}}}}$ =1，否则视为任务未完成， ${\rm{Coupl}}{{\rm{e}}_{{{wt}}}}$ =0。 $C$ 为任务完成数量，希望尽可能地完成所有任务，同时满足以下约束条件：

1)每个任务都有最后的结束时间，要求工人必须在任务结束前将任务带到任务执行地点并完成任务，假设工人们的技术水平相同，并且任务到达任务执行地点便视为任务完成，如式(3)所示。

2)任务完成具有先后顺序，必须先领取任务，才能将任务带到执行地点，未领取任务之前便到达任务执行地点则不能视为任务完成，即式(4)中工人领取任务的时间必须早于工人到达任务 $t$ 对应的地点 $c$ 的时间。

3)同一个工人执行的任务数不可过多，为保证总体的执行时间较少，在保证时间约束和总路程最小化的前提下，将任务平均地分配给工人，使得每个工人都能凭劳动力获得报酬。如式(5)所示，等号左边为工人 ${\rm{w}}$ 完成任务的数量，| $W$ |和| $T$ |分别为该地区工人和任务的总数。

4)众包任务、工人以及任务执行地点要求在一定的区域范围内，距离过远的对象将不能进行任务分配，如式(3)所示。

例1描述了任务分配的执行过程。

例1　假设众包工作环境中有3个众包任务 ${t_1}{\text{、}} {t_2} {\text{、}} {t_3}$ ，2个众包工人 ${w_1}$ 和 ${w_2}$ ，以及每个众包任务所对应的任务地点 ${c_1} {\text{、}}{c_2}{\text{、}} {c_3}$ ，它们的位置如图1所示，每个点的信息如表1所示。众包工人和众包任务随机散落在各个位置，当有任务出现的时候，其所对应的执行地点也会相应地出现，此时首先出现的任务就会分配给符合条件的工人去执行，工人需要前往任务地点领取任务，随后再前往任务对应的执行地点完成任务。在对象出现的过程中，一般会进行两种决策过程：第1种是直接将任务分配给最近的众包工人；第2种是暂不对任务和工人进行分配，而是设置一个时间窗，在时间窗内出现的全部对象进行整体的合理匹配。众包任务、众包工人以及任务执行地点都有自己对应的属性信息，包括地理位置，通过地理位置可以计算出各个对象之间的距离，假设所有的众包工人具有同等的技术水平，包括行进速度以及任务的执行速度都是相同的，可以通过计算完成所有任务的总路程，来换算出执行完成所有任务的平均时间，优化的最终目标就是最小化平均任务执行时间。

由于问题的背景为动态情景，为了避免出现局部最优的情况，设置了时间窗，即在一定的时间段内，该时间段出现的3类对象的所有信息都是可知的。众包工人和众包任务随机散落在各个位置，当有任务出现的时候，其所对应的执行地点也会相应地出现，此时首先出现的任务就会分配给符合条件的工人。

假设工人 ${w_1}$ 首先上班，此时任务 ${t_1}$ 出现，其所对应的任务执行地点 ${c_1}$ 同时出现，系统将任务分配给工人 ${w_1}$ ，工人需要前往 ${t_1}$ 所在地点领取任务并送达 ${c_1}$ 。在工人 ${w_1}$ 前往领取任务的过程中，任务 ${t_2}$ 以及其所对应的任务执行地点 ${c_2}$ 出现。在一定时间窗内，系统判断如果工人 ${w_1}$ 在领取了任务 ${t_1}$ 后，再前往领取任务 ${t_2}$ ，之后再送达也可以满足时间约束的条件。那么系统会在保证先领取任务后执行的前提下，在 ${t_1}$ 、 ${t_2}$ 、 ${c_1}$ 、 ${c_2}$ 几个对象之间合理安排一个总距离最短的线路顺序，从而使工人在最短的时间内完成更多的任务，同时行驶最短的路程；在任务 ${t_2}$ 出现后，工人 ${w_2}$ 以及任务 ${t_3}$ 和其所对应的任务执行地点 ${c_3}$ 出现。假设所有的对象都出现在同一时间窗内，根据条件属性判断，如果工人 ${w_1}$ 再前去领取任务 ${t_3}$ ，会超出前面所领取任务的时间约束，而工人 ${w_2}$ 更加符合分配条件，那么系统会将任务 ${t_3}$ 分配给工人 ${w_2}$ 。从而使得在一定时间窗内，完成所有任务所耗费的平均任务完成时间最小化。

2.2 问题复杂性

禁忌搜索算法被广泛地用来解决组合优化问题，如调度问题、TSP问题等。在此用组合优化的思想来简单介绍禁忌搜索算法的计算复杂度。对于 $n$ 元素的置换问题，其所有排列状态数为 $n$ 的阶乘，当 $n$ 较大时搜索空间的大小将变得非常庞大，禁忌搜索则避免对所有的解空间进行搜索，仅通过搜索少量的空间来得到近似最优的结果，但是用禁忌搜索算法来解决3类对象任务分配问题仍然需要大量的计算。

3 解决方案

本文提出禁忌搜索算法与自适应阈值算法相结合的方法来解决基于路径规划的时空众包任务分配问题，首先分别对两种算法进行简单的介绍。

3.1 禁忌搜索算法

禁忌搜索算法是在局部邻域搜索算法的基础上发展而来的，它的特点是采用了“禁忌表”的概念，利用了人类短时记忆的特点，从而避免重复性搜索，所谓禁忌^[20]就是防止重复之前已经进行的工作，避免算法陷入局部最优，将搜索过程中出现的局部最优点记录在禁忌表中，在之后的搜索过程中，禁忌表中存在的信息便不再搜索，这样便可以跳出局部最优点。

禁忌搜索算法在最大车辆路径问题中应用较多。刘霞等^[21]对禁忌搜索算法进行了改进，并通过一些典型的算法对最大最小车辆路径问题进行了研究；对车辆路径静态子问题，提出了蚁群算法^[22]。为求解带时间窗和多配送人员的车辆路径问题，苏欣欣等^[23]对该问题进行了数学建模，并用禁忌搜索算法来求解。

对于组合优化问题 $\min f(x)|x \in X$ ，首先通过贪婪的计算方式得到初始解 $s$ ，定义 $m(x)$ 为初始解 $s$ 的邻域移动集，然后从该集合中挑选一个移动 $m \in m(x)$ ，如果该移动能够得到更优的解，便从当前解 $m'$ 继续搜索，假如邻域搜索过程中只有比当前解更优的解才能被接受，搜索过程便可能陷入死循环和局部最优。为避免以上情况的发生，设计禁忌表(Tabu List)，来存放刚刚进行过的移动，禁忌表的长度 $T$ 需要提前设定，这些移动称作禁忌移动(Tabu Move)。对于当前的移动，在以后的 $T$ 次搜索过程便不再选取，以避免陷入死循环， $T$ 次以后释放该移动。禁忌表在搜索过程中会不断修改，使得禁忌表始终保存着 $T$ 个移动。虽然设置了禁忌表，禁忌搜索算法仍有可能出现死循环。因此必须设置停止条件，当算法无法找到更好的解或者一个最优解反复出现的时候则算法停止。

3.2 基于随机阈值的禁忌搜索算法

算法输入迭代次数、禁忌搜索次数、禁忌表长度、循环次数以及工人集、任务集和地点集。为了提高搜索效率，采用贪婪的策略获取初始解，将总体迭代次数设置为100次，禁忌表的长度设置为10，输入任务集、工人集和地点集合。得到初始解后，进行下一步移动，迭代次数用来控制邻域搜索的次数，当所有任务都被分配后，迭代结束。将获取的局部最优解与禁忌表中的解进行对比，如果表中不存在，则填入禁忌表中，当禁忌表的长度达到10时，将表中的第一个解去掉，反复进行上述过程，在算法迭代100次后输出最优候选集，输出的结果为三类对象的顺序集合以及最小的总时间耗费。

对于众包工人的任务完成质量以及众包任务的预计等待时间，我们希望通过在线学习的方式训练出最理想的数值，在本小节借鉴自适应阈值的算法思想，来对工人服务质量进行设计。

质量控制是众包中的一个核心问题^[24]，众包工人初始都具有自己的服务质量属性，但是这个属性不是一成不变的，工人在完成任务过程中的表现，将会影响他们的服务质量：在规定的时间内更快地完成任务，工人的服务质量将获得提升，而不能在规定的时间内完成任务将受到差评，工人的服务质量将会相应地降低，虽然工人服务质量不会影响单个任务的报酬，但在任务分配过程中，在相似距离的条件下，系统将会优先把任务分配给服务质量更高的工人。

$ {q_w} = {q_w} + \Bigg(1 - \frac{{{\rm{AW}}{{\rm{T}}_{{t}}}}}{{{\rm{EW}}{{\rm{T}}_{{t}}}}}\Bigg) \times \varepsilon $

(6)

式(6)用来计算每次完成任务后，工人 $w$ 的服务质量变化，其中 ${\rm{EW}}{{\rm{T}}_t}$ 表示任务的预计等待时间， ${\rm{AW}}{{\rm{T}}_{{t}}}$ 表示完成任务所耗费的时间， $\varepsilon $ 是一个调整系数，设置大小为0.001。当 ${\rm{EW}}{{\rm{T}}_{{t}}} \geqslant {\rm{AW}}{{\rm{T}}_{{t}}}$ 时，表示任务完成，通过式（6）直接进行工人的服务质量变化。当 ${\rm{EW}}{{\rm{T}}_{{t}}} < {\rm{AW}}{{\rm{T}}_{{t}}}$ ，表示工人没有按时完成任务，分别按照超时和未完成任务给予不同程度服务质量的扣除。

$ \sigma = \frac{{\displaystyle\sum\limits_{i = 1}^{|W|} {{q_i}} }}{{|W|}} - \theta $

(7)

通过式(7)计算出一个阈值，每个工人必须大于该阈值才能参与任务分配。式（7）中的 ${q_i}$ 为工人 ${w_i}$ 的服务质量，通过求出当前区域所有工人的平均服务质量并适当调整，使得服务质量不够理想的工人也能被允许参与任务分配，同时剔除服务质量过低的工人。

$ {P_i} = {P_i} \times {(1 + \tau )^{({\rm{cos}}{{\rm{t}}_{{\rm{max}}}} - {\rm{cost}})/{\rm{cos}}{{\rm{t}}_{{\rm{max}}}}}} $

(8)

阈值的自适应变化过程具体如下： $\theta $ 从0.10、0.12、0.14、0.16、0.18、0.20六个值中以每个值对应的概率 ${P_i}$ 进行选取，每个值的初始概率相等，并且和为1。当出现新的 ${\rm{move}}$ 时，按概率随机选取 $\theta $ 的值并计算阈值 $\sigma $ ，同时计算当前 ${\rm{move}}$ 的时间耗费 ${\rm{cost}}$ 。通过历史实验得出单个 ${\rm{move}}$ 的最大 ${\rm{cost}}$ 不会超过300，因此设置 ${\rm{cos}}{{\rm{t}}_{\max }}$ 为300。通过式(8)对被选取的 $\theta $ 值的概率进行更新，其他值被选取的概率相应变小。设置 $\tau $ =0.01用以调整数值大小。

不同的任务由于与所分配工人的距离不同，所以预计等待完成的时间也不相同，每个任务在分配的时候都要计算出一个预计等待时间，工人要求在这个预计等待时间内完成任务。预计等待时间过长，则工人的效率就会降低，总体所耗费的时间便会增加，并影响到最终的优化目标；如果预计等待时间过短，那么工人便无法在短时间内同时执行多个任务，工人不能顺路接取任务，也会造成一定的时间浪费，同样无法达到优化平均任务完成时间的目的，所以预计等待时间的选取需要经过认真考虑。

$ {\rm{EW}}{{\rm{T}}_{\rm{i}}} = \frac{{|T|}}{{|W|}} \times \alpha + [{\rm{dist}}({l_t},{l_c}) + {\rm{dist}}({l_t},{l_w})] \times \beta $

(9)

预计等待时间的计算式(9)所示，影响预计等待时间的因素包括任务与地点之间的距离以及任务与工人之间的距离，当这两个距离过长时，意味着工人耗费在路程上的时间更多，需要更多的时间来执行该任务。另一个影响因素是当前区域工人密度，本文使用任务数与工人数的比值来表示。当工人数量较多的时候，每个工人分配到的任务数较少，任务可以更早完成；当工人数量较少时，每个工人将分配更多任务，导致一定数量的任务较迟执行。其中 $\alpha $ 和 $\beta $ 为调整系数， $\alpha $ 设置为5， $\beta $ 设置为0.3，用以控制计算结果的数值大小。当预计等待时间接近 ${\rm{dist}}({l_w},{l_t})/{v_w}$ 时，工人必须前往执行该任务， ${v_w}$ 为工人的行驶速度，统一设置为30。

4 实验分析 4.1 实验设置

实验环境：处理器为AMD Athlon(tm) Quad-Core Processor 2.79 GHz，内存容量为8 GB，Windows 7操作系统，编程语言 为 Python3.7。

为验证本文算法的有效性，从时空众包平台gMission^[25]获取了8000条记录，并在此数据的基础上进行了模拟数据的实验。该数据集包括工人、任务和任务对应地点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分别为算法的平均耗费时间和匹配数的对比结果。从表中可以看出：随着任务数增加，3个算法的平均耗费时间和匹配数都是不断增加的；随着工人数量的增加，平均耗费的时间是不断减少的。

由于本文算法目标是优化平均任务执行时间，因此希望更多的工人参与，为此本文设定了工作质量阈值，目的是使略微低于平均工作质量的工人能够在保证整体任务完成质量的前提下也能参与进来，从而增加工人数量。因此本文算法在匹配数和平均耗时方面取得了较好的效果。

4.2.2 半径对比

设置工人数量为20，任务数量为50，通过改变任务和工人的有效半径，对比3种算法在任务的分配数、耗费的总时间以及行驶的总路程几个方面的情况，实验结果如图2~4所示。

从图2和图4可以看出，ASPT算法的平均耗费时间是在不断增加的，在半径为2 km时达到最佳匹配数。Adaptive RT算法同样在半径为2 km时达到最佳匹配数，由于工人数量充足，在半径为3 km时得到了更少的平均时间耗费。从图3和图4可以看出由于工人数量增加，在半径为1 km时ASPT和Adaptive RT算法的匹配数都更多一些，因此在总行驶路程上有了一定的增加。而本文所提算法由于已达到最大任务数，并且工人数量增加提高了算法邻域搜索的多样性，总行驶距离有小幅度减少。

从上述实验可以看出，工人和任务有效半径的大小对ASPT算法和Adaptive RT算法具有较大的影响，对本文所提算法的影响较小，原因是本文算法更多地考虑时间约束，并且追求匹配数量的优化，同时禁忌搜索算法本身的搜索优化能力较强，能够在相同条件下产生更多的有效匹配。

4.2.3 参数设置

在计算预计等待时间时，设置 $\alpha $ 的值等于图5中的横坐标的10倍， $\beta $ 的值等于横坐标，通过对比实验确定在 $\alpha $ =5和 $\beta $ =0.3时优化效果最好，但整体变化幅度较小。

通过对比试验可以看出，改进后的禁忌搜索算法在行驶的总距离、耗费的平均时间以及对象的匹配数等方面都取得了相比于ASPT和Adaptive RT算法更理想的效果:本文所提算法在任务耗费时间上平均比Adaptive RT算法降低13%，比ASPT算法降低23.3%。在移动成本上比Adaptive RT算法降低了6.99%，比ASPT算法降低了25.9%。但是在算法的运行时间方面，本文所提算法具有较高的复杂度，运行时间较长，需要进行改进。

5 结束语

本文提出了众包工人需要携带任务到指定地点完成的工作模式，首次考虑了三类对象条件下众包工人的路径规划问题和移动成本问题；将空间上的距离成本换算成时间成本，分析了时间约束对任务分配过程的影响，提出了基于自适应阈值的禁忌搜索算法，并通过在线学习的方式，计算出每个任务合理的预估等待时间，通过合理的匹配使得区域内的众包任务能在最短的时间内得到分配。最后通过在真实数据集实验，验证了该算法在降低任务分配时间、提高匹配效率上具有高效性。在未来工作中，还要进行更多研究来降低算法的复杂度。同时，我们将继续研究路径规划中其他的经典算法，并将之应用到众包领域。