基于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个，第二个，具有很大的争议性，因为，容易打车的地方，并不一定是出租车空车多的地方（可能人群更多），机场就是一个典型的例子。