[软件工程]基于浮动车的实时路况智能交通系统-浏览器端设计与开发.docx

存档编号 技术图纸及程序仿真及源代码需要联系qq：68661508业 论 文题目基于浮动车的实时路况智能交通系统 -浏览器端设计与开发 学 院 资源与环境学院 专 业 地理信息系统 姓 名 学 号 指导教师 完成时间 2013.5.20 教务处制独立完成与诚信声明本人郑重声明：所提交的毕业设计（论文）是本人在指导教师的指导下，独立工作所取得的成果并撰写完成的，郑重确认没有剽窃、抄袭等违反学术道德、学术规范的侵权行为。文中除已经标注引用的内容外，不包含其他人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确的说明并表示了谢意。本人完全意识到本声明的法律后果由本人承担。毕业设计（论文）作者签名： 指导导师签名： 签字日期： 签字日期：毕业设计（论文）版权使用授权书本人完全了解华北水利水电大学有关保管、使用毕业设计（论文）的规定。特授权华北水利水电大学可以将毕业设计（论文）的全部或部分内容公开和编入有关数据库提供检索，并采用影印、缩印或扫描等复制手段复制、保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交毕业设计（论文）原件或复印件和电子文档（涉密的成果在解密后应遵守此规定）。毕业设计（论文）作者签名： 导师签名：签字日期： 签字日期：基于浮动车的实时路况智能交通系统-浏览器端设计与开发摘 要交通拥堵现在已经逐渐成为我国大中城市的首要难题，如何及时地反映这些道路上路况，为出行者提供准确的导向，成为智能交通领域亟待解决的问题，传统的道路运行信息采集方式已经不能够适应快速增长的道路数量和车辆保有量。本文采用新兴的浮动车技术，以深圳市为背景，对深圳市出租车上传的GPS数据进行分析，在充分考虑这些GPS定位数据特性的基础上，开发出了一种适用于现代复杂道路结构的地图匹配算法。为了保证地图匹配的实时性，本文借鉴离线技术思想，提出了离线匹配支持下的在线匹配技术。该技术利用最短路径的一致性原理，将所需的每个节点间的最短路径存储到数据库中。与传统的道路网存储策略相比，该技术在提高查询效率的同时，又节省了大量的存储空间。在交通拥堵问题日益严重的今天，向人们发布实时交通状况信息是十分有意义的。因此本文根据地图匹配的结果，计算出深圳市道路的交通拥堵状况，建立基于浮动车的实时路况智能交通系统，发布深圳市的交通状况。人们出行时，就可以参考路况信息选择出行路线或者出行时间，以此达到调节交通流量，缓解交通拥堵压力的目的。该系统采用B/S构架模式，基于ArcGIS Server平台发布地图服务；利用ASP.NET构建网站后台，发布Web服务；前端使用Javascript语言，借助ArcGIS API for Javacsript接口进行开发，实现了地图匹配结果验证，实时路况发布等功能。关键词：浮动车；地图匹配；智能交通；实时路况；AbstractTraffic congestion has become the primary problem of large citys in china, how to reflect the road traffic, to provide accurate guidance for the traveler, has become an urgent problem in the field of intelligent transportation.The traditional ways to acquisition the road information could not meet the rapid number growth of the cars and the road.This paper adopts the floating car technology, with the city of Shenzhen as the background, the GPS data on the taxi from the city of Shenzhen Shenzhen was analysed, developed a suitable for modern complex structure of the road map matching algorithm.In order to ensure real-time map matching, based on the off-line thought of technology, proposes a off-line matching online support matching technique. The principle of consistency of the shortest path by using this technique, the shortest path to store each node will be required between the database. Compared with the traditional road network storage strategy, the technology to improve query efficiency, but also saves a large amount of storage space.In the increasingly serious problem of traffic congestion released today, the real-time traffic information to people is very meaningful. Therefore, according to the results of map matching, calculate the Shenzhen city road traffic congestion, the establishment of real-time traffic in intelligent transportation system based on floating cars, released the traffic situation in Shenzhen city. When people travel, you can reference traffic information to choose travel routes and travel time, in order to achieve the regulation of traffic flow, traffic congestion relief pressure to.Keywords: Floating Car; Map Matching ; ITS ; Real-time traffic ;目 录摘 要iiiAbstractiv目 录v第 1 章绪论11.1 背景11.2 浮动车技术简介21.3 浮动车技术研究现状31.4 主要研究内容41.5 研究意义4第 2 章地图匹配72.1 浮动车数据72.1.1 浮动车数据内容72.1.2 数据筛选72.2 道路网模型82.3 地图匹配算法92.3.1 地图匹配步骤112.3.2 确定GPS数据在边上的匹配位置122.3.3 匹配边权值计算122.4 SFPA最短路径算法132.5 离线匹配支持下的在线匹配142.5.1 SILC道路网存储策略142.5.2 选择SPFA最短路径算法15第 3 章基于浮动车的实时路况智能交通系统173.1 系统概述173.2 系统平台173.2.1 第三方平台工具173.3 总体设计193.3.1 设计原则193.3.2 技术路线193.3.3 功能设计203.4 Web服务203.4.1 Web服务设计203.4.2 Web服务调用213.5 功能展示253.5.1 匹配结果查询253.5.2 车辆追踪253.5.3 轨迹查询263.5.4 路况273.5.5 最优路径28第 4 章结论314.1 研究工作总结314.2 创新点314.2.1 地图匹配的准确性和实时性314.2.2 离线技术314.2.3 REST构架风格的Web服务设计314.3 研究展望32参考文献33致 谢35附 录(一) 英文翻译（原文）36附 录(二) 英文翻译（中文）47附 录(三) 毕业设计任务书55附 录(四) 本科生毕业设计开题报告57附 录(五) 部分源代码59xi华北水利水电大学毕业设计第 1 章 绪论1.1 背景先进的城市交通流诱导是防止和减轻交通阻塞，并最终实现交通流在路网各个路段上合理分配的有效手段，而交通状态信息的实时采集是该系统实现的基础。目前，许多先进的系统应用于车辆导航、实时交通信息采集与发布。例如，许多城市的出租车都安装了 GPS，用于车辆导航和调度控制，通过 GSM、GPRS 和 CD-MA 等无线通讯网络向控制中心传送，控制中心可以准确地知道出租车所在的位置。通过对遍布城市路网空间的、数量众多的 GPS 出租车位置移动所经过的路段以及时间的采集和分析，可以用来推算路网交通信息。随着现代科学技术的发展，尤其是全球定位技术、通信技术、网络技术、计算机通信处理技术、地理信息技术日新月异的发展，为解决上述问题提供了良好的技术基础1。GPS 具有全球、全天候、连续实时的三维空间定位与精密的时钟校准功能，有着广泛的应用价值和发展潜力。在海湾战争中，GPS 发挥了至关重要的作用，因而引起各国军事部门和民用部门的广泛关注。近十年来 GPS 定位技术在中国的应用已经得到迅猛发展，应用领域几乎涉及各行各业。特别是在智能交通领域，GPS 作为价廉物美的位置传感器，迅速占领了中国的个人导航服务与车辆安全监控的所有相关行业，成为移动终端（人或车辆）必备的定位设备的核心器件。因其具有定位精度高，速度快，不受云雾、森林等环境遮挡的特点，已被广泛应用于军事测绘精密测量、导航定位、交通管理、地球科学研究等国民经济各个领域，成为当今应用最为广泛的卫星定位系统。将 GPS技术与城市交通管理系统相结合，得到交通状况信息具有重要意义，可实现交通状况的实时检测。利用浮动车进行实时路况信息采集具有建设周期短、投资少、覆盖范围广、数据精度高、实时性强等优点。目前国内部分城市（如北京、广州、深圳、沈阳等）逐步在出租车上安装 GPS 终端，使这些车辆成为了能够获取一定动态交通数据的浮动车。深圳市目前已经在 6,500多辆出租车上安装了 GPS 终端这为实时路况信息的采集和处理提供了数据来源。这些终端能够每隔 1 分钟向深圳市出租车管理中心发送本车的位置、速度和方向等信息1，从而使这些出租车成为了能够采集实时交通信息的浮动车。当大量的浮动车在路网上运行时，便能实时反映整个路网的交通运行状况。1.2 浮动车技术简介浮动车技术的原理浮动车道路交通数据采集系统是基于全球定位系统(GPS)、地理信息系统(GIS)、无线通信技术、数据处理技术。浮动车系统通过搜集和存储浮动车 GPS 设备和无线通信设备实时回传车辆的 GPS 数据信息,并对其进行进一步处理,获得所需的交通路况信息。这些信息是交通管理部门和出行者所需要的,对交通的调度和管理以及出行者的交通规划起到了辅助与指导作用。浮动车本质上是对道路上的车流进行采样,通过应用相应算法对采样得到的数据(即浮动车 GPS 数据)进行处理,以此来还原所采样路段的道路交通状况信息1。如图 1-1 所示,浮动车系统主要包括三个部分:浮动车及浮动车终端、通信网络、信息处理中心。浮动车终端的作用是采集 GPS 数据信息。浮动车终端主要包括 GPS 模块和通信模块,它接受 GPS 定位卫星的信号并通过对不同卫星信号的处理来确定浮动车位置,然后以固定的频率发送浮动车的 GPS 数据信息至信息处理中心(服务器端)。浮动车一般为常见的机动车,从成本、覆盖率、机动车利用率等因素考虑,一般将出租车和公共汽车当做浮动车的第一选择。图 1-1 浮动车系统的架构通信网络的作用是提供浮动车终端到信息处理中心的数据通道。浮动车终端的通信模块将浮动车的 GPS 发送至数据通信网络,通信网络将其传输至信息处理中心。因为浮动车是不停运动的,而且单个浮动车的 GPS 数据的数据量不大,通信网络传输数据的方式只能是无线传输。无线传输浮动车 GPS 数据时必须要稳定、可靠,才能为信息中心提供及时、准确的原始浮动车数据信息。信息处理中心的作用是处理浮动车 GPS 数据信息。它首先存储浮动车传来的 GPS数据信息,并以固定的数据处理周期对 GPS 数据进行处理,将其转化为各种有用的信息,如交通路况信息、事故信息等。这些信息能够为交通管理部门和出行者提供有效的帮助。1.3 浮动车技术研究现状对浮动车技术的研究主要分布在几个方面:浮动车采样周期确定、浮动车采样率确定、数据预处理、浮动车数据处理等2。 浮动车采样周期的确定是浮动车数据采集环节重要的步骤。它们关系到浮动车GPS数据能否很好地反映道路交通状况。如果仅仅从技术角度来考虑,浮动车的采样周期是越短越好。但是越短的采样周期意味着更大的数据传输量、存储量和数据处理量,各种成本将显著增长。因此,更好的方法是从经济角度和数据结果两方面角度入手,确定最优的采样周期。有学者分别从概率论角度入手,建立模型来确定最优的采样周期。也有学者将浮动车 GPS 数据信息视为随时间变化的随机信号,从信号频域分析的角度入手得到采样周期。 浮动车采样率的确定和采样周期的确定同样重要。有的学者从路段覆盖率方面考虑,给出了浮动车最小覆盖率的计算模型2。也有学者给出了浮动车样本数量、路段覆盖率以及抽样时间段三者之间的关系。另外,还有学者从浮动车平均行程时间估计精度与平均速度估计精度两个方面考虑,给出了不同的浮动车采样率计算模型。还有学者提出的模型既考虑了估计结果的精度,也考虑了路网的覆盖率。浮动车采样率与采样周期这两个方面的研究较为充分,为浮动车技术的实际应用提供了强大的理论基础。浮动车系统的数据预处理包括浮动车 GPS 数据与 GIS 数据预处理、地图匹配等部分,是整个系统的基础环节。数据预处理负责识别和处理 GPS 数据采集模块中所存在的GPS 数据丢失、错误等异常,为最后的数据处理提供完整、可靠的 GPS 数据和 GIS 数据。地图匹配算法主要包括：路段选择算法和地图位置匹配算法。路段选择算法只运用路网几何信息的算法和将路网几何信息与路网拓扑性质相结合的算法,而将路网几何信息与路网拓扑性质相结合的算法是现在研究的主流。地图位置匹配算法目前主要有投影法、MAP 算法、最优估计算法等2。浮动车数据处理就是利用收集并存储的浮动车 GPS 数据推算出各种交通参数,如路段平均行程时间、路段平均速度、路段交通流量等交通参数,并将这些交通参数转化为准确的道路交通状况信息。这些信息可以为交通管理部门和出行者提供良好的决策依据和参考3。1.4 主要研究内容1) 建立一种满足地图匹配需求的道路网模型。2) 研究一种适用于现有浮动车定位数据特性的地图匹配算法。3) 使用现有浮动车数据，设计实现上述地图匹配算法的程序，验证算法正确性。4) 建立基于浮动车的实时路况智能交通系统，实时发布交通拥堵状况，为人们生活提供便利。1.5 研究意义基于 GPS 浮动车的交通状态估计技术被认为是实现先进的交通诱导的重要途径，尽管目前还处于探索阶段，但其在实验性的研究成果中已经表现出良好的应用前景4。交通诱导服务系统需要全路网或区域范围内的交通量、车道占有率、行程车速、行程时间等交通参数及交通状态信息等。移动型交通检测器可以检测大区域的路段交通流参数，包括路段的行程时间、行程车速及瞬时车速等区域性、连续性的交通参数，这是移动型交通检测器独特的优势5。通过 GPS 浮动车，在掌握路段和交叉口每个时段实时交通状况信息基础上，对各个路段、交叉口的相关交通参数进行测量、估算，然后通过交通诱导方式，向交通参与者提供实时的交通流信息6。从主观上，交通参与者可以在出行前依据交通诱导信息确定出行的时间、方式和路线，也可以在出行中依据交通诱导信息对出行方式和出行路线进行重新选择，以期达到躲避拥挤、缩短出行时间的目的。从客观上讲，交通参与者的这些决策结果使得交通流的时空分布更加合理，能够提高现有道路的利用效率。通过 GPS 浮动车技术，可以全面有效地获得道路的实时动态交通信息，通过行程速度等相关交通参数可以快速、准确地发现路网中已经发生或即将发生的交通拥挤。可以为制定合理有效的交通拥挤疏导策略提供有力的参考依据，避免因局部交通拥挤而引起全路网的交通瘫痪具有重要的现实意义和理论研究价值7。通过 GPS 浮动车技术，可以对全天所有时段、全市所有道路的实时动态交通信息进行采集，结合地图匹配和行程速度估算，便可获取及存储全市的交通运行参数8，能够为未来交通规划提供全面的完整的数据支撑。第 2 章 地图匹配2.1 浮动车数据2.1.1 浮动车数据内容图2-1：出租车数据内容内容说明：1) 车牌号：车辆的标识，与上传该信息的车辆的注册车牌号码一致。2) X坐标：以大地坐标（坐标系 WGS 84）形式记录的车辆位置的“经度”。3) Y坐标：以大地坐标（坐标系 WGS 84）形式记录的车辆位置的“纬度”。4) 时间：该定位信息采集的时间，通过 GPS 设备的时钟获取。5) 速度：车辆当前的行驶速度，单位为千米每小时。该列数据类型为整型。6) 方向：以真北方向为起点，按顺时针方向（北-东-南-西-北）计，分为 0、1、2、3、4、5、6 和 7 等八个方位。每个方位范围为 45 度，合计 360 度。2.1.2 数据筛选根据浮动车数据内容，数据主要存在以下三方面的问题1：一是测量值的精度低。车辆的行驶方位只用八个方位表示，而不是用 0.0360.0 度的范围记录，据估计是为减少数据的传输量而采取的措施；车辆的行驶速度的测量值的数据类型是整型，即无法表示测量值的小数部分，大大降低了测量值的精度。二是无测量误差信息。通过 GPS 设备测量的位置信息存在误差，其中包含 GPS 信号中人为加入的随机误差，信号经大气、建筑物等折射、反射带来的时钟误差等，因此每次测量的误差范围是数据处理的重要参考因素。通常 GPS 设备根据所接收的 GPS 信号在计算后除出定位坐标外还将输出水平定位精度和垂直定位精度等信息，而这些测量误差信息都没有被有效地存储。三是无出租车营运相关信息。出租车的运营状态是以出租车作为浮动车与其它类型的浮动车不同的重要特征之一，也是后续数据处理的重要输入。出租车可能存在空驶、载客、交班、休息停运、临时停车及停车待客等不同运营状态，当出租车处于停运、停车待客等特殊运营状态时，其采集的数据并不能反映当前道路交通的运行情况9。因为浮动车数据存在上述问题，所以需要依据出租车的运营状态剔除不可用的定位信息。2.2 道路网模型将路网抽象为“点线”模型。按道路中心线把道路抽象成线状要素，结合该线段各关键点的坐标以表征路段的形状和位置。通过节点连结不同线段的起点或终点，以此建立拓扑关系。通过与线段、节点相关联的表格存储与道路相关的属性12。该道路网模型主要由道路网，道路拓扑，节点，路段，节点遍历器，边遍历器等几个要素组成。如图2-2所示，每个要素都有不同的属性和方法，其中：节点(INode)：1) ID：该节点的唯一标识；2) X：该节点的经度；3) Y：该节点的纬度；路段(IEdge)：1) ID：该路段的唯一标识；2) FromNode：路段的起始节点；3) ToNode：路段的终止节点；4) OneWay：该路段是双行或是单行的；5) Length：路段长度；6) Points：组成该路段折线的所有点的集合；道路网(IRoads):1) GetCloseEdge：查询某点最近的一个路段；2) GetCloseNode：查询某点最近的一个节点；3) SearchEdges：查询某点周围内的所有路段；4) SearchNode：查询某点周围内的所有节点；5) GetNodeById：根据ID号查询节点；6) GetEdgeById：根据ID号查询路段；道路拓扑(CNodeEdge):1) GetNextNodes：查询以某个节点为起点的所有路段的终节点；2) GetPreNodes：查询以某个节点为终点的所有路段的起节点；3) GetNextEdges：查询以某个节点为起点的所有路段；4) GetPreEdges：查询以某个节点为终点的所有路段；图2-2：道路网模型接口设计2.3 地图匹配算法地图匹配的目的是确定浮动车上传GPS数据时的位置。地图匹配的根本依据是：“车是在道路上行驶的”10。这就意味着：1) 定位点应当处于浮动车所在的行驶道路上，尽管由于误差的原因，定位点不会精确地落在由电子地图所示的该道路中心线上。GPS的误差距离类似与正态分布，误差距离越大，可能性就越小11。所以GPS数据距道路中心线的距离是地图匹配的一个很重要的参数。2) 浮动车的行驶方向应当与沿着所在路段的走向与该路段所允许的通行方向相一致，因此将浮动车行驶方向与道路走向的夹角大小作为地图匹配的关键之一；3) 浮动车在行驶过程中不会出现空间跳跃的情况，它总是按着“路段 交叉点- 路段”的模式在路网上行驶。那么，通过前一个已匹配的定位位置结合前一定位点到当前时刻的行驶距离和道路网络的拓扑关系就可以估算当前位置。并且人们习惯通过距离最短的路径到达目的地。因此将前后两个相邻定位点间的行驶距离作为地图匹配的参考。当GPS数据在两条道路的交叉口附近时，应将其匹配到交叉口处。2.3.1 地图匹配步骤图2-3：匹配算法流程图系统采用的匹配方法具体步骤是：1) 当接收到GPS数据后，以该点为中心作缓冲区（比如以200m为半径的圆），找出穿过缓冲区的边，加入候选集合。2) 对候选集合中所有的边进行权值计算，剔除权值过小的边。3) 统计集合元素中边的个数，如果为0，则丢弃该GPS数据；如果为1，则匹配到这条边上；如果大于1，进行步骤4。4) 当候选集合中的边有交叉点并且交叉点到GPS数据的距离在限定范围内时，将它们的交叉点加入候选集合，并从集合除去这些边。5) 如果候选集合中只有一个点，没有边时，则将其匹配到该节点上。6) 将集合中所有的点和边都作为候选项，在接收到该车的下一个正常GPS数据时，以最短路径的方式选出最合适的候选项，以确定浮动车的行驶轨迹。2.3.2 确定GPS数据在边上的匹配位置以边上距GPS最近的点作为GPS数据的定位点，所以确定GPS数据在边上的匹配位置，就转换成了求点到折线段的最短距离的问题。折线段是由连续的直线段组成的。点到折线段的最短距离就是点到这些直线段中距离最短的一项13。点到直线段的最短距离用一下公式求得。公式 2-1其中：是直线段的端点；是点的坐标；是点到直线段上的垂点分直线段的比例；当t1时，线段上，点到线段的最短距离是线段的终点。2.3.3 匹配边权值计算在地图匹配时，赋予候选边的权值的主要公式如下： 公式 2-2其中：为评价结果，值越小越优；分别为距离和夹角的权重，系统默认取d为定位点到直线段的距离；为定位点方位和直线段方位的差的绝对值；为d的评价函数；为的评价函数。 公式 2 - 3其中；D为定位点到直线段的距离。即定位点到直线段上任意一点的距离的最小值，单位为米；R为候选路段距离定位点的最大允许距离，即允许的误差半径，单位为米，系统默认取R=30。14 公式 2 - 4其中：为允许的最大角度偏差，建议取；为定位点方位与直线段方位的差的绝对值。系统接收的GPS数据“方向”的意义：以真北方向为起点，按顺时针方向（北-东-南-西-北）计，分为0、1、2、3、4、5、6和7等八个方位，记“方向”为。用“方向”所示的范围的中心方位代表该定位点的行驶方向，记为则，直线段的方位记为,则。那么，假设某一路段的抽象模型为包含有n条直线段的折线段，记这些直线段为，对应的评价值为若，将中最小值记为，则对应的d与的值，分别为点到该路段的距离与浮动车行驶方向与该路段走向的夹角大小。如果的值不唯一，则取其中对应的d最小的一个或者多个当中的任意一个15。2.4 SFPA最短路径算法由于浮动车上传数据时间间隔较大，前后两个点往往会相隔多个路段。在这种情况下，最可靠的方法就是用最短路径来推测车辆行驶轨迹。本文使用SPFA算法进行最短路径运算，选择该算法的原因将在下一节中说明。SPFA算法是单源的，大致流程是有一个队列，初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队，并记录下其前一个节点16。直到队列为空时算法结束。SPFA最大的优点是其空间复杂度低，因为每个节点只保存到源点的前一个节点，这样存储源点到其它所有点的最短路径只需要N的空间，这样就大大的节省了最短路径预处理所需的存储花费。在做最短路径查询时，首先建立一个栈，将查询点压入栈中，循环将栈顶点的前一个点入栈，直到起点入栈为止。栈中的点序列就是查询的最短路径18。2.5 离线匹配支持下的在线匹配因为系统中接收到的数据量比较大，而最短路径运算相对来说是很耗时的，如果同时接收并做所有的处理工作，在现在计算机的水平下需要大量的时间。但实时路况要求在很短时间内完成所有的工作并将得到的路况信息发送给用户。如果我们事先计算所需的每个节点间的最短路径，并将结果保存起来。这样在系统运行的时候就不用再进行最短路径的运算，直接从数据库中查询即可。这样就避免了求最短路径时的高消耗19。但是预处理需要考虑查询效率，预处理时间和存储花费，简单的存储N个节点两两之间的最短路径需要N*3的空间20。为了减少空间存储，提高查询效率，针对在线地图服务和路程安排等领域中的点对点最短路径查询方法，系统使用SILC道路网存储策略，以有效存储预先计算好的点空间信息和与之对应的最短路径信息。2.5.1 SILC道路网存储策略对一个包含n个点的公路网络G = (V, E,) ，最简单的预处理方法是存储路网上任意2点u、v的最短路径，这样查询的时间复杂度为O(1)。假设路网中每条最短路径包含 O(N)个顶点，那么存储所有2N 条最短路径共需要的额外空间，这种方法由于其过大的存储空间而并不实用。SILC提出的降低存储花费的方法是只存储任意2点如u到v的最短路径上的第1个节点(“下一跳节点”)。举例来说，在下图中，到 的最短路径为，那么对于 、 来说，只需要存储最短路径上 的邻点。这样在查询路网中任意2点s到t 的最短路径时，可以先找到s到t 的最短路径上的下一跳节点w，然后再寻找w到t 的最短路径上的下一跳节点，直到到达终点t，共需要查找k次，其中，k为路径的长度。一种存储下一跳节点信息的简单方法是使用n n 的二维数组A，其中，数组中任一项Au,v代表u到v的最短路径所经过的u的邻接节点。这样数组A的存储花费为 。SILC方法利用了路径一致性，对于任一点q，将空间中其他点根据q到这些点的最短路径所经过的q的邻边划分为不同种类，其中，最短路径经过q的相同邻边的点为同一类，这样，空间上的点根据q的邻边被划分为不同类。SILC方法将空间中不同种类的点及所对应的邻边信息使用Quad树存储起来，最后用Quad树的二进制形式Morton Block方式压缩存储空间21。这样，每个点需要的额外存储花费从O(N)降到O()，因此，总的存储花费为O()。图2-42.5.2 选择SPFA最短路径算法由于SPFA算法在计算过程中，记录每个节点的前一个节点。这与最短路径的一致性原理是相似的。相对于其他最短路径算法，我们可以方便高效的对SPFA算法的运行结果进行缓存，在SPFA算法运算过程中，也可以有效的利用缓存，提高系统的运行效率22。第 3 章 基于浮动车的实时路况智能交通系统3.1 系统概述随着我国经济的发展，城市人口越来越多，汽车数量大量增加，随之而来的交通问题也越来越多，比如交通事故，环境污染，资源短缺，交通堵塞等。其中人们最关注的问题莫过于交通堵塞，并且由于我国独特的城市布局，城市中心区功能高度集中，人们都集中在中心区狭小的空间内工作，生活，更加剧交通的拥堵问题。因此向人们发布实时交通状况信息是十分有意义的23。本系统以深圳市为背景，以深圳市6,500多辆出租车上传的GPS信息为数据源，利用这些GPS信息，准确的对其进行道路匹配，进而计算出城市道路的交通拥堵状况信息。系统利用ArcGIS Server平台管理地图数据，发布地图服务；基于ASP.NET构建网站后台，发布Web服务；前端使用Javascript语言，借助ArcGIS API for Javacsript接口进行开发，构建实时路况发布系统，将深圳市的交通状况发布在网络上，人们可以通过浏览器就能查看深圳市实时的交通状况信息。人们出行时，就可以参考路况信息选择出行路线或者出行时间，以此来调节交通流量，缓解交通拥堵压力。3.2 系统平台开发语言：C#,Javascript;开发环境：Visual Studio 2010 , Chorme;数据库：SqlServer 2008;3.2.1 第三方平台工具ArcGIS Server 10：ArcGIS Server 是基于服务器的综合性 GIS 产品，提供高级 Web GIS 服务和应用程序以及企业地理数据管理功能。 ArcGIS Server 用于构建工作组、部门和企业级 GIS 应用程序以及 Web GIS 部署。ArcGIS Server 采用集中式的管理，支持多用户使用，允许他们访问丰富的 GIS 功能并且在构建时使用行业标准。ArcGIS Server 主要包含以下内容：1) 一组综合性 GIS 及地图服务和任务2) 基于标准的开放式 Web 服务接口，用于访问和使用 ArcGIS 服务3) 管理员控制台，用于设置和管理 ArcGIS Server 的安装4) 功能强大的企业地理数据库管理，可用于多种 DBMSjQuery：jQuery是一个兼容多浏览器的javascript库，极大地简化了 JavaScript 编程。jQuery在2006年1月由John Resig在纽约的barcamp发布，现在由Dave Methvin率领团队进行开发。jQuery是免费、开源的，使用MIT许可协议。jQuery的语法设计可以使开发者更加便捷，例如操作文档对象、选择DOM元素、制作动画效果、事件处理、使用Ajax以及其他功能。除此以外，jQuery提供API让开发者编写插件。其模块化的使用方式使开发者可以很轻松的开发出功能强大的静态或动态网页。Dojo：Dojo是一个使用Javascript编写的开源DHTML工具包。它建立在很多已捐献的代码基础之上。利用Dojo，可以很容易地建立动态web页面以及其他支持Javascript的环境。可以使用Dojo封装的组件，它使web站点更具有可用性、更快速的响应、更多的功能。Dojo的事件系统，I/O API,和泛型语言增强组成了强大的程序环境的基础。可以使用Dojo建造工具来为Javascript代码编写命令行单元测试。可以使用Dojo 包来使得代码更容易去维护和更少的平台依赖。Dojo主要分成4个包：dojo是核心，包括Ajax基础,以及事件、JSON、CSS查询等基本内容；dijit包含了各种基于模板的布局、组件类，可以在它们的基础上直接使用或者继承定制；dojox是上述两个包的扩展包，提供了更加丰富绚丽的组件以及功能；util是辅助工具包。Highcharts：Highcharts 是一个用纯JavaScript编写的一个图表库, 能够很简单便捷的在web网站或是web应用程序添加有交互性的图表，并且免费提供给个人学习、个人网站和非商业用途使用。目前HighCharts支持的图表类型有曲线图、区域图、柱状图、饼状图、散状点图和综合图表。HighCharts界面美观，而且运行速度快。另外HighCharts还有很好的兼容性，能够完美支持当前大多数浏览器。3.3 总体设计本系统采用B/S构架模式，B/S结构（Browser/Server，浏览器/服务器模式），是WEB兴起后的一种网络结构模式，WEB浏览器是客户端最主要的应用软件。这种模式统一了客户端，将系统功能实现的核心部分集中到服务器上，简化了系统的开发、维护和使用。客户机上只要安装一个浏览器。浏览器通过Web Server 同数据库进行数据交互。B/S最大的优点就是可以在任何地方进行操作而不用安装任何专门的软件，只要有一台能上网的电脑就能使用，客户端零安装、零维护。系统的扩展非常容易。B/S结构的使用越来越多，特别是由需求推动了AJAX技术的发展，它的程序也能在客户端电脑上进行部分处理，从而大大的减轻了服务器的负担24；并增加了交互性，能进行局部实时刷新。3.3.1 设计原则1) 实用性原则：该系统使用的数据简单、易得，同时变复杂的过程为模块化，使操作更简单、结果更准确、实用性更强；2) 标准化原则：系统地设计与开发基于信息标准化、规范化，并遵循相关行标准；3) 可靠性原则：系统运行要可靠、稳定、正确，并能保证所用数据的安全；4) 模块独立性原则25：系统的功能要明确，接口要简单，易于开发、测试和维护，同时增加模块间的内聚度，减小其耦合度。3.3.2 技术路线系统采用B/S构架模式，在服务器端，利用ArcGIS Server平台管理地图数据，发布地图服务；使用SqlServer 2008数据库管理数据，基于ASP.NET构建网站后台，发布REST风格的Web服务；在浏览器端，使用Javascript语言，使用AJAX调用服务器Web Service,并借助ArcGIS API for Javacsript接口进行开发。图3 - 1：技术路线图3.3.3 功能设计1) 基础功能：本系统提供了对地图的常用操作功能。包括地图的缩放、漫游、鹰眼、量算、导出地图等功能。2) 匹配结果：选择车辆、时间，查看该时间段内，车辆上传的GPS点的匹配结果。3) 车辆追踪：输入要追踪的车牌号，可以在地图上实时显示该车的位置信息。4) 轨迹查询：查询车辆在某段时间内经过的位置。5) 路况：实时显示当前最新的路况信息，也可以查询某个时间点的路况信息。道路的颜色表示道路的拥堵状况。6) 最优路径：在地图上点选起点和终点，显示从起点到终点距离最短的路径。并按照当前路况，显示从起点到终点用时最短的一条路径。3.4 Web服务3.4.1 Web服务设计系统将每个功能以Web服务的形式发布，用户通过访问Web服务以调用这些功能。表3-1列出了系统的Web服务：表3-1：Web服务设计服务说明输入参数返回结果车辆追踪实时定位车辆位置车牌号车辆当前位置速度等信息轨迹查询查询车辆在某段时间内经过的位置车牌号，查询时间段车辆在时间段内的位置信息匹配结果查询车辆上传的GPS数据的匹配结果车牌号，查询时间段所选GPS数据的匹配结果实时路况查询当前最新的路况信息每个路段的路况信息历史路况查询某一时间点的路况信息时间每个路段的路况信息最短路径两点之间距离最短的路径起点，终点起点到终点的路径最优路径某个时间，两点间时间最短的路径起点，终点，时间起点到终点的路径3.4.2 Web服务调用系统提供REST风格的WEB服务访问接口，用户可以通过AJAX方式访问URL来调用相应的WEB服务。REST简介表征状态转移（Representational State Transfer，简称REST）是Roy Fielding博士在2000年他的博士论文中提出来的一种软件架构风格。REST 从资源的角度来观察整个网络，分布在各处的资源由URI确定，而客户端的应用通过URI来获取资源的表征。获得这些表征致使这些应用程序转变了其状态26。随着不断获取资源的表征，客户端应用不断地在转变着其状态，所谓表征状态转移。REST是一种设计风格而不是标准，它定义了应该如何正确地使用Web标准。REST是无状态的，这意味着，REST无法跟踪从一个请求到下一个请求。每个请求都必须包含所有必要的信息并成功处理。REST风格特征27：1) 可寻址性：每个资源都有唯一的URL；2) 无状态性：服务器不能保持除了单次请求之外的，任何与其通信的客户端的通信状态。3) 链接与连通性：服务器可以通过“在表示里给出链接与表单来引导应用状态的变迁。这里的链接与表单起到了将资源相互连接起来的作用。4) 统一接口：客户端与资源之间的所有交互,都是通过为数不多的几个基本HTTP方法进行的任何资源都将暴露这些方法的一个子集,而且这些方法无论被哪个资源暴露,都具有相同的意义REST架构风格的优点：1) 可以利用缓存Cache来提高响应速度。2) 通讯本身的无状态性可以让不同的服务器的处理一系列请求中的不同请求，提高服务器的扩展性。3) 浏览器即可作为客户端，简化软件需求。4) 相对于其他叠加在HTTP协议之上的机制，REST的软件依赖性更小。5) 不需要额外的资源发现机制。6) 在软件技术演进中的长期的兼容性更好。REST服务URL设计系统Web服务符合REST风格约束，服务URL设计为层状结构，每个服务都有唯一的URL。如图3-2所示。例如在本机上测试最短路径服务对应的URL为：http:/hxf-pc:80/float/rest/Services/Path/Shortest。图3-2：Web服务URL设计AJAX调用Web服务在浏览器客户端，用户可以使用javascript脚本发送后台HTTP请求调用系统的Web服务。例如，调用最短路径服务，最短路径服务要求输入两个点作为参数var from_point = x : -178.244 , y : 50.007;var to_point = x : -179.244 , y : 50.105 ;编写回调函数：var call_back = function(data)alert(调用成功);发送Http请求，调用Web服务：$.ajax( url: http:/hxf-pc:80/float/rest/Services/Path/Shortest,data: fpt_x: from_point.x, fpt_y: from_point.y, tpt_x: to_point.x, tpt_y: to_point.y , type: POST, dataType: json).done(call_back);3.5 功能展示3.5.1 匹配结果查询该功能用于验证地图匹配的结果。在导航窗体中点击“匹配结果”一栏，显示匹配结果输入框。输入参数“选择日期”，“起始时间”，“终止时间”，“车牌号”；点击确定按钮，查询结果以表格形式展出。点击表格中的一行，该匹配结果会在地图上展示，如图3-6所示。图3 - 6：匹配结果3.5.2 车辆追踪该功能用于实时追踪车辆的位置在导航窗体中点击“车辆追踪”一栏，进入车辆追踪对话框。输入要追踪的车牌号，点击确定；这时地图上会自动更新该车辆的位置信息，如图3-7所示。图3 - 7：车辆追踪3.5.3 轨迹查询该功能用于查询车辆的历史位置。在导航窗体中点击“轨迹查询”一栏，显示轨迹查询输入框。输入参数“选择日期”，“起始时间”，“终止时间”，“车牌号”；点击确定按钮，查询结果以表格形式展出。点击表格中的一行，该匹配结果会在地图上展示，如图3 - 8所示。图3 - 8：轨迹查询3.5.4 路况实时路况该功能用于查询实时路况信息。在导航窗体中点击“路况”一栏，显示路况结果输入框。勾选显示实时路况复选框，地图上显示当前的实时路况。每个路段的路况拥堵级别以不同颜色表示，其中：红色表示拥堵，黄色表示缓慢，绿色表示畅通。图3 - 9：路况查询历史实时路况该功能用于查询历史路况信息。在导航窗体中点击“路况”一栏，显示路况结果输入框。勾选显示实时路况复选框，然后选择日期，选择时间；点击确定。地图上显示查询时间的实时路况。每个路段的路况拥堵级别以不同颜色表示，其中：红色表示拥堵，黄色表示缓慢，绿色表示畅通。如图3-10所示。图3 -