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