Page 180 - 《软件学报》2020年第12期

3846 Journal of Software 软件学报 Vol.31, No.12, December 2020

Table 3 Real dataset
表 3 真实数据集
日期 工人 用户 工作点
11.09 9 425 9 755 9 900
11.16 10 657 11 523 12 000
11.23 9 147 9 062 9 200
11.30 9 871 10 894 11 000

本文还通过一组合成数据集测试算法的可扩展性.首先,通过划定不同大小区域,调整工人集、用户集和工
作点集的大小.通过调整时间槽的时间跨度、用户等待时间的长短和区域大小来验证这 3 个参数对算法效率的
影响.合成数据集的详细信息见表 4,实验默认设置已经加粗显示.
Table 4 Synthetic dataset
表 4 合成数据集
参数 范围
|W|=|U|=|P| 10k,20k,30k,50k,100k
等待时间(分钟) 5,10,15,20,30
时间槽(分钟) 5,10,15,20,30
区域大小(千米) 0.1×0.1,0.2×0.2,0.5×0.5,1.0×1.0
实验环境采用的 CPU 为 Intel(R) Core(TM) i5-6500 3.20GHz CPU 以及 32GB 内存,算法通过 C++和 STL 库
实现.评价的算法包括延迟匹配算法(DM)和预测指导的匹配算法(POM),此外,将静态的三维稳定匹配算法 [10] 作
为最优解(OPT)进行比较.算法的评价指标包括任务匹配个数、运行时间和占用内存,预测和离线匹配的运行时
间和内存不计算在内.
5.2 真实数据集的实验结果
本节报告 3 种算法在真实数据集上的测试结果见表 5.
• 在 4 组不同日期的数据上,OPT 算法耗时最多,并且由于使用索引,导致占用内存最大;
• POM 算法的匹配结果次之,耗费时间最短,但占用内存略高于 DM 算法;
• DM 算法的匹配结果较差,运行时间高于 POM 算法,但是占内存最少.
实验结果说明预测技术对本文的问题具有指导作用,能够在一定程度上预测工人和用户的时空分布,从而
提高在线匹配的效果.由于 POM 首先进行离线匹配结果的查找,查找失败再进行 DM 的匹配,算法耗时较少.由
于 POM 保存了离线分配结果等,而 DM 算法只保存了基本的信息,导致了 POM 算法内存占用高于 DM 算法.
Table 5 Results over real datasets
表 5 真实数据集实验结果
数据集 算法 匹配率(%) 运行时间(s) 内存(MB)
OPT 84.54 45.88 204.47
11.09 DM 38.34 12.48 50.67
POM 62.14 9.67 127.88
OPT 84.96 57.23 278.53
11.16 DM 55.30 15.79 57.87
POM 64.99 11.81 159.96
OPT 81.83 44.12 188.75
11.23 DM 34.40 11.75 32.78
POM 58.20 7.14 107.67
OPT 86.86 49.66 218.67
11.30 DM 48.13 13.74 58.95
POM 67.34 8.47 130.36

5.3 合成数据集的实验结果
本节在合成数据上研究不同参数对 3 个算法的影响,包括工人数量、用户数量和工作点数量、用户等待时