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

李博扬 等:新型时空众包平台中的在线三维稳定匹配问题 3845

Table 2 Matching results of the offline guide
表 2 离线匹配结果
1
1
(w 1 70,1 ,u 1 87,1 , p 4 ) (w 1 25,1 ,u 27,1 , p (w 1 3,2 ,u 1,2 , p 1 ) (w 1 7,2 ,u 1 9,2 , p 2 ) (w 1 84,2 ,u 1 64,2 , p
6 )
3 )
y y y
9 9 9
8 u 1 8 8
p 6 p 6 p 6
7 7 w 2 7 p 5
6 p 5 w 1 6 p 5 6
p 4 w 3 p 4 5 p 4
5 5
p 3 u 2 p 3
4 4 u 3 4
3 3 3 p 3
p 1 p 2 p 1 p 1 p 2
2 2 p 2 2 w 4 u 5
1 1 1
u 4
12 3 4 5 67 89 10 x 12 3 4 5 678 9 10 x 1 2 3 4 5 6 7 89 10 x
(a) t 0:u 1 和 w 1 出现 (b) t 4:u 2 到达最长等待时间,u 3 出现 (c) t 6:u 4 和 u 5 出现
y y y
9 9 9
8 8 w 6 8 p 5 w 6 u 1
7 p 6 7 u 6 p 6 7 w 2 p 6
p 5 p 5 u 6 w 1
6 6 6
p 4 p 4 w 3 p 4
5 5 5
p 3 p 3 p 3
4 4 4 u 2
u 3
3 3 3
p 1 p 2 p 1 p 1
2 2 2
p 2 w 4
1 1 1 p 2 w 5
w 5 u 5 u 4 u 5
1 2 3 4 5 67 89 10 x 1 2 3 4 5 67 8 9 10 x 1 2 3 4 5 67 8 9 10 x
(d) t 7:w 5 出现 (e) t 9:u 6 和 w 6 出现 (f) 最终匹配结果
Fig.5 Execution process of the prediction-oriented matching algorithm
图 5 预测指导的匹配算法执行结果
算法复杂度分析:算法每个时刻需要执行一次,算法 M off 中使用索引可快速查询相应的匹配结果,复杂度为
O(1),对于所有用户和工人最优的匹配复杂度可以达到 O(|U|+|W|).对到达最长等到时间的用户调用延迟匹配算
法的最坏时间复杂度是 O(|U|×|W|×|P|).更新 M off 需要对其进行遍历,复杂度是 O(M off ).综上所述,算法最差复杂度
是 O(|U|×|W|×|P|).算法需要记录 3 种对象的信息,分别记录用户和工作点之间、工人和工作点之间的距离,还需
要记录离线匹配结果,空间复杂度为 O(|U|×|P|+|W|×|P|).
5 实验及分析

本节报告文中算法的实验结果,在真实数据集和合成数据集的情况下,分别对算法的效率和效用进行评估.
5.1 实验设置

本文采用滴滴盖亚数据开放计划(https://outreach.didichuxing.com/research/opendata/)作为测试的真实数据
集.滴滴出行是国内著名的出行服务平台,盖亚数据开放计划提供了真实脱敏的数据源,以天为单位,记录平台
中的出行信息.数据包括订单文件和轨迹文件:订单文件记录订单的起止时间和起止位置,轨迹文件按照时间记
录司机的行车位置.本文选取 4 天、相同区域的订单作为真实数据集,根据订单信息和轨迹信息选取工人和用
户的时空信息,出现在不同位置的同一司机被视为两个不同的工人,根据订单起始位置选取一些位置作为工作
点.时间槽设定为 15 分钟,即:全天被划分为 96 个时间槽,用户的最长等待时间是 15 分钟,区域大小为 0.5km×
0.5km.相同区域不同时间的数据被作为预测算法的训练数据.真实数据集的详细信息见表 3.