`

基于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种情况:

  1. 所有的车辆位置更新,拆分成删除已有的数据,然后新增现有数据。
  2. 对于本次没有的获取到的车辆位置(即无更新),不处理
  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个,第二个,具有很大的争议性,因为,容易打车的地方,并不一定是出租车空车多的地方(可能人群更多),机场就是一个典型的例子。

 

 

  • 大小: 66 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics