题目：浮动车交通信息处理技术关键算法的研究与实现

浮动车（Float Car Data）技术，也被称作“探测车（Probe car）”，是近年来国际智能交通系统（ITS）中所采用的获取道路交通信息的先进技术手段之一。其基本原理是：根据装备车载全球定位系统的浮动车在其行驶过程中定期记录的车辆位置，方向和速度信息，应用地图匹配、路径推测等相关的计算模型和算法进行处理，使浮动车位置数据和城市道路在时间和空间上关联起来，最终得到浮动车所经过道路的车辆行驶速度以及道路的行车旅行时间等交通拥堵信息。如果在城市中部署足够数量的浮动车，并将这些浮动车的位置数据通过无线通讯系统定期、实时地传输到一个信息处理中心，由信息中心综合处理，就可以获得整个城市动态、实时的交通拥堵信息。浮动车数据具有数据规模大、实时性强和离散分布等特点，其核心处理算法必须达到计算速度快，结果准确性高的性能才能满足提供实时动态交通信息的系统需求，基于此，本文研究并设计了一种快速的地图匹配算法和准确的路径推测算法，以及能对它们的高效运行提供有效支持的三层路网数据结构。用于大规模浮动车数据处理的地图匹配算法采用将地图数据分块、将道路结构分层的思想，利用小网格和路段方向属性作为索引，选择候选的匹配路段，可大大缩短候选匹配路段的搜索时间，显著地提高计算效率；而基于向量识别的路径推测算法采用了类似A*算法的启发式图搜索方式，导入几何运算的约束条件，根据车辆轨迹点所形成的向量与特殊的路网数据结构比较来进行启发式搜索，选择车辆所有可能行驶的候选路径。然后根据全局择优的方式从整体进行比较并选择车辆最有可能的行驶路径。同时，通过对基本道路空间数据的分层处理和抽象，本文改进了基于节点－路段－路链的三层路网数据结构，有效的为上述算法的运行提供支撑。本文利用上述的算法和路网数据结构，为一个实际的动态交通信息服务系统，设计并实现了其核心子系统－浮动车交通信息处理子系统。通过一系列的时间效率测试，和数据准确性的对比实验，验证了本文设计的浮动车交通信息处理关键算法的正确性和高效性。