Xu X, Zhou J, Liu Y, Xu Z, Zhao X. Taxi-rs: Taxi-hunting recommendation system based on taxi GPS data. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(4), 1716-1727.

Taxi-RS:基于出租车GPS数据的出租车搜索推荐系统

思维导图

相关工作

轨迹挖掘

  • T-Drive

    • 基于时间依赖地标图的路由算法
    • 考虑诸多因素:天气,个人驾驶习惯,技能…
  • T-Finder

    • 聚类算法:寻找司机高收入地点
    • 概率模型:分析司机和乘客不同策略下的成本与风险
  • HUNTS

路线规划

  • 局部算法/渐增型算法:贪心 -> 局部最优解
  • 全局算法:运用费雷歇距离和弱费雷歇距离比较路径空间相似性

问题定义

目标

  • 计算定时定点打到出租车的概率
  • 计算打到空车的等待时间

基本定义

  • GPS Data Point(GPS数据点):gps_ij (taxi_i,时间t_j,经度longtitude_i,j,纬度latitude_i,j,速度v_i,j,方向dir_i,j,运行状态state-run_i,j)
  • Map Difference(图差值):ΔMap(t2, t1) = Map2 − Map1,不影响结果精度
  • Frequent Surface(频率曲面) :TCM(x,y,z)确定经度,纬度,出租车数量
  • Hotspot(热点):一天内某个坐标出租车数量超过阈值K
  • Hotspot Zone(热点区域):相近坐标热点的聚集,最小的Zone即一个热点
  • Trajectory(轨迹):从时间j到时间k的gps_ij~gps_ik的集合组成
  • Frequent Trajectory(频繁轨迹):轨迹出现频率超过阈值FT
  • FTG:包含所有热点的完全图

问题定义

  • Arrival time of the first taxi ( ATFC ) :T(x,y,t,m)代表点P(x,y)在当前时间t打车需在m时间内等到第一辆出租车的等待时间
  • the probability of getting a taxi ride ( PGTR ) :P(x,y,t,m)代表点P(x,y)在当前时间t打车需在m时间内等到第一辆出租车的概率
  • Effective Trajectory(有效轨迹):出租车在时间[t,t+m]内经过点P(x,y)的轨迹集
  • Effective trajectory graph ( ETG ) :出租车在时间[t,t+m]内经过点P(x,y)的轨迹图,包括子集FTG

概述

离线预处理模型

FTG模型

在线处理模型

离线预处理算法

文件分区

  • 按星期几分成七部分
  • 中间变量定义

    • LO:经度转化为参考点的横向距离
    • LA:纬度转化为参考点的纵向距离
    • S:与参考点的欧氏距离
    • v:速度
    • SET:t时间的所有GPS数据集合

$$
R_{i}= \frac{\sum {gps{x_{i}}\in SET_{i}}\left ( S_{x_{i}}\times v_{x_{i}}\right )}{\left ( \left | SET_{i}\right |\right )}
$$

热点扫描

  • 扫描每个文件块中的热点,获取频率曲面,使用hash简化
  • HSS算法:递归进行区间操作(线段树)求解热点区域数量

偏好轨迹扫描

  • 捕捉更频繁、更一般的轨迹
  • PTScan算法(PrefixSpan algorithm思想 ):从长度为1的前缀开始寻找符合阈值的投影,分治求解频繁子序列

FTG

条件

  • 根据历史数据分析速度和距离
  • 不会被其他乘客拦截,需要计算每个人每个方向的PGTR
  • 确保查询位置在首选轨迹上

设计新的数据结构time-stratified mul-tiple adjacent tab(TMAT时间分层多邻表)缩减空间复杂度

###

$$
node_{ij}
$$

  • Location:用hash值表示位置
  • Frequency:某一时刻的车辆频率
  • NextLocation:

$$
node_{i,j+1}
$$

  • NextEdge:频繁子序列的后一节点及对应的P

$$
node_{x,y},P
$$

  • PreviousTime:频繁子序列的前一节点及对应的P

$$
node_{a,b},P
$$

在线查询算法

输入

  • 上车地点
  • 查询时间
  • 可接受的等待时间

步骤

  • 将查询地点定位到相应热点区域
  • 根据时间信息,找出到达查询点的轨迹数
  • 根据轨迹数,估计参数,计算P和T

两个问题的解决方案

  • P

    • (n表示热门路线中某位置出现的次数)

$$
P_{i,j(preference)}=\dfrac{n_i}{n_j}
$$

- p代表路线中的PGTR

$$
P_{i,j(non-get)}=1-\prod {k\in E{i,j}}(1-p_{k})
$$

  • T=S/H,S平均行驶距离,H平均行驶速度

优化过程SPO

  • 以搜索点为根,热点为叶建立搜索树
  • μ为剪枝边界(一开始令等于m,小于0时剪枝)
  • 父子关系参数

$$
\theta =1-\prod_{i=0}^{m}(1-\omega (E).P)
$$

  • 第i层概率的平均,累和判边界

$$
\beta _{i}=lg(\frac{\sum {p\in PS{i}}lg(\omega (E).P)}{\left | PS_{i}\right |})
$$

两个问题的计算过程

  • PGTR符合泊松分布

$$
P=P(x\neq 0)=\lim {n\rightarrow \infty }\sum{i=1}^{m}P(x=i)=1-e^{-\lambda }.
$$

  • 第一辆出租车到达时间服从几何分布

$$
T=P_{1}Time_{1}+(1-P_{1})P_{2}Time_{2}+(1-P_{1})(1-P_{2})P_{3}Time_{3}+…+\prod_{i=1}^{n-1}(1-P_{i})P_{n}Time_{n}
$$

测试

结论

问题

  • 系统随时间推移而变化
  • 受外部因素影响

建议

  • 检查数据集的时间有效性,丢弃旧数据
  • 逐步替换旧数据,新数据与旧数据比例8:2
  • 使用动态图/动态规划算法构建离线模型

小仙女