基于GPS轨迹的道路匹配的打车推荐
大城市的出租车都有GPS,通过一些技术进行采集后,可以形成一个出租车行驶轨迹。通过轨迹分析,可以做一些比较有意义的事情。
- 空车位置显示
这个在手机地图上已经有了。实现原理:
将出租车的位置记录下来,当用户查询时即返回。使用的数据结构:
QuadTree或者RTREE
ConcurrentHashMap:java的这个map类设计得比较好,在高性能大并发上,解决了一大难题。
(数据源,通常是不定时的向客户端推数据,每辆出租车的更新频率(采样率)不一,因此需要维护这个动态表)目前,实时显示,从数据接收到实际显示时间大约5s。
如果需要更快速的实时显示,需要重新设计该结构。
先说面临的几个问题:
数据来源:
第一种情况:假设数据从输入源是不断读取socket的buffer中获得的。
第二种情况:数据是从第三方一次性GET获得的,但2次GET获取有大量冗余数据,少量修改。
这两种数据来源是常见的2中情况。
数据频繁更新面临的问题:可以参考综述性文献
2006Vol. 33No. 8
移动对象索引技术研究进展兴)
廖巍熊伟景宁钟志农
(国防科技大学电子科学与工程学院长沙410073)
,说实话,我没有看得很懂,感觉有点杀鸡用牛刀,而是我这个不是完全的轨迹查询,并不查询某个时刻,该车辆位置(即不差分),而是最近一次车辆位置)
但在这里也给自己mark下名词:U-tree,DR-tree
(1)因为不断有新数据更新,如果车辆从位置1,变化到位置2中,原有RTree中记录的位置,需要删除掉。
(2)当间隔一段时间后,需要删除的对象特别多,RTree的删除是非常低效的,如果有大量删除,实际上不如重建RTree
为了获得接近实时查询:
先处理3种情况:
- 所有的车辆位置更新,拆分成删除已有的数据,然后新增现有数据。
- 对于本次没有的获取到的车辆位置(即无更新),不处理
- 本次新增加的数据。
对上述3中情况,(1)新增数据,是在一个新的TREE中(RTREE2)建立索引,即增量建立索引,。(2)删除数据,并不修改原有TREE中索引,而是直接修改该数据内容,对数据内容进行标识为删除。
(3)记录删除数据总量,如果删除总量超过50%(这个是我预估的,没有实际验证具体阈值是多少,比较合适),重新建立RTREE(删除Rtree1,Rtree2)。该步骤耗时较大,因此,系统延时较大。理论上,性能有个突变点,(在实际检测过程中,也确实发现cpu有一定周期性飙高一次)。
所有数据都是记录在一个Map中,因此,在实际过程中发现,这个Map是影响性能的关键点,(tree的建立
题外话:删除RTREE,也不能简单的删除,因为此时有可能外部还在访问,需要有同步(采用2个,来回切换实现,即修改指针,当无人访问该Rtree后删除。如何判断无人访问,我是通过等待一定时间,确保该时间窗口,所有访问会结束即可;当然也可以通过计数方式实现(较复杂),即访问某个TREE时,该计数器+1,当退出时,该计数-1,+1和-1操作需要原子操作。)
- 出租车位置推荐
(1)轨迹分析,将点匹配到道路上形成轨迹
(2)提取上车点,(有人提取下车点),这种差异基本可以忽略
(3)统计某个路口,该路口相关的车辆通过数(需要剔除重复车辆)
(4)基于局部加权统计该路口打车指数(采用线性的加权平均即可);但需要这个是二维空间+时间的加权,权重应该通过学习的算法来实现(我没有做这个过程,主要是缺失验证数据)
这是惠新街口附近得到的地区的打车位置推荐
<return> <results> <Sgstn> <score>2.0</score> <dist>169</dist> <rd>惠新西街</rd> <dir>175</dir> </Sgstn> <Sgstn> <score>5.0</score> <dist>174</dist> <rd>惠新西街</rd> <dir>355</dir> </Sgstn> <Sgstn> <lon>116415852</lon> <lat>39977023</lat> <score>3.0</score> <dist>242</dist> <rd>北土城东路</rd> <dir>85</dir> </Sgstn> <Sgstn> <score>2.0</score> <dist>299</dist> <rd>惠新西街</rd> <dir>235</dir> </Sgstn> <Sgstn> <score>2.0</score> <dist>361</dist> <rd>北土城东路</rd> <dir>85</dir> </Sgstn> <Sgstn> <score>4.0</score> <dist>437</dist> <rd>北土城东路</rd> <dir>85</dir> </Sgstn> </results> </return>
注意:同一个名字的道路,并不一定很近。
- 热点地区
出租车上下车最多的位置可以认为是热点地区。
(1)普通热点。如以北京为例,机场,机场高速路线,是出租车使用频率最高。
(2)突发热点。前几天,北京4号线停运,中关村大街,打车量比平时高很多。
(3)商圈。以晚上为例,出租车集中载客点,在三里屯,工体,国贸商圈。
因此,可以认为,该地区娱乐设施,夜间生活丰富,反之,如果一个地区的出租车聚集的地方,说明该商圈可能具有丰富的娱乐设施或者特殊的必须应用场景(机场,客站)。
这多多少少,可以为商业分析提供一丁点参考
以上3个,第二个,具有很大的争议性,因为,容易打车的地方,并不一定是出租车空车多的地方(可能人群更多),机场就是一个典型的例子。
转载自:https://blog.csdn.net/iteye_5392/article/details/82541489