基于GOS的不停车收费系统_毕业论文.doc 41页

'题目：基于GPS的不停车收费地图匹配方法研究I 摘要基于GPS的不停车收费技术代表着未来道路收费的发展方向，精确的地图匹配决定该收费系统能否成功实现精确收费。本文概述了各种常用的地图匹配算法，并就各种地图匹配算法进行系统的分析和对比，在此理论基础上，提出基于GPS的不停车收费系统的地图匹配算法。本文以自驾车从黄岛到济南为例，对此路线中收费用地图中的关键点即收费点进行定义，并提出了一种新的专门用于收费的地图匹配算法。此算法被证实是具有可行性的。关键词：GPS，不停车收费，收费电子地图，地图匹配I 青岛理工大学毕业设计（论文）ABSTRACTABSTRACTDoparkingchargebasedonGPStechnologyrepresentsthefuturedevelopmentdirectionofroadpricing.Accuratemapmatchingdecidedtoachieveprecisechargingofthesuccessofthechargingsystem.Thisarticleoutlinedthevariouscommonlyusedmapmatchingalgorithm,andavarietyofmapmatchingalgorithmforsystemanalysisandcomparison,basedonthetheory,putforwardthenoparkingchargesystembasedonGPSmapmatchingalgorithm.Takingself-drivingfromHuangdaotoJinanasanexample,thisrouteinchargewiththepointsonthemap—thechargepointsaredefined,andanewmapmatchingalgorithmisdesignedtocharge.Thealgorithmisprovedtobefeasible.KeyWords:GPS,noparkingcharge,electronicmap,mapmatchingII青岛理工大学毕业设计（论文）目录26 青岛理工大学毕业设计（论文）目录目录摘要：IABSTRACTII目录11绪论31.1论文研究的背景31.2道路收费的发展历程31.3GPS收费系统的原理与特点51.3.1DSRC电子收费技术61.3.2ANPR电子收费技术71.3.3基于GPS的不停车收费技术91.3.4DSRC、ANPR和基于GPS的电子收费技术的性能比较及分析121.4本文研究内容及结构132地图匹配技术152.1地图匹配的基本原理152.2常用地图匹配算法182.2.1最短距离算法182.2.2概率统计算法192.2.3基于拓扑关系的算法202.3地图匹配方法分析212.4地图匹配的应用223基于GPS的不停车收费系统地图匹配方法243.1基于GPS不停车收费地图匹配的作用243.2基于GPS的收费地图的定义243.2.1道路收费地图收费关键点及收费路段定义253.2.2主线站出入口特殊处理253.2.3收费关键点和收费路段属性值的定义253.2.4地图精简273.3基于GPS的不停车收费系统的地图匹配方法2838 青岛理工大学毕业设计（论文）目录3.3.1地图匹配中搜索范围的确定283.3.2卫星收费地图匹配算法描述293.4该算法可行性实验344总结36致谢37参考文献3838青岛理工大学毕业设计（论文）1绪论38 青岛理工大学毕业设计（论文）1绪论1绪论1.1论文研究的背景高速公路因其“高速、高效、安全、舒适”等优点，在现代化公路建设中己成为发展的必然趋势。作为连接主要城市和重要港口的枢纽——高速公路，已成为承载繁忙运输的交通要道。我国的“十二五”规划中明确指出，要进一步完善公路网络，发挥路网整体效率。全国公路总里程已超过400万公里，五年增加38万公里，高速公路里程已达6.4万公里，总里程数位于世界第一。然而，与公路建设相比，公路收费的自动化水平却相对滞后，传统的收费方式（找零、回票、投币）无法缓解尖峰时间的车流量，效率低下，使车辆在收费站区域滞留，形成“瓶颈”，不能很好的发挥高速公路的服务优点，从而使电子不停车收费系统应时而生。电子不停车收费系统是智能交通系统的主要服务内容之一，是国内外正在不断开发并推广普及的一种用于公路、大桥和隧道的电子自动收费系统。目前广泛应用的主要是利用专用短程微波通信技术，通过路侧单元（RSU）与车载单元（OBU）的信息交换，自动识别车辆，采用电子支付方式，自动完成车辆通行费扣除的全自动收费方式。而基于GPS的不停车收费系统是世界上最先进的电子收费方式之一，它的诸多优点注定其必将成为未来发展的方向。作为电子不停车收费中最具广泛应用前景的GPS不停车收费系统正逐渐受到人们的青睐。卫星收费电子地图是卫星收费系统中的核心技术，能够实现GPS的不停车收费技术的精确收费，而目前正由于车载设备成本高，使该收费系统受到一定的限制，因此车载收费电子地图匹配方法具有重要的研究价值。目前关于国外道路收费方面技术资料大多限于对收费系统的介绍，而收费地图匹配技术介绍很少。常规的用于导航系统中的地图匹配方法是通过投影距离和车辆行驶方向与路段矢量方向差值加权的方法来进行地图匹配，判断出车辆行驶的路段。由于这些方法需要完全的地图路段信息较大的计算能力和存储单元，从而增加了车载设备的成本。另外需要判断匹配的路段较多，对信号可靠性的要求也比较高。加之道路收费自身的一些特点，上述方法不适合道路收费使用。因此需要对基于GPS的不停车收费地图匹配方法进行大量研究和试验。38 青岛理工大学毕业设计（论文）1绪论1.2道路收费的发展历程自从道路收费开始应用与人们的日常生活中以来，收费技术经历了从低级到高级，从功能简单到功能完善丰富的过程。首先是无任何设备的人工收费方式，发展成为现在的半自动收费和电子收费。道路收费技术发展历程如图1-1所示。人工收费是指完全靠收费员来分辨车型、发卡、开票验证、按里程计收费用、保管现金、统计数据和结帐的收费方法。从20世纪60年代以来，很多地方就采用这种简单的收费办法。目前，中国的一些收费公路（特别是低等级公路）仍广泛采用这种收费方式。半自动收费是指在道路入口处由人工识别车型、发卡，但在出口处通过仪器设备来读卡、人工进行收费、显示收费金额、付费放行等的收费方式。电子不停车收费（ElectronicTollCollection，简称ETC）系统是国际上正在努力开发并推广普及的一种专门用于公路、桥梁和隧道的新型电子自动收费技术。它包括三种技术：基于DSRC（DedicatedShort—RangeCommunication，短程无线通信）电子收费技术、基于ANPR（AutomaticNumberPlatRecognition，车牌识别）电子收费技术及基于GPS（GlobalPositioningSystem全球定位系统）电子收费技术。ETC的三大特点：无需人、不停车、无现金。图1-1道路收费发展历程38 青岛理工大学毕业设计（论文）1绪论首先，高速公路收费由传统的人工收费到不停车非现金收费经历了漫长的过程，虽然国内外目前均是多种收费方式并存的情况，但不停车电子收费必然成为未来收费方式的主流发展方向，世界各国均在努力发展适合本国国情的不停车收费系统，并在努力促使其标准化。在国际上，美国、欧洲、日本很早就针对不停车收费系统中的研发技术、工程实施、标准规范进行了深入研究。在美国，电子不停车收费方式已经成为美国回收公路投资和养护费用的高效率手段，最著名的联网运行电子不停车收费系统是E—Zpass系统。葡萄牙的ViaVance电子收费系统可以算作欧洲具有代表意义的联网电子收费系统之一，事实已证明，ViaVance电子收费系统是既有利于道路使用者又有利于道路运营商的有效收费手段。国际标准化组织（ISO）、欧洲准化委员会（CEN）也在开展不停车收费领域的技术标准化工作。其次，联网收费项目已经成为国内、国际不停车收费的主流方向，但在电子收费系统从引进我国到实施，经过了一段时间的实践，目前也取得了一定的进展。如今国内的ETC系统采用的基本都是基于DSRC技术的不停车收费系统。由于早期的不停车收费系统的引进采取公路管理部门自主引进的方式，没有一个统一的标准，各个地区不停车收费系统的技术标准不尽相同。至于车道结构、通信网络、监控系统等等更是各行其是。至今我国的基于DSRC的技术标准也还在制定和完善中，仍未公布。如今，我国公路收费系统从各路段独立收费的状态步入了联网统一收费、通行费多业主拆分的时代。在实施区域联网收费的进程中，标准的不一致，协调上的困难，使我国的不停车收费系统逐渐暴露出了一些问题:1）各个城市的不停车收费系统需要在地区内得以统一，比如说首先在省的范围内。这就需要扩大规模，路网规模的扩大，将导致ETC系统规模的扩大，使一次性投资增加，周期更长，风险更大。2）现有的不停车收费系统造价比较高，许多关键的设备需要引进。3）国内己建的收费站中，大多数的入口收费站和出口收费站的交通量小，车道数量少，如果考虑单独辟出一条专用的ETC车道在建设上比较困难，在利用率上又不够经济。38 青岛理工大学毕业设计（论文）1绪论总之，我国的ETC项目进展并不顺利，有些大项目碰到了很复杂的协调问题，有些项目正式运行后因多种原因无法扩大规模，用户群较小。与半自动收费方式相比，电子收费系统的运行市场化特色更浓一些，要求运营公司有很高的商业运作能力。在现阶段，各方面的精力主要集中在人工半自动的区域联网收费工作上。1.3GPS收费系统的原理与特点电子收费技术从实现的技术手段上可分为3种：短程无线通信（DedicatedShort-RangeCommunication，DSRC）电子收费技术，车牌识别（AutomaticNumberPlatrecognition，ANPR）电子收费技术及卫星定位（VehiclePositioningSystem，车辆定位系统）电子收费技术。1.3.1DSRC电子收费技术1.DSRC电子收费技术的定义DSRC电子收费技术是近几年国际上比较成熟的收费技术。它是利用安装在路侧的路边设备（R0ad—SaidUnit，简称RSU）与行驶在收费道路的车辆上的车载装置（On—BoardUnit，简称OBU）联系起来，司机不停车、不使用现金而支付通行费用的一种收费技术。它可以应用在城市道路收费、公路收费及大桥和隧道收费中。2.DSRC电子收费系统的构成DSRC电子收费系统包括前端系统和后台系统组成：其中前端系统包括OBU车载单元、DSRC路边设备、车辆分类系统、执法系统等；后台系统主要实现车辆通行费的结算、清分等功能。3.DSRC电子收费系统的工作原理整个DSRC电子收费系统大致的运行过程是：1）用户前往发行安装部门，申请安装车载装置，预缴通行费或设立事后付费帐户，相应的信息被存入车载装置中，然后该车便可以上路行驶。2）在进入收费站时，车辆按规定限速通过收费车道。DSRC路边设备通过天线与车载单元进行双向通信，收费操作在通信的过程中同时完成。收费操作的具体步骤包括根据车型按照收费标准确定收费额、核对余额、帐号信息、有关结果通知对方等。如果一切无误（剩余余额充足或帐号有效时），则正常结束收费操作（改写余额、记帐等）。否则（剩余余额不足或帐号无效时）启动执法系统记录其车辆号码，以保证通行费最终能被征收，不致流失。38 青岛理工大学毕业设计（论文）1绪论3）每次收费操作，都需将收费操作的相关信息递交后台系统，后台系统对这些信息按照不同类别分别进行处理。正常收费信息可以积累汇总，产生相应的收入报告，同时，事后付款方式的收费数据将定时（或实时）递送给后台系统，以便生成转帐清单向金融机构请求支付。不正常收费信息将立即通知执法系统，以确保统一及时处理。后台系统除了接收收费车道呈递的信息外，还向收费车道发送相关信息，如收费标准、帐号“黑名单”等。4）在系统中，金融机构负责提供金融服务，包括管理事后付款帐户及收费帐户，处理各种转帐、清帐事务，还参与车载装置的发行、安装。同时，它也向系统提供一定的信息，如不良信息帐号的“黑名单”业务结算结果等。4.DRSC优缺点DRSC电子收费是利用安装在路侧的路边设备（RSU）与行驶在收费道路车辆上的车载装置（OBU）联系起来，司机不停车、不使用现金而支付通行费用的一种收费技术。它具有如下优点：1）收费精确。对于采用DSRC电子收费技术组成的道路收费系统，它可以对通过设有天线的收费站点的车辆进行精确收费、误差极小、并可以结合图像抓拍等技术，对于未安装车载装置（OBU）的车辆进行严格控制。2）技术成熟，系统完整性好。DSRC电子收费系统是经过多年发展的成熟技术。在采用该技术的条件下，道路收费系统可以适应多种实际应用要求，包括多种费用支付要求，且系统灵活性好，可以与其它应用比较密切地结合。同时存在以下不足：1）系统的前期投资大。该技术要求用户在相应的车辆上安装车载OBU，导致前期投资比较大。一般单片式OBU价格为200～300元，双片式则多达500元左右。2）违章处理弊端。要求用户必须安装OBU，否则按违章车辆处理。用户的配合问题也是该系统有效实施的关键。3）需要安装龙门架。一方面增加大量投资，另一方面，如果是在城市道路上会有碍市容，同时在市区中安装龙门架存在地理位置限制、影响交通等问题1.3.2ANPR电子收费技术1．ANPR电子收费技术的定义车牌识别技术（AutomaticNumberPlateRecognition，简称ANPR）是基于图像处理与光学字符识别（OCR）的汽车牌照自动识别技术，主要运用“不同车辆不同牌照”38 青岛理工大学毕业设计（论文）1绪论的思想概念来识别车辆。ANPR电子收费技术是指在收费区内不设收费站，司机或者车主需要预先预付交通道路通行费，并将汽车牌照输入到计算机的数据库中。当车辆行使到收费区及出口时，系统利用车牌识别摄像机拍摄车辆照片，并将图片传输至中心，通过ANPR软件自动识别车辆，并与计算机数据库内的交款车辆进行比对，已付款的车辆进行核销，未付款的车辆会被记录下来，待工作人员核实之后，就会送出罚单。2．ANPR电子收费系统的构成ANPR电子收费系统由前端采集系统和后台收费管理系统组成。前端采集系统包括视频摄像机（获取车辆图像）和照明灯（用于拍摄光源补充）以及相应的视频传输设备等，后台收费管理系统主要实现车辆通行费的管理等功能。3．ANPR电子收费系统的工作原理整个ANPR电子收费系统的工作流程如下：1）司机或者车主需要通过通行费支付系统预先预付交通道路通行费。预付手段有4种：路侧自助付费，因特网付费，手机付费和特约银行付费。在付费的同时需要将车主自己的车牌号码输入收费管理系统中，以便保存到相应的车牌数据库中。2）当车辆行驶到收费区内及出入口时，ANPR电子收费系统就利用安装在收费区域边缘（出入口）的固定视频摄像机或移动视频摄像机拍摄通过的车辆照片并通过一定传输线路将视频流传至收费管理中心。3）收费管理中心通过ANRP软件读取图像、识别车牌以及与数据库内交款车辆的车牌进行匹配，已付款的车辆进行核销，未付款的车辆会被记录下来，待工作人员核实之后，就会送出罚单。对于那些不能识别的车牌将有中心系统通过人工的办法来识别，对于那些未付款的车辆将会保存它进入收费区域配有时间、日期以及位置的图片，以便作为处罚的证据。4.ANPR电子收费系统概况车牌识别技术在道路收费的应用主要是辅助收费系统的执法功能，在半自动收费和电子收费中都是利用ANRP来实现逃费抓拍系统（VideoEnforcementSystem，简称VES），而真正采用ANPR作为一种收费技术是2003年2月伦敦市政府在中心区实施道路拥挤收费。除伦敦外，采用相似技术的有安大407ETR（ExposTol38 青岛理工大学毕业设计（论文）1绪论Route）电子收费系统以及英国Darford桥梁电子收费系统。随着车牌识别精度的改善，相信这种收费技术将会有越来越大的发展空间。同样，车牌识别技术在我国道路收费的应用主要是辅助收费系统的执法功能，在半自动收费和电子收费中都是利用ANRP来实现逃费抓拍系统。但是伦敦拥挤收费已经在我国引起强烈反响，我国的北京、上海、广州、南京、深圳等城市已经开展了城市拥挤收费的研究，相信ANPR电子收费技术在不久的将来会有助于解决中国城市拥挤问题。5.ANPR电子收费技术的优缺点ANPR电子收费技术适用于预交费的情况，可实行对经过的车辆进行自动扣款收费，能实现不停车收费，它有如下特点：1）ANPR收费系统只需在固定识别点安装摄像机（需要配套的支撑装置，如电线杆），路侧设施投人相对比较少，且ANPR收费技术不需要安装车载设备，减免了道路收费用户的投人；2）通过ANPR软件识别车牌并能添加相应的时间、地点信息，便于按里程、滞留收费。同时存在以下弊端：1）自动车牌识别技术虽然发展的时间比较长，但是识别率不高，是制约ANPR收费的关键所在；2）车牌识别技术的性能指标（识别率）不能满足道路收费的实际需要，系统的稳定性需要进一步提高；3）运营管理复杂，不能完成现场扣款；4）天气对摄像机捕获车辆图像的影响比较大；5）ANPR收费系统功能扩展性是有限的。1.3.3基于GPS的不停车收费技术1.基于GPS的不停车收费技术的定义它利用卫星定位系统（GlobalPositioningSystem，简称GPS）及全球移动通信系统（GlobalSystemforMobileCommunication，简称GSM），通过与车载装置的通信，进行不停车收费。2.基于GPS的不停车收费技术的构成该系统包括GPS接收装置,用于接收GPS数据,定位车辆;电子地图及数据库,其中包含所有收费高速公路及其出口的空间位置信息及高速公路段落名称、段落长度、所属业主及收费标准等属性信息;缴费卡,可持卡缴费及传递数据。3.工作原理38 青岛理工大学毕业设计（论文）1绪论基于卫星定位和无线接入技术的新一代收费系统，通过自动记录车辆行驶的位置和里程，综合考虑道路收费车辆参数和道路收费因素，自动计算车辆的通行费，由无线传输网络将数据传输到收费管理中心，根据相关公路收费政策，对车辆收取通行费。卫星定位收费系统包括智能车载收费设备（OBU）、稽查系统、管理中心3大部分组成，共同组成1个完整的卫星定位收费网络，如图1-2所示。图1-2卫星定位网络收费图该系统通过GPS接收卫星信号定位车辆当前位置,定位数据与电子地图结合应用路径辨识算法等判断车辆当前位置是否属于收费高速公路,如位于收费公路,记录虚拟入口时间、入口站号,接着等待出口,通过GPS定位当汽车离开公路时记录出口时间,出口站号,通过入口站号与出口站号到数据库中查询其它属性信息,并增加收费记录。费用支付可采用实时支付或先使用后支付两种方式。实时支付可用缴费卡与车载装置相连,当车辆驶离高速公路时,实时扣取缴费卡中的相应费用,余额不足限定值时提示充值;38 青岛理工大学毕业设计（论文）1绪论先使用后付费方式可定期到指定机构交纳费用。无论哪种收费方式均可在缴费时传递收费数据,然后依据收费数据通过银行或指定收费机构对收缴费用进行划分。定期对收费数据备份和更新电子地图及数据库。4.系统特点（1）适用性好基于GPS的不停车收费系统利用现有车道即可,不需要对车道改进,不受道路扩宽,增加车道等的影响,为采用该收费方式的汽车专留一个车道,未安装该种收费系统的车辆走人工收费车道,随着该收费方式的普及,逐渐取消所有人工收费车道。整个过程全部利用现有车道。另外由于该系统不需要在道路上建设收费设施,因而不受道路施工的影响。当整个路网有新建高速公路时,更新电子地图数据库即可。（2）可移植性强该收费系统在小范围内实验成功后可快速进行大规模推广,有利于自动收费系统的快速发展。可首先对一个小行政区内车辆进行实验,实验成功后,大范围效仿相同方式进行即可。具有建设周期短,硬件设施投入少,易于大规模推广的特点。（3）可扩展性好该收费系统可与GPS卫星导航系统共同开发,并可进行功能扩展,提供其它服务功能,如车辆跟踪、信息查询、出行路线规划等。在日本超过60%的新车出厂时就已安装了车辆导航系统,可以预见,随着更多汽车企业的介入,导航产品市场将逐渐成熟,导航产品前景广阔,与GPS相关的其它服务功能正在悄然兴起,基于GPS的收费系统与GPS服务产品共同开发将更能调动道路使用者的积极性。5.基于GPS的不停车电子收费技术的优缺点基于GPS的不停车电子收费技术是利用GPS及GSM，通过与车载装置OBU的通信，进行不停车收费。它的特点如下：1）GPS电子收费系统可以将路旁设备降低到很少，无需龙门架，不会因为安装龙门架而影响市容美观和道路交通，更适合于城市道路有效空间的利用。同时降低了设备的投资，在地理位置受限制的地方，这种技术的优势更为明显。38 青岛理工大学毕业设计（论文）1绪论2）提供灵活的收费区域定义和灵活的费用支付。DSRC收费技术在土地使用模式发生变化、收费区域需要改变时，克服传统基础设施改变存在比较大的困难。而GPS通过改变虚拟收费点的定义，非常容易实现。3）车载装置可由市场直接提供，GPRS／GSM以及GPS技术规格己标准化，很多厂商具有生产制造能力，系统供应商较难垄断车载设备市场，故很容易跨平台或系统使用。4）车载装置不仅是用作支付收费道路通行费的工具，它只要载人相关的应用软体，即可产生多用途，如：车载导航，车队管理，移动商务，车辆保全，交通信息等。5）车载装置易扩展为移动商务基础平台的终端设备，并衍生其它商机。6）具有长距离通信的优点，收费机制较不受空间限制，容易实时地在整个区域内按里程收费及实施匝道收费，具备收费策略调整弹性。同时基于GPS的不停车收费技术存在以下不足：1）用户的OBU成本高，如果由此造成用户的数量减少，可能影响系统的有效运行。2）车载电子地图的更新复杂。3）如果系统设计得不合理，将会涉及到用户的隐私问题，这是很多国家暂时不考虑这种方式的一个原因。4）在技术上，相对于DSRC电子收费技术要新。GPS技术是成熟的，但应用在不停车收费方面比较少。在城市道路中GPS定位信号容易受到建筑物的阻挡，影响车辆的定位，需要辅助系统支持。5）GPS电子收费系统的运营需要配套法规、政策和严厉的惩罚制度，特别是针对那些“违规车辆”以及故意损坏车载装置的行为。1.3.4DSRC、ANPR和基于GPS的电子收费技术的性能比较及分析DSRC收费技术、ANPR收费技术及VPS收费技术，这3种电子收费技术都各有自己的优缺点。下面将从路侧设施成本、车载装置成本、技术成熟性、收费准确率、按车型收费、按里程或滞留收费、电磁干扰、景观影响、天气影响、外埠车辆收费、功能扩展、兼容性和可维护性等方面来比较，见表1-1。38 青岛理工大学毕业设计（论文）1绪论表1-1三种收费技术的性能比较特性指标DRSC收费技术ANPR收费技术GPS收费技术路侧设备成本高较低不需要车载装置成本较低（约500元）不需要高（约5000元）技术成熟性成熟比较成熟不成熟收费准确率高一般高按车型收费好差好按里程、滞留收费一般好好电磁干扰有无有景观影响有有无天气影响无严重无运营管理简单复杂（不能完成现场扣款）简单外埠车辆收费方便不方便比较方便功能扩展宽窄宽兼容性较差一般好可维护性较差一般好DSRC电子收费技术和基于GPS的不停车收费技术主要应用于公路收费，而ANPR电子收费技术主要用于城市拥挤收费。由以上3种收费技术的原理及技术性能比较分析可知：1）ANPR电子收费技术不成熟、且车牌识别精度不高，是制约这种技术发展的最大障碍。2）DSRC电子收费技术成熟、且广泛使用，但需要高额费用来建设、维护路边设备。3）基于GPS的不停车收费技术比较新、且车载装置投人较高，但其灵活的收费区域定义和费用支付方式及毋需建设龙门架等路边设备已受到全球的关注。38 青岛理工大学毕业设计（论文）1绪论4）对一个较大范围的路网进行收费，基于GPS的不停车收费技术则可能较合适。以德国为例，其实施的货车收费系统将按其行驶里程与重量来计算应缴的道路通行费，由于其收费范围较大，收费点分布较广，采用DSRC电子收费技术的难度较大，费用也高，VlX3可能是较好的选择。对一条相对独立的收费公路，桥梁或隧道而言，DSRC电子收费技术可能是最佳选择，它用在类似新加坡的较小范围且单一、集中的市区道路收费也很合适。5）由于收费分区与计价方式复杂，这类系统通常必须具备一套全国性或区域性的收费系统。再进一步设想，对于一个收费区的不同道路按不同道路的等级实施差别费率时，基于GPS的不停车收费技术则更具有优势。1.4本文研究内容及结构基于GPS的不停车收费技术代表着未来道路收费的发展方向，精确的地图匹配决定该收费系统能否实现成功收费。本文概述了各种常用的地图匹配算法，并就各种地图匹配算法进行系统的分析和对比，在此理论基础上，提出基于GPS的不停车收费系统的地图匹配算法，本文以自驾车从黄岛到济南为例，对收费用地图中的关键点即收费点进行定义，并提出了一种专门用于收费的地图匹配算法。具体内容如下：1.基于GPS的不停车收费系统的原理和特点概述，并就各种ETC技术对比分析。2.系统的提出各种地图地图匹配技术。3.以黄岛前往济南为例，对基于GPS地图进行重新定义，并给出了新的地图匹配算法。4总结。38青岛理工大学毕业设计（论文）2地图匹配技术38 青岛理工大学毕业设计（论文）2地图匹配技术2地图匹配技术2.1地图匹配的基本原理将用导航定位方法得到的车辆位置或行驶轨迹与车载的电子地图道路数据相比较、匹配，从而找到车辆所在的道路，并且显示出车辆的实时位置的软件修正技术叫地图匹配（MapMatching，MM）。地图匹配过程可分为两个相对独立的过程:1）寻找车辆当前行驶的道路；2）将当前定位点匹配到车辆行驶的道路上。地图匹配的两个条件是高精度的数字地图和车辆在路网中行驶。如果条件成立，就可以把定位数据和车辆运行轨迹同数字化地图所提供的道路位置信息相比较，通过适当的匹配过程确定出车辆最可能的行驶路段以及车辆在该路段中的最大可能位置。反之，则地图匹配将产生错误的位置输出，并可能导致系统性能的严重下降。一般认为用于匹配的数字地图误差不应超过15m。由于陆地车辆在除了进入停车场等之外的决大多数时间都位于道路网络中，因此使用地图匹配技术的条件是满足的。在图2-1中，点A、B、C都是GPS观测点，显然这些观测点都没有准确的定位在道路上，地图匹配的任务就是通过一定的方法将这些点校正到道路的中心线上。现在地图匹配的算法有很多，但根据利用信息不同，大体上可以归结为两大类：1）基于几何信息的地图匹配方法；2）基于拓扑关系的地图匹配方法。基于几何信息的地图匹配方法有三类：点到点的匹配；点到线的匹配；线到线的匹配。前两种可视为搜索问题，最后一种可视为统计估计问题。38 青岛理工大学毕业设计（论文）2地图匹配技术图2-1地图匹配示意图1）点到点的匹配点到点的匹配就是搜索地图数据库中的节点、形状点或自定义的点距离GPS观测点最近的点作为匹配点。该方法简单易行，实现快速，但是匹配结果与路段上待匹配的点集关系密切，待匹配的点越多，匹配效果越好。匹配形式如图2-2显示。图2-2点到点的匹配在图4-2中，A1、A2、A3、A4、A5、B1、B2、B3都是GPS观测点P的待匹配点。从图中可以看出，距离PA3是最短的，按照点到点匹配方法，应该将车辆匹配到A3点，但从图中直观看出，P点匹配到线段B上似乎更为合理些，因为P更靠近线段B。缺点在于匹配点少时匹配结果不准确。2）点到线段的匹配点到线段的匹配就是搜索所有可能的线段，以GPS观测点到线段距离为判断依据，观测点到条线段距离最近的那条线段作为匹配路段，观测点到匹配路段的投影点即为匹配点。这种方法同样比较简单，也很直观，但该方法得到的结果的不足在于匹配结果会出现来回摆动的情况，当GPS观测点距离多条路段的距离相等时就无法进行路段匹配了，匹配形式如图2-3所示。38 青岛理工大学毕业设计（论文）2地图匹配技术图2-3点到线段的匹配在图4-3中，P1、P2、P3、P4是连续的GPS观测点，它们的匹配结果是这样的：（P1—B1），（P2—A1），（P3—A2或P3—B2），（P4—B3）。可以看出，匹配结果出现了在线段A、B间摇摆的情况，还有观测点P3无法确定匹配点。点到点的匹配、点到线的匹配都是仅仅利用了当前观测点位置进行匹配，没有充分利用历史和未来的观测点位置，有很大的局限性。3）线到线的匹配线到线的匹配就是将一系列GPS观测点拟合到道路网相应的路段中，拟合的标准就是观测点形成的折线到路段之间的距离，距离最短的为匹配路段。连线间的距离可以有很多种定义的方式，如定义两折线X、Y的距离为取它们间最近点的距离，即。匹配的示意图如图2-4（a）所示。图2-4线到线的匹配（a）38 青岛理工大学毕业设计（论文）2地图匹配技术在图2-4（a）中，GPS观测点出现了一个离群点P，按照上述的匹配方法，GPS观测点被匹配到路段B上，这显然不合理，合理的匹配应该被匹配到线段A上。两折线间距离的定义还可以如下，按照这样距离计算方式同样也会出现像图2-4（b）那样的错误匹配了。图2-4（b）线到线的匹配在图2-4（b）中，待匹配路段A的坐标为（6t，6），待匹配路段B的坐标为（3，6t），GPS观测点连线的线段P的坐标为（6t，3）。按照上述距离计算方式，，至于的计算，如果距离定义有正负定义（定义线一侧的点到线的距离为正，则另一侧的点到线的距离就为负），则；如果距离定义是取绝对值，则通过计算可得。按照匹配方法，就要选择B为匹配路段了，但从图上直观的看，选择A作为匹配路段似乎更为合理。在图中，P的长度为6，如果要求以使得GPS观测点正确的被匹配到A上，通过计算，P的长度至少是15，这显然延迟太大，达不到实时校正车辆位置并正确显示的要求。上述的三种地图匹配方法相对来说都是计算简单，仅利用了数字地图的单一信息，不能保证任何时候都能得到正确的匹配结果，无法满足真正地图匹配的要求，因此根据这三种基本地图匹配方法衍生出来了许多比较实用的地图匹配算法。2.2常用地图匹配算法地图匹配的常用算法有很多，比如最短距离算法、基于拓扑关系的算法、概率统计算法、模糊逻辑算法、相关性算法等等。下面对其中的几种进行简要分析。38 青岛理工大学毕业设计（论文）2地图匹配技术2.2.1最短距离算法最短距离法是一种基础的匹配方法。该方法根据道路属性，预先设置一个匹配阈值，在数字地图数据库中的所有或部分路段中，计算当前获取的GPS数据与各道路路段之间的距离以及GPS数据在该道路路段上的最短距离点，将在阈值范围内各路段的匹配距离进行比较，得到一条距离最短的路段，则该道路为GPS点的匹配路段，该最短距离点为GPS点的匹配点。最短距离法简单易行，能在很大程度上消除地图匹配中各种误差产生的影响，但它没有考虑GPS数据接收中的各种情况及道路的地形特征，通常作为一种基本方法，与其他匹配方法结合来得到好的效果。2.2.2概率统计算法基于概率统计的地图匹配同样是一种基础的匹配方法。概率统计算法的基本思想是根据GPS接收到的数据，首先设置一个置信区域，并从中提取用以匹配的道路位置信息，依据已有匹配结果的概率统计，经过比较判断，确定车辆在这一置信区域内的匹配路段。基于误差模型，根据接收的GPS定位数据建立缓冲区。按照统计理论，定位误差椭圆可推导如下:（2-1）（2-2）（2-3）其中，是椭圆长半轴取向与正北方向的夹角，a和b是误差椭圆的长、短轴，和分别是GPS东向和北向测量误差的标准差，是协方差，是单位权值的后验方差。通过改变的值来调整误差椭圆的大小，获得不同的可信度。在车辆导航系统中，利用GPS的接收模块的参数来定义误差椭圆。误差椭圆的定义如图2-5所示。38 青岛理工大学毕业设计（论文）2地图匹配技术图2-5误差椭圆的定义该算法利用误差椭圆确定了误差区域，以便从数字地图数据库中提取候选路段的信息，从而减少候选路段的数目，缩短地图匹配的计算时间，但它没有历史信息进行有效利用，当道路较为密集的时候，可能会出现匹配点在几条路段间反复跳跃的情况，与基于拓扑关系的地图匹配方法相结合能得到较好的效果。2.2.3基于拓扑关系的算法拓扑空间关系是一种对空间结构进行明确定义的数学方法。GIS中，常将空间事物抽象成点、线、面等几何要素，并在点、线、面之间建立拓扑关联关系。具有拓扑信息的矢量数据是网络分析必要的数据来源。数字地图数据包含：1）节点：表示空间对象所在的位置，或者线段的起始、终止点，它具有特定的拓扑性质。2）形状点：表示线、面经过的点，不具拓扑性质。3）线（弧线）：起始与终止点为节点、并且具有若干形状点的有序点集。4）面：由若干弧线相连的封闭曲线围成的区域称为面，面以弧线的形式表示，但通过代码与弧线区别，且其内部填充方式可以设置。建立道路网拓扑关系的一般步骤为：1）数据预处理：数据压缩（剔除冗余数据，提高计算速度）和自动断链（使整幅图图形无相交或自相交链）。2）结点匹配：建立点、弧段关联关系。3）追踪多边形：以左转算法或右转算法跟踪，生成多边形，建立多边形与弧段的关系。4）多边形嵌套关系的生成，建立多边形嵌套关系树，即找出多边形包含的“岛屿”，建立多边形与多边形之间的关系。38 青岛理工大学毕业设计（论文）2地图匹配技术5）具有嵌套关系多边形的关联弧段的左右面的编号调整及多边形内点自动生成。基于拓扑关系的匹配算法是在道路层网络拓扑关系的数据基础上进行的，是利用历史轨迹对地图数据库的道路信息进行实时的模式识别的一种方式。拓扑关系在电子地图中一般是指节点和路段之间的拓扑关系。在一段时间内，车辆行驶的区域是有限的，而且这个区域的道路也是有限的，因此在区域中建立的道路实体对也是有限的。电子地图足够精确并且具有路网拓扑完整性是地图匹配能够正常工作的前提。由于受车辆速度的限制，在一定的时间内，车辆只能驶经有限的路段上。如下图2-6所示，假设当前时刻车辆行驶在道路1上，由于速度等各种因素的存在，在下一时刻，车辆只可能出现在道路2、道路3或道路4上，即与道路1相连的道路链上，不可能直接跳到道路5或道路6上，如下图2-6所示。图2-6道路拓扑关系基于拓扑关系的算法通过对前一次匹配结果和车辆前进方向的分析，利用道路层的网络拓扑关系，来确定当前车辆的匹配位置。但是，这种方法也仅利用了电子地图的单一信息，同时，其匹配效果有时也会受到拓扑关系质量的影响，空间拓扑范围越大，匹配效果就越差。2.3地图匹配方法分析最短距离投影法逻辑简单、速度快、实时性好、所需内存空间少，但它没有考虑GPS数据接收中的各种情况及道路的地形特征，通常作为一种基本方法，与其他匹配方法结合能得到较好的效果。概率统计算法考虑了道路的地形特征，与其他方法结合能较好的解决匹配时道路中的合点与并行路段的问题，缺陷在于没有充分利用移动目标行驶轨迹前后的相关性。38 青岛理工大学毕业设计（论文）2地图匹配技术基于拓扑关系的算法对电子地图的精确度依赖性太高，而且该算法仅仅建立了结点与结点、结点与道路、道路与道路之间的拓扑关系。但在实际的道路通行过程中，还有很多的交通规则，这些规则限制了移动目标只能在某些道路上运动，而不能在受限制的道路上运动，这些交通规则我们统称为交通关系。两条道路如果仅仅是物理上连通是不够的，车辆是否能够从一条道路运动到另一条道路还要遵守交通规则。因此，要建立良好的道路拓扑关系，还应建立完整的交通关系以符合实际交通情况。基于以上这些情况，地图匹配算法的研究应该朝着多手段综合运用，相互补充、相互完善、精确化方向发展，对算法本身的准确性应该有一个检验机制，以最大程度保证算法的可靠性。2.4地图匹配的应用在智能交通系统中，车辆控制、紧急救援、路径诱导、出行信息服务，公交调度等各种应用都需要精确地位置信息，地图匹配结合准确的空间地图数据对车辆位置信息进行校正，为各种智能化应用提供准确的位置信息，使得它们更加可靠。1.在车辆定位导航系统中的应用地图匹配可以为车辆定位导航系统提供准确的位置信息，便于在地图上正确地显示车辆位置，向司机提供准确的行驶指令，并提供给司机从起点到目的地的最短路线，或最短行驶时间的路线，并为司机提供路线周围大型建筑物如银行、商店、加油站、旅馆等位置信息为用户的，还为用户提供道路的拥堵情况，方便用户及时调整路线，避免浪费时间和改善交通拥堵情况。2.在车辆控制中的应用地图匹配由于可以提供比原始数据更为准确的位置信息，所以在车辆安全应用方面起到重要作用。例如，地图匹配可以应用于车辆巡航控制（VehicleCruiseControl）系统中，具有地图匹配模块的系统可以根据电子地图所表现的路网中道路的曲率和拐点来自动的调整车辆的巡航速度。另外，精确的地图匹配还可以应用于车道保持（LaneKeeping）技术。虽然基于图像识别的车道保持技术已经相当成熟，但是由于恶劣天气对该系统的严重影响使得重新考虑一种新的方法成为一种必要。如果车辆定位精度能够达到10cm或者更小，那么当高精度的车道级别的地图出现时，车道保持以及其他安全技术将会变成可能。毫无疑问，没有地图匹配的协助，这将是个不可能完成的任务。38 青岛理工大学毕业设计（论文）2地图匹配技术3.在道路收费上的应用在道路收费问题上，由于卫星定位与地图精度的精确度无法满足卫星收费的技术要求，因此需要优化的地图匹配方法来使之实现，这是本论文研究的重点。也是下文所要展开研究的问题。38青岛理工大学毕业设计（论文）3基于GPS的不停车收费系统地图匹配方法38 青岛理工大学毕业设计（论文）3基于GPS的不停车收费系统地图匹配方法3基于GPS的不停车收费系统地图匹配方法3.1基于GPS不停车收费地图匹配的作用基于GPS的不停车收费系统的匹配方法是通过对GPS采集的位置点信息与收费地图上的虚拟收费路段进行匹配，来判断当前车辆是否在收费路段上行驶，以判断是否对车辆进行收费，若需要进行收费，则记录收费信息和车辆的基本信息并发送到后台管理中心进行扣费处理。程序在接收到GPS定位数据信息后，先做译码处理，在提取位置、方向、速度及其他一些环境数据信息，最后将车辆位置信息和收费地图上路段通过一定的匹配方法进行精确地匹配，从而可以清晰区分收费路段和非收费路段，达到较准确地收费效果。GPS的定位精度、电子地图的绘制精度是影响GPS收费路段匹配准确性的主要因素。而只有在两者都达到一定精度条件下才能进行准确无误的匹配。但由于高速公路上行、下行车道间距离较小，通常只有5m左右，而目前GPS定位的精度仅在20m左右，此外受车载设备成本的限制，车载设备上不可能使用精度非常高的GPS接收机，而且也不可能使用精度非常高的电子地图。因此单纯依靠GPS定位和提高地图精度，很难区分上下行两个距离很近的点，因而对两条道路匹配混乱，导致收费路径的错误判断。要想实现定位信息与收费路段的精确匹配，首先要解决的就是地图匹配问题。3.2基于GPS的收费地图的定义卫星收费电子地图不同于一般车载导航所用地图，这是一种专门用于道路收费的具有特定定义的地图，该地图包含收费路段的地理位置信息、形状数据信息、拓扑关系数据信息和属性信息等。对于收费用电子地图来说，基于我国高速公路大多采用封闭式收费系统的特点，即在收费公路所有出入口设立收费站，高速公路对外界呈“封闭状态”，车辆按进出收费站出入口进行收费，因此车载收费地图的定义需要围绕这些特点进行定义。38 青岛理工大学毕业设计（论文）3基于GPS的不停车收费系统地图匹配方法收费电子地图根据存放位置的不同分为两部分：一是存储于车载单元中，对这部分的要求是尽可能的精简属性信息，以节约成本；二是存储在管理中心数据库中，此部分中包括了GPS定位收费所需要的详细全面的地理信息、包括路段编号、路段名称、路段长度、路段类型、限速、有节点编号、左节点编号、高速公路名称、高速公路公司代码、收费类型等。3.2.1道路收费地图收费关键点及收费路段定义本文所描述的车载收费地图由关键点和关键路段组成的，所谓关键点和关键路段是收费道路上的对道路走向和计费起到关键作用的点和路段。通过对现有高速公路布局和收费情况的分析，我们定义3种类型的关键点和3种类型的路段。入口点、出口点、经过点和入口路段、出口路段、经过路段。入口点是车辆经该点进入收费道路的点，和高速公路入口收费站对应；出口点是车辆经该点离开收费道路的点，和高速公路出口收费站对应；经过点，对于匝道收费站而言，是匝道和主路的交汇点，该点同时属于主路和匝道；由此定义入口点和经入口匝道与主路交汇的经过点组成的路段为入口路段；出口点和经出口匝道与主路交汇形成的经过点组成的路段为出口路段；经过点与经过点连接组成的路段为经过路段，多个相连接的经过路段组成主路路段。3.2.2主线站出入口特殊处理主线收费站和匝道收费站不同，主线收费站出入口都是在主路上，为定义保持一致需要对主线收费站出入口做特殊处理，添加一个入口路段和出口路段。入口路段是从主线站入口开始沿道路方向在入口和下一个经过点的中间位置附近的道路上添加一个新的经过点，新经过点一端连接主路入口、另一端连接下一经过点，从入口到新经过点形成主路入口路段；同理出口路段是从主线站出口开始沿道路相反方向，在出口和上一经过点的中间位置附近添加新经过点，形成主路出口路段。注意新经过点位置应均匀分布，不能过于靠近下一经过点和出入口。3.2.3收费关键点和收费路段属性值的定义关键点属性值的定义是为了区分出入口关键点，不能用来区分判断出入口，对于车辆进出收费道路起到辅助识别作用，入口关键点属性值为0；出口关键点属性值为1；经过点属性值为2。本文定义2种路段属性值，路段识别属性值和路段长度属性。路段识别属性值：出入口的识别是收费路段识别最重要的部分，出入口识别靠设置路段识别属性值来实现，路段识别属性值定义为3种，收费路段入口识别属性值为0；收费路段出口识别属性值为1；中间路段识别属性值为2。路段长度属性值：考虑到将来进行按里程收费扩展，设置路段长度属性，这里是指各个点之间道路的实际长度值，而非我们定义的关键路段的长度。38 青岛理工大学毕业设计（论文）3基于GPS的不停车收费系统地图匹配方法图3-1是以黄岛到济南的行程各路段定义简图。我们定义从黄岛到济南途中经过管家楼收费站进入前湾港1号疏港高速公路，再从枢纽立交出入口进入沈海高速公路；途径马店立交进入青银高速高速，最后在济南北收费站下高速。在此段高速公路收费道路中，对道路中的收费关键点和进出口路段作如下定义。1为管家楼收费站入口，此为入口关键点2为管家楼收费站。1119826青银高速5沈海高速4青兰高速321012图3-1黄岛到济南行程路段定义图图中各关键点的名称、属性及对应的属性值如下表3-1所示。表3-1名称、属性及属性值表编号名称属性属性值1管家楼收费站入口入口关键点02管家楼收费站出口出口关键点13黄岛枢纽立交经过点24胶南枢纽立交经过点25马站立交经过点26济南北收费站入口入口口关键点038 青岛理工大学毕业设计（论文）3基于GPS的不停车收费系统地图匹配方法7济南北收费站出口出口关键关键点18匝道经过点29济南北收费站出口路段110管家楼收费站入口路段011济青高速非收费路段无12中间路段中间路段23.2.4地图精简收费的准确性取决于能否准确判断出是否行驶在收费路段上，这就要求收费电子地图必须保持高的地图精度。由于考虑到车载系统受成本限制，其硬件资源非常有限，因此要求在满足收费功能要求的条件下尽量缩小存储地图的数据量，即车载设备只存储必要的用于收费的基础信息，大量的时效性数据的查询和计算量较大的操作都放到后台服务器上进行，因而需要对电子地图数据进行裁剪，以便节省车载单元内存资源，提高运行效率。同时其数据结构也必须更加符合嵌入式设备显示、运算和分析的要求。地图信息的精简包括下面两个方面：1.电子地图的形状信息精简电子地图可通过精简地图数据进行压缩，去除不必要的形状连接点，保留路段的拓扑结构，这样可大大的减少数据量，节省数据存储空间和减少程序计算量。2.电子地图的属性信息的精简电子地图属性信息的精简就是首先确认收费地图所必需的信息，去除不必要的其他信息。收费系统中费率计算分2种情况，瘦客户端计费和胖客户端计费，瘦客户端计费是将费率计算放在后台完成，胖客户端计费将费率计算前段完成，从而减少后台的计算压力，2种费率计算方式下，车载端存储的信息也不一样。瘦客户端收费地图保密与地图匹配相关的数据信息包括：路段编号，路段做节点坐标，路段有节点坐标，路段类型。胖客户端收费地图数据的定义要考虑增加收费类型表和费率表，根据收费类型，查询费率表内相关费率，基本表包括：路段编号，路段名称，路段长度，路段左节点坐标，路段右节点坐标，路段类型，收费类型。38 青岛理工大学毕业设计（论文）3基于GPS的不停车收费系统地图匹配方法基于GPS的不停车收费系统所用费率计算方式是瘦客户端计费，车载设备只存储必要的用于收费的基础信息，大量的时效性数据的查询和计算量较大的操作都放到后台服务器上进行，这样可以减少车载设备成本并且可以减少程序计算量，提高效率。3.3基于GPS的不停车收费系统的地图匹配方法3.3.1地图匹配中搜索范围的确定在电子地图的精度和GPS定位精度在目前的技术水平下难以有较大提升的条件下，对匹配方法进行优化是能否成功实现卫星收费的关键环节。以GPS定位点G（x,y）为中心，一个值为半径的区域内，在收费电子地图上搜索是否有收费路段存在及收费路段在此范围内，如果有收费路段存在，则进行判断。搜索范围的选取非常重要，范围过大，容易造成误判，且加大计算量，如近距离平行的主辅路,使辅路行驶的车辆误收费。如果搜索范围过小，收费路段点丢失。GPS数据接收频率1次/秒，如果车速过快，搜索范围会跳过路段上的一些节点，造成漏点。影响匹配准确性。本文采用根据车辆行驶速度动态收本文采用根据车辆行驶速度动态调整搜索范围的方法。搜索范围的选取应考虑以下两个原则:1）搜索范围和GPS定位精度及地图精度有关,搜寻范围应大于GPS定位精度和地图精度的最大值。这样才能保证所有节点都不会遗漏。2）实际操作搜索范围可根据车速在一定范围内自动调节。车辆在高速公路行驶的特点,快速120km/h,而GPS定位数据以1次/秒的频率接收。为不遗漏对任何路段的节点进行判断,在这种情况下,算法判断节点范围至少为50m。高速公路双向路段的横向距离通常大大小于50m。由此可见车速和判断范围的选取对地图匹配的准确性影响很大。随车速增加,判断范围增大,车速减小,判断范围减小。这样既保证在速度慢时匹配的精确,又使速度快时不遗漏节点。搜索匹配范围是车辆行驶时，以车辆GPS定位点为中心点，一个值为半径的区域内在收费电子地图上搜索关键点进行匹配。搜索范围的选取应考虑到GPS的精度误差，道路宽度等因素。选取过大会造成误判且加大计算量。另外，随着车速的加快，车速每秒行驶的距离大于匹配范围，跳过关键点，就会造成漏点。因此匹配范围的选取和车速有一定的关系。本文提出了在保证基本匹配范围的条件下，匹配范围随车辆行驶速度动态调整的方法。匹配范围分为两个部分，基本值和变化值，实际搜索范围为两者之和。38 青岛理工大学毕业设计（论文）3基于GPS的不停车收费系统地图匹配方法（1）基本值的确定搜索范围基本值的选取应考虑以下两个原则:一是搜寻范围应大于GPS定位精度的最大误差值，以保证在GPS存在误差条件下不丢点;二是搜索范围必须完全覆盖关键点所在道路同向所有车道。由此可知，基本的搜索范围为GPS误差值与关键点所在道路宽度之和。假如GPS定位误差为20m，道路为两车道组成，每车道3.75m，路侧间隙为各为0.8m，则搜索范围为：（3-1）其中m表示GPS定位误差，n表示车道数，l表示车道宽度，a表示路侧间隙以济青高速公路为例，假设GPS的定位误差为18，该高速公路为双向四车道，路宽3.75m，路侧间隙为0.8m则search_scope=18+4×3.75+2×0.8=34.6m（2）动态搜索匹配范围值的确定搜索范围可根据车速在一定范围内自动调节。经过反复测试，车辆在36km/h速度下，搜索基本值能够满足匹配要求;在车速高于36km/h，搜索范围需要动态随车速的变化。搜索范围变化值具体描述如下:令初始搜索范围基本值:search_scope=35m，实际搜索变化值为bound。当速度V＜36km/h，搜索范围不变，为基本值，bound=search_scope;当速度V≧36km/h，实际搜索范围（3-2）所以在V≧36km/h的情况下，若在时速为80km/h，上例的实际搜索范围bound=V×1000/3600+search_scope=80×1000/3600+35=57.2m通过对系统实际运行情况分析，这种匹配范围的定义是比较合理的。3.3.2卫星收费地图匹配算法描述下面是搜索范围方法的详细描述。参数定义如下：i,j—i为任意路段号；j为任意一节点号;fee_status—当前路段收费标志值1：行驶在收费路段；当前路段收费标志值0：没有行驶在收费路段；search_scope—GPS位置点：初始搜索范围值；bound—实际变化的搜索范围；—当前i位置的行驶速度；38 青岛理工大学毕业设计（论文）3基于GPS的不停车收费系统地图匹配方法—GPS位置i的坐标；—任意搜索到的节点i的位置坐标；—收费路段i上的节点位置坐标；—收费路段i,左节点号为u,右节点号为v；—i收费路段类型，入口值为0，出口值为1；—i收费路段长度/km；Fee（all）—总通行费用/元；Node_Fee（j）—收费路段上的节点号；Fee（i）——收费路段费率/（元/km）；设定收费标志值fee_status区分当前车辆是否在收费路段上：fee_status=0——不在收费道路上；标志值fee_status=1——在收费道路上。下面是匹配方法的详细描述：方法:步骤1初始化fee_status=0,i=0,j=0,Fee（all）=0,search_scope=35m。步骤2接收GPS定位信息,坐标值,速度v,接收频率为1次/秒。步骤3根据当前车辆的行驶速度v确定搜索范围bound。当v<36km/h,bound=search_scope；。步骤4以GPS位置点为中心，搜索范围bound为半径，在收费地图上搜索路段数据，判断收费点和收费路段；如果有节点Node（i）在点搜索范围bound内，首先，判断是否是收费路段上的节点；再判断是否是收费路段上的节点：进入步骤5；步骤5如果是收费节点38 青岛理工大学毕业设计（论文）3基于GPS的不停车收费系统地图匹配方法，这里分两个情况处理,车辆当前未在收费路段上，即fees_tatus=0;和车辆已经行驶在收费路段上即fee_status=1的情况。1）当fee_status=0时，判断该点Node_feei（x,y）属于哪一个收费路段，接着再判断是否该收费路段的路段类型是入口路段0，如果是,进入收费道路开始计费过程。否则返回前面，继续判断。置fee_status=1;记录入口路段ID：返回步骤2。否则返回步骤2。2）当fee_status为1时,进入收费路段后接着判断是否通过节点号,判断该节点Node_Fee（j）和上个收费节点Node_Fee（j-1）是否存在邻接关系,如果存在,车辆当前行驶在这个收费路段上,进行计费,最后判断该收费路段是出口等于1,之后设置fee_status=0,车辆离开收费路段,收费结束,返回步骤2;否则返回步骤2。如果；如果（type）=1；置fee_status=0;记录路段出口ID号；计费Fee（all）=Fee（all）+（L）Fee（i）；收费结束,返回步骤2；否则计费Fee（all）=Fee（all）+（L）Fee（i）；返回步骤2；否则返回步骤2；程序结束。上述流程中费用计算是按里程收费的计算方法,对于按路段出入口收费的情况下,只需在收费路段出口处,将记录的入口ID和出口ID在费率表中匹配,即可得到入口到出口整条路段的通行费用Fee（all）。下图3-2即为上数算法的程序框图。38 青岛理工大学毕业设计（论文）3基于GPS的不停车收费系统地图匹配方法图3-2地图匹配的程序框图38 青岛理工大学毕业设计（论文）3基于GPS的不停车收费系统地图匹配方法济青高速公路（现为国家高速公路网规划的一条东西横向线，编号G20青银高速公路，是青岛—银川高速公路的东段）是中国高速公路15年15项最具影响力重大工程候选项目之一。济青高速公路全长318公里，西起济南市大桥路，东至青岛市北郊的西袁庄，横贯山东半岛17个市、县（区）连接济南、淄博、潍坊、青岛等重要工业城市，穿越5条国道、15条省道。济青高速公路一直是山东最繁忙的高速公路，但也成为山东最为拥挤的高速公路，山东省的车祸大约一半发生济青高速上，追尾事件时有发生，因此我国交通部决定开通济青南线，但是南线并未起到分流作用，北线依旧车满为患，虽有过将北线拓宽的提议并得到各方的同意，但由于牵涉面较广，何时拓宽并没有确切的时间。济青高速在各个出入口出收费站一般都有基于DSRC的ETC车道，虽大大解决了拥挤的程度，但依旧不能很好地解决道路拥堵问题，如果基于GPS的ETC能够应用在济青高速上，将大大缓解拥挤程度，减少交通事故量。下面以济青高速为例，研究分析上述地图匹配算法是否能够实现准确收费。下图3-3为济青高速公路的北线和南线地图。图3-3济青高速南北线从青岛济南有多个收费站，基于GPS的不停车收系统要想成功实现不停车收费，就要对车载地图进行一些处理，首先是路线上个关键点的定义，青岛到济南横贯山东半岛17个市、县（区）38 青岛理工大学毕业设计（论文）3基于GPS的不停车收费系统地图匹配方法，所以至少要定义17个关键点，所谓收费关键点，就是定义高速公路上的收费点，从而可实现车辆在经过该点时成功实现扣费，达到收费的目的，除此之外还要对地图进行一些精简，在满足收费功能要求的条件下尽量缩小存储地图的数据量，即车载设备只存储必要的用于收费的基础信息，大量的时效性数据的查询和计算量较大的操作都放到后台服务器上进行，因而需要对电子地图数据进行裁剪，以便符合嵌入式节省车载单元内存资源，提高运行效率，同时其数据结构也必须增加。此功能的实现可以在GISGAS平台上实现。进行完上述操作后，便开始进行车辆的实际行驶路线与地图上的虚拟收费站进行匹配收费，假设自驾车从青岛到济南，途中经过若干个收费站，其基本流程算法如下：车辆行驶在在路上，车载GPS接收机接收GPS信号，通过前面的计算可知以GPS定位点G（x,y）为中心，若形式在该路线上的车辆的速度低于36km/h，则使用静态的搜索范围，若使用前面的计算数据，则搜索范围为34.6m，若速度高于36km/h，则使用动态数据，计算公式见本节前面所给公式,。在地图上搜索路段数据，判断收费路段和收费节点，若为入口路段，则开始收费。若为经过节点，如果该节点与前一收费节点存在邻接关系，则在收费路段上继续进行收费，若为出口点，则路径收费完成。实现扣费，路程结束。3.4该算法可行性实验基于GPS不停车费技术作为一项新技术，虽并没有在中国广泛应用，但是中国相关方面的专家对此做了大量研究和试验，在京津塘高速公路搭建的卫星定位收费试验系统中，通过采用本文描述的车载收费地图的定义方法能够大大的节省了存储空间和提高计算效率和匹配的可靠性京津塘高速公路全长142.69km，由北京到塘沽，跨北京，河北和天津3个省市，共有11个收费站。普通电子地图实际路段有上千个，采用本方法共定义70个关键点和85个关键路段。如马驹桥收费站到采育收费站只需判断识别4个关键点、3个路段，即可完成收费过程和得到路径信息大大减少识别失误率，提高计算效率和识别的准确性。在此次卫星定位收费试验系统运行中，进行了共有300多台车辆参与，历时6个月的运行试验，试验系统运行初期，路段识别方面出现的错误基本是由于车载地图关键点位置选择不当引起的，主要集中在收费站和桥梁附近，GPS信号容易受到遮挡，特别在车速较快的情况实验运行后期由于京津塘高速公路部分收费广场扩建造成关键点处于匹配范围之外，关键点丢失，造成匹配错误38 青岛理工大学毕业设计（论文）3基于GPS的不停车收费系统地图匹配方法这些问题在采用本文部分的方法对关键点进行修正，出现的问题得到了很好的解决收费电子地图和与之对应的路段识别方法组成的系统软件部分通过了国家权威部分的软件测试，得到了认可。所以本论文中所用的地图匹配算法是具有可行性的。38 青岛理工大学毕业设计（论文）4总结4总结基于GPS的不停车收费技术的地图匹配技术是当前应用比较热门的一项技术，直接决定了卫星收费技术能否成功实现收费。当下各国收费技术竞争相当激烈，中国有必要站在技术前列，掌握该技术的主动权。本文概述了各种常用的地图匹配算法，并就各种地图匹配算法进行系统的分析和对比，在此理论基础上，提出基于GPS的不停车收费系统的地图匹配算法，本文以自驾车从黄岛到济南为例，对收费用地图中的关键点即收费点进行定义，并提出了一种专门用于收费的地图匹配算法。此算法已被证实具有可行性。以下是对本论文的总结：1）对道路收费技术的发展历程做出简介；2）对各种电子收费技术的原理及各自的优缺点进行了进行了分析和对比，得出结论，基于GPS的不停车收费系统具有最大的发展前景和发展空间；3）系统的分析了各种地图匹配算法并进行比对；4）针对GPS不停车收费的地图匹配算法中的地图进行了重新的定义，并对该地图进行了精简；5）不足之处是对GPS收费地图的从匹配到收费整个收费流程并没有完全把握，不过我会在以后的工作中努力研究，并向老师请教。基于GPS的不停车收费技术有望在不久的将来占领中国市场，因此车载电子地图匹配的研究可以在本文的基础上进行进一步的研究和改进，使该技术能够应用与中国未来道路收费中。38青岛理工大学毕业设计（论文）致谢38 青岛理工大学毕业设计（论文）致谢致谢首先诚挚的感谢我的论文指导老师高志彬老师。他在忙碌的教学工作中挤出时间来审查、修改我们的论文。导师渊博的专业知识，严谨的治学态度，精益求精的工作作风，诲人不倦的高尚师德，严以律己、宽以待人的崇高风范，朴实无华、平易近人的人格魅力对我影响深远。不仅使我树立了远大的学术目标、掌握了基本的研究方法，还使我明白了许多待人接物与为人处事的道理。再感谢我的班主任刘尊民老师以及教过我的所有老师们，你们严谨细致、一丝不苟的作风一直是我工作、学习中的榜样；你们循循善诱的教导和不拘一格的思路给予我无尽的启迪。最后要感谢四年中陪伴在我身边四年的同学、朋友。尤其是我的舍友徐俊玲、许艳芳等，她们在我做论文的过程中给与我极大的帮助并提出了较多的宝贵建议，有了她们的支持、鼓励和帮助，我才能顺利完成论文，并充实的度过了四年的学习生活！最后再感谢我的父母，是他们的细心养育和教导才成就今天的我，我定会在结束大学生涯踏入社会后辛勤工作，报答他们也报答社会！38青岛理工大学毕业设计（论文）参考文献38 青岛理工大学毕业设计（论文）参考文献参考文献[1]胡松利,徐国军,李翠.联网电子不停车收费（IETC）系统的研究[J].交通与计算机，2005，23（4）：14-16.[2]杨继成,施莉娟.ETC技术原理及其在高速公路收费中的应用[C].上海市公路学会第6届年会学术论文集,2003:242-245.[3]郇鹏,张仲义.基于射频技术的高速公路不停车收费系统[J].交通运输系统工程与信息，2004，4（2）:121-124.[4]Bor-ShennJeng,etc.Anintegratedserviceforbackendsystemsintaiwanelectronictollcollectionproject[C].Proc.ofInternationalConferenceonITS-2000,2000.IntelligentTransportationSystemConference,2001,8.[5]王笑京．国家“十一五”科技支撑计划“国家高速公路联网不停车收费和服务系统”可行性研究报告[R]．-IIs．：交通部公路科学研究院，2006.[6]OperationalBenefitsofElectronicTollCollection:CaseStudyJ.Tramps.Engorge,1997,123（6）:467-477[7]张北海.国内电子不停车收费系统发展现状.国际智能交通,2005（6）:1-10.[8]许宏科.高速公路收费系统理论及应用.北京:电子工业出版社,2003:253-270.[9]朱书善,李亚檬,宋向辉,等.基于GPS的电子不停车收费车载设备系统开发[J].交通信息与安全，2009,27（5）:127-130.[10]王东柱，朱书善，李亚檬，刘楠.卫星收费系统GPS定位信息和路段匹配方法研究[J].交通信息与安全2010年3（28）:12-2938'