第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·