城市中急剧增加的机动车辆数量与城市道路资源之间的矛盾日益凸显，经常产生的交通拥堵给人民的出行造成严重困局并引发了诸如环境污染、能源浪费、时间浪费等一系列社会问题，高效的交通信息查询分析变得非常重要。

车辆轨迹与依赖电感线圈、监控摄像头的传统交通信息获取来源相比，具备独有的优势：①在数据采集的范围上，车辆轨迹几乎遍布整个交通网络，而传统交通信息获取设备的部署范围较为有限；②在信息获取的角度上，基于电感线圈无法获取诸如行程时间等路段级别的信息，基于监控摄像头的视频车辆识别技术的识别效果易受天气、车辆密集程度等因素的影响，识别精度难以保证。

现有针对车辆轨迹交通信息的研究大致可以分为交通信息提取^[1-3]和交通决策应用^[4-8]两类。前者探讨如何从原始车辆轨迹中提取诸如行程时间^[1]、平均速度^[2]、车辆密度^[3]、排队长度^[3]等实时交通信息。后者侧重如何利用这些交通信息，为交通调度、道路规划提供决策依据，目前已在最优路径选取^[4]、路径推测^[5]、路网生成^[6]、路网结构动态更新^{[7, 8]}等多个应用领域取得了一定的成果。

Spaccapietra等^[9]提出轨迹中两种基本的拓扑状态：停留/移动(Stop/Move)。向隆刚等^[10]对Stop/Move模型进行拓展，提出了轨迹与地理空间中的点、线、面实体的时空拓扑关联模型。

本文对车辆轨迹与路网(表现为线状实体集合)之间随时间变化的拓扑关联关系，即动态拓扑过程进行探究，提出了轨迹-路网动态拓扑过程模型，完整地描述车辆轨迹在路网中的动态移动过程。在此基础上，设计了轨迹-路网动态拓扑过程模型的关系模式，并探讨了该模型在交通信息分析中的应用。

1 轨迹-路网动态拓扑过程建模

随着行驶时间推移，车辆轨迹与路网中道路的拓扑关系也不断动态生成并发生变化。轨迹-路网动态拓扑过程是对车辆轨迹在路网运动过程中与道路之间的拓扑关系的动态产生的过程进行描述与表达。一方面，路网一般包括多条道路，也就是多个线状实体，需要考虑轨迹与不同道路之间的拓扑关系；另一方面，还需要考虑车辆轨迹自身移动状态的变化(如停留、折返等)。从而完整地构建轨迹-路网动态拓扑过程模型。

考虑到轨迹、路网的复杂性以及拓扑关系的多样性，本文将车辆轨迹划分为拓扑关键点与拓扑子轨迹，在此基础上建立轨迹-路网动态拓扑过程模型。

1.1 拓扑关键点与拓扑子轨迹

定义1  轨迹拓扑状态。轨迹拓扑状态是车辆轨迹在某一时刻于路网中的瞬时拓扑状态，由轨迹停留状态、移动方向、所在道路3部分组成。停留状态是指轨迹当前处于移动或者是停留的状态；移动方向是指轨迹前进方向与道路方向的关系；所在道路是指轨迹当前所处的道路。当轨迹的停留状态、移动方向、所在道路中的任意一部分发生改变时，就说明轨迹拓扑状态发生了变化。

定义2  拓扑关键点。拓扑关键点是轨迹拓扑状态发生变化的临界点，包含拓扑关系信息的关键点。轨迹的起点和终点也被视作拓扑关键点。值得注意的是，拓扑关键点并不是几何意义上的0维点，而是拓扑层面的关键点，在某些情况下，拓扑关键点甚至对应一段子轨迹(如停留点)。

在拓扑关键点定义的基础上，车辆轨迹在路网中被拓扑关键点划分为多个轨迹局部拓扑状态保持不变的子轨迹，我们称之为拓扑子轨迹。

定义3  拓扑子轨迹。拓扑子轨迹是指位于连续的两个拓扑关键点之间，轨迹拓扑状态保持不变的子轨迹。

在定义1~定义3的基础上，一条车辆轨迹可以被划分为n(n≥2)个拓扑关键点和n-1个拓扑子轨迹组成的序列。在拓扑关键点处轨迹与路网的拓扑状态发生变化，从而形成拓扑关系；在拓扑子轨迹中，轨迹在某条确定的道路中上行行驶或下行行驶，拓扑状态保持不变。

1.2 轨迹-路网空间参考框架

网络约束下的移动对象数据库往往使用结点-弧段模型对数据进行组织、查询，而在现实生活中，人们常常使用自然语言下的道路名对世界进行认知。使用贴近人类理解的语言对数据进行表达，有助于降低人们理解并查询、分析抽象数据的难度。因此，本文以自然语言中的道路(双向)为基准，建立轨迹-路网空间参考，并在此基础上建立轨迹在路网中的动态拓扑过程编码。

1.3 轨迹-路网动态拓扑过程模型定义

拓扑关键点表明轨迹在路网中的拓扑状态发生了变化，而拓扑关键点与特定道路的拓扑关系是唯一的，因此，拓扑关键点编码可以表示为在不同道路中拓扑关键点处对应拓扑关系的序列。

定义4  拓扑关键点编码。拓扑关键点P的编码SKPC定义为：

(1)

其中，Pⁱ为语义关键点P在某条道路中对应的语义。当m>1时，表明该拓扑关键点与多条道路存在拓扑关系。Pⁱ为轨迹在拓扑关键点P时在某条道路中对应的拓扑状态，可表示为四元组{pid, xytz, road, time}。该四元组中，pid代表关键点的标识符(identifier，即ID)。x与y分别表示轨迹入边、出边在相应道路上的拓扑方位，即取空集Φ或f、b、l、r之一，取Φ代表该方位关系不存在。z为关键点在道路中的拓扑方位，取s、i、e之一。拓扑关系语义标签表示轨迹在关键点处与道路的拓扑关系语义，取之一，分别代表始于、终于、进入、离开、相遇、穿越、折返、停留。road为关键点P所处的道路；time为轨迹在关键点P所处的时间。当在关键点处存在停留时，time也表示该停留所处的时间范围。

将xyz称之为拓扑关系编码，包含了关键点处拓扑状态的上下文信息。单从排列组合的角度出发，xyz可以得到600种可能的排列。然而，一些情况在实际中是不可能发生的。本文通过对拓扑关系编码进行整理，并考虑复合拓扑关系(中存在多种拓扑关系语义)的情况，给出了118种有意义的拓扑关系编码，如表 1所示。

在关键点编码的基础上，我们进一步给出拓扑子轨迹编码。

定义5  拓扑子轨迹编码。对于给定的拓扑子轨迹S，对应的编码如式(2)：

$\begin{array}{l} {\rm{SSTC}} = \left\{ {{\rm{sid}}, {\rm{pi}}{{\rm{d}}_s}, {\rm{pi}}{{\rm{d}}_e}, xdy, {\rm{road}}|{\rm{sid}}, {\rm{pi}}{{\rm{d}}_s}} \right., \\ \left. {{\rm{pi}}{{\rm{d}}_e} \in Z, x, y \in \{ s, i, e\} , d \in \{ f, b\} } \right\} \end{array} $

(2)

式中，sid为拓扑子轨迹的ID、pid_s与pid_e分别为拓扑子轨迹起点、终点对应的拓扑关键点的ID，x、y分别对应子轨迹起点和终点在所处道路中的拓扑方位，而行驶关系语义标识对应车辆轨迹在道路中的行驶方向信息，其取值表示行驶方向为上行方向，b表示行驶方向为下行方向。xy经排列组合可得到8种情况，表 2列出了沿着道路上行、下行两种情况下的子轨迹编码。

综上所述，本文给出的轨迹-路网动态拓扑过程模型定义如下：

定义6  轨迹-路网动态拓扑过程模型。设轨迹包含n(n≥2)个拓扑关键点，这n个拓扑关键点将轨迹分成n-1段拓扑子轨迹，那么，轨迹-路网动态拓扑过程模型可以表示为式(3)：

$\begin{array}{l} {\rm{TRSM}} = \left\{ {{\mathop{\rm tid}\nolimits} , {P_0}, {S_0}, {P_1}, {S_i}, \cdots , {S_{n - 1}}} \right., \\ \left. {{P_n}|{P_i} \in \left\{ {P_i^0, \cdots , P_i^{m - 1}} \right\}} \right\} \end{array} $

(3)

其中，P_i为该轨迹中第i处拓扑关键点的编码；S_i为由P_i和P_i+1两个连续的拓扑关键点确定的拓扑子轨迹的编码。

2 轨迹-路网动态拓扑过程提取

轨迹-路网动态拓扑过程提取，是从原始的车辆轨迹数据以及路网数据中得到最终的轨迹-路网动态拓扑过程模型的过程。其过程可以分为轨迹数据预处理、停留点提取、路网匹配、关键点提取以及拓扑关系生成。

2.1 数据预处理

数据预处理可以分为轨迹数据预处理和路网数据预处理。

由于GPS设备故障、信号质量等原因，原始GPS轨迹数据中可能存在一定量的重复点和漂移噪声等影响轨迹数据质量的点。轨迹数据预处理分别对重复点和漂移点进行处理，对于重复点的剔除较为简单，对于漂移点，往往通过速度阈值^[11]、转折角度^[12]等联合手段进行去除。

路网数据预处理主要分为路网空间矫正和拓扑修复，空间矫正是指对路网数据在地理坐标下的偏移进行修正，使之与轨迹数据相匹配，而拓扑修复是指修复路网数据中错误的拓扑信息(如相连弧段的分裂)。

2.2 停留点提取

停留点是移动对象静止或在小范围内移动的点所形成的子轨迹^[13], 对于车辆轨迹，停留点常常表现为在停留中心附近来回移动的轨迹点所构成的团簇。由于停留点处轨迹点数量较大且精度有限，若不对停留点进行识别并在后续计算中加以排除，将大大增加后续路网匹配和拓扑过程提取的计算时间。停留点的识别方法有很多, 本文选择了CB-SMoT算法^[14]，以10 min与50 m作为停留判别阈值，提取车辆轨迹中的停留点。

2.3 路网匹配

由于GPS设备定位精度有限，可能导致车辆轨迹中的点并非落在道路上。有必要对车辆轨迹进行路网匹配，将车辆轨迹点投影至其对应的道路中并同时获取车辆在路网中的行驶路径。考虑到轨迹数据的采样频率可能较低，为保证道路匹配的精度，本文选择了基于隐马尔科夫链的路网匹配算法^[15]，并使用该文献中推荐的参数进行匹配。

2.4 关键点提取

根据轨迹-路网动态拓扑过程模型，在路网中涉及到的拓扑关键点主要分为两类：①由轨迹自身性质所决定的停留点或折返点；②轨迹在行进过程中所经过的两条道路的道路交叉口。停留点的提取见§2.2。折返点可以通过判断在同一条道路上连续的3个轨迹点之间的夹角来判断，本文选取15°作为阈值，若在同一条道路上存在连续的3个轨迹点P_i，P_i+1，P_i+2的夹角∠P_iP_i+1P_i+2 < 15°，则将P_i+1视为折返点。值得注意的是，大多数车辆轨迹数据集轨迹点的采样间隔较大，一般在20 s~1 min之间，这就导致了相对稀疏的轨迹点未必落在道路的交叉口，因此，需要构造位于道路交叉口处的虚拟节点作为拓扑关键点，并按照时间顺序插入到对应的轨迹中去。

2.5 拓扑关系生成

从表 1中可以发现，对于任意的拓扑关键点P，拓扑关系语义标签 可以由其对应的拓扑编码x、y、z共同决定(除停留)。因此，在从轨迹中提取停留点的基础上，只需结合以关键点为中心的入边/出边的拓扑方位及关键点在对应的一条或多条道路中的拓扑方位便可导出轨迹与道路的拓扑关系。对于拓扑子轨迹S_i，其在道路中对应的行驶关系则可以通过其两端的关键点P_i与P_i+1导出。

3 交通信息查询分析应用 3.1 基于SQL的轨迹-路网动态拓扑过程数据组织

轨迹-路网动态拓扑过程建模完成了从车辆轨迹到其在路网中的时空动态拓扑过程的映射，而轨迹-路网拓扑关系提取则完成了从车辆轨迹、路网数据到拓扑关系信息的转化。如何对这些拓扑关系信息进行组织，从而支持高效的检索，是基于动态拓扑过程模型的交通信息查询分析的关键。考虑到关键点与子轨迹编码的结构性以及轨迹、路网、子轨迹、关键点、道路节点之间的关联性，本文将轨迹-路网动态拓扑过程信息存储在关系数据库中，在避免后续查询分析中重复计算的同时，支撑起高效的查询应用。图 1给出了一个简单的面向轨迹-路网动态拓扑过程模型的关系模式示意图。

该关系模式中仅仅列出了支撑拓扑关系查询的关键字段与联系，省略了诸如道路具体信息、几何网络信息的部分。对于关键点表KeyPoint，轨迹ID、道路ID、关键点ID使得关键点编码唯一确定，Type对应拓扑关系语义标签，Position对应z，而FromDirection与ToDirection分别对应以关键点为中心分界的轨迹入/出边在路网道路在路网道路中的拓扑方位x和y。值得注意的是，当关键点对应一个点时，其起始时间StartTime与结束时间EndTime重合，而当其对应停留时，StartTime与EndTime表示停留的时间范围。在子轨迹表SubTraj表中，FromKeyPoint和ToKeyPoint分别表示该子轨迹的起点以及终点所对应的关键点ID，Direction表示车辆在这段子轨迹内相对于道路的行驶方向。

3.2 实验数据

本文以武汉市658辆出租车7 d的轨迹数据以及从OpenStreetMap上下载的武汉市路网数据作为实验数据。由于OpenStreetMap的路网数据由用户自由上传，其数据存在诸如拓扑错误、道路名缺失等现象且现实道路状况非常复杂，很难构建完整的路网结构。本文在原有数据的基础上手工编辑并选取了29条典型的道路。在轨迹-路网动态拓扑过程模型的基础上，本文一共从29 868条轨迹中提取了512 450个关键点。

3.3 道路交叉口分析

道路交叉口是不同道路交汇口，车辆在通过交叉口时，车辆与道路可以产生左转、右转、直行等不同的“离开”，基于本文模型，可以将道路交叉口分析描述为：统计某个道路交叉口处按照Type分类的拓扑关键点的数量。基于本文模型，查询2014年6月4日上午8:00至中午12:00武汉市区武珞路这条道路的end关键点处按照Type统计拓扑关键点的数量。结果如表 3。

3.4 道路交通流量分析

交通流量是指在选定时间段内通过道路某一地点、某一断面或某一车道的交通实体数，实时准确的交通流量信息是辅助智能交通系统实现其功能的关键。基于本文模型，某一路口处交通流量可以被描述为从t₁时刻到t₂时刻时间段内从道路终点“离开”以及“进入”道路的轨迹的数量。图 2给出了使用该方法查询得到的武汉珞喻路以30 min为时间段单位的24 h的交通流量趋势图。

3.5 道路行程时间分析

道路行程时间是车辆通过选定路段所用的时间，是评判道路状况的重要依据。在本文的模型下，某车辆道路行程时间可以被描述为从某道路起点“进入”到从该道路终点“离开”两个连续的拓扑关键点之间的时间段。基于该方法查询得到12:30至13:00时段中，车辆通过武汉市珞喻路路段的通行时间为431 s。

4 结束语

本文建立轨迹-路网动态拓扑过程模型对车辆轨迹在路网中的时空动态拓扑过程进行精确表达，并且将轨迹-路网拓扑关系信息通过关系型数据库进行组织，以支撑高效的信息查询。在信息建库的基础上，本文从道路交叉口分析、道路交通流量分析、道路通行时间分析等多个角度来展示轨迹-路网动态拓扑过程模型在交通信息查询分析中的应用潜力。考虑到轨迹点采样间隔较大对停留点提取精度的影响，本文的模型可以用于更高时间分辨率的车辆轨迹数据的拓扑过程提取，为更加精细的交通信息查询分析提供支持。