第40卷 计算机学报 Vol.402017论文在线出版号No.53 CHINESEJOURNALOFCOMPUTERS OnlinePublishingNo.53本课题得到国家自然科学基金项目（(No. 61472287,61572370);湖北省自然科学基金重点项目（2015CFA068）;武汉市科技计划项目（2016060101010047）资助.吴黎兵(通讯作者)，男，1972年生，博士，教授，计算机学会会员（E200011921s）,主要研究领域为网络管理、无线传感器网络、分布式计算等，E-mail:wu@whu.edu.cn.范静，男，1989年生，博士生，主要研究领域为车联网、分布式计算.E-mail:fanjing@whu.edu.cn. 聂雷，男，1989年生，博士研究生，主要研究领域为无线传感器网络、车联网，E-mail:lnie@whu.edu.en. 崔建群，女，博士，教授，主要研究领域为计算机网络、高性能计算，E-mail:jqcui@126.com. 邹逸飞，男，1994年生，本科生，主要研究领域为车联网、无线传感器网络，E-mail:Karltherine@whu.edu.cn一种车联网环境下的城市车辆协同选路方法吴黎兵1),2)范静2)聂雷2)崔建群3)邹逸飞2)1)(武汉大学软件工程国家重点实验室, 武汉430071)2)(武汉大学计算机学院, 武汉430071)3)(华中师范大学计算机学院, 武汉430070)摘要 随着智能导航设备的不断普及，越来越多的驾驶员使用智能导航设备来选择自己的行驶路径。现有的选路方法往往采用城市道路地理信息、历史行驶信息以及交通信息中心提供的实时交通状态来进行路径的规划。而城市车辆数目增加使得车辆间的相互作用逐渐成为了影响车辆行驶时间的主要因素之一，现有的选路方法已经无法满足现今城市的导航需求。因此有必要设计一种能够考虑选路车辆间相互作用的新型选路算法来应对这种新的变化。本文首先对车辆运动过程中的相互作用进行了研究，并量化了车辆选路行为对其他车辆的影响，进而提出了一种车联网环境下的城市车辆协同选路方法(CoRP,CollaborativeRoutePlanning)。该方法通过收集并分析联网车辆的行驶规划信息，在为车辆提供更适用于实际交通情况的路径规划方案的同时减少车辆选路行为对其他车辆带来的负面影响。仿真实验表明，相较于现有的选路方法，该方法能够提升城市车辆选路的协同性，降低了18%~30%的道路最大滞留车辆数目，并减少了14%~29%的车辆整体行驶时间开销，在很大程度上缓解了城市道路拥塞的情况。关键词 车辆导航系统；智能交通系统；车辆选路问题；路径规划；车联网中图法分类号TP311论文引用格式：吴黎兵，范静，聂雷，崔建群，邹逸飞, 一种车联网环境下的城市车辆协同选路方法,2017,Vol.40,在线出版号No.53WuLi-Bing,FanJing,NieLei, Cui Jian-Qun,ZouYi-Fei,ACollaborativeRoutingMethodwithInternet ofVehiclesforCityCars,2017,Vol.40,OnlinePublishingNo.53ACollaborativeRoutingMethodwithInternetofVehiclesforCityCarsWULi-Bing1),2)FANJing2)NIELei2)CUIJian-Qun3)ZOUYi-Fei2)1)(StateKeyLaboratoryofSoftwareEngineering,WuhanUniversity,430071)2)(ComputerSchool,WuhanUniversity,430071)3)(ComputerSchool,CentralChinaNormalUniversity,430070)Abstract WiththeincreasingpopularityofGPSSystemsandvehiclenavigationdevices, anincreasingnumberofdriversareaccustomedtoplottingtheir travel routesthroughusingintelligent navigationdevices. Formostexisting routingmethods, the results of pathplanning are merely depending onurbanroads’ geographicinformation, historical travel informationor thereal-timetrafficstatusprovidedbytrafficinformationcenters.However, sincethenumber of vehicles is continuouslyincreasingintheurbanenvironment, theinteractionamongvehicleshasbecomeoneofthemost significant factorsthat affectsthetravel time. Thus, thoseexistingroutingmethodsarenotsuitableforthedemandsofcurrenturbannavigation.Toaddressthisnewchallenge, itis网络出版时间：2017-05-06 12:08:46网络出版地址：http://kns.cnki.net/kcms/detail/11.1826.TP.20170506.1208.004.html2 计算机学报 2017年necessarytodesignanimprovedroutingmethod, whichcanconsider themutual interactions amongurbanvehicles. Recently, theVehicularAd-HocNetwork(VANET)hasbeenoneofthemost promisingachievementsforthedevelopmentofIntelligentTransportationSystem(ITS)intermsofvehicularinformationtransmission.InVANET, takingadvantageofvehicularonboardnetworkdevicesandDedicatedShort RangeCommunications(DSRC)protocol, thevehiclescanachievereal-timecommunicationwithothervehiclesorurbaninfrastructures.Moreover,vehiclescansharetheirroutingplanningandretrievereal-timetrafficinformationfromtheIntelligentTransportationSystemCenter via these communicationtechnologies. Nevertheless, it is still a serious andrealisticchallengetomakemoreaccuratepredictionofvehicles’routingplanningwhenitconsidersthedynamicchangesof futuretrafficstatusinroad; especiallythechangesareresultedfromthecurrent routingplanning.Therefore, this paper proposes a collaborative route planningmethod(CoRP), whichis more rational andadaptableforurbanvehiclestoplot their travel routes. Inthispaper, wefirstlygiveananalysistothevehiclerunningprocessandtheinteractionsamongvehicles.Basedontheaboveanalysis,wedrawaconclusionthatthetravel process of urbanvehicles canbe convertedintoa queuingproblem. Furthermore, we quantifytheinteractionamongthoseurbanvehicleswhiletheyaremakingtravel planning, andthenput forwardaquantifyalgorithmtoevaluatetheirinteractions.Atlast,wecomeupwithanoptimalmethodtargetingatminimizingtotaltimespend(TTS)forroutingvehicles. Giventheproposedmethod,CoRPcanreducethenegativeinfluenceoneachvehicleintheroutingprocess, andcanprovidemorerational andpractical routingplansforurbandrivers.Thesimulationshowsthat CoRPcandecreasethenumberofretardedvehiclesontheroadby18%~30%, andreducethetotal timespendof all vehiclesby14%~29%whencomparedtosomeclassical routingmethods.Therefore, theproposedCoRPcanenhancethecollaborationamongvehicles,anditismorepracticalfortherealurbanenvironment.Keywords vehicle navigation system; intelligent transportation systems; vehicle routing problem; routeplanning;internetofvehicles1引言随着城市的发展，人们对交通出行的需求越来越高，城市中的车辆数目也越来越多。中国国家统计局的数据表明，截至2015年底，全国民用汽车保有量达到1.72亿辆1。汽车在给人们的生活带来便利的同时，其数量的几何增长也引发了一系列的交通问题。例如，高德地图2015年年度拥堵延时指数2数据显示出，受城市车辆拥堵的影响，在交通高峰期车辆出行往往需要花费2倍于畅通状态下的时间才能到达目的地。因此，如何减少城市车辆行驶时间，缓解道路拥堵成为研究的一大重点。缓解城市交通压力主要有两类方法：一是降低交通需求，即通过限号限行等手段控制城市道路上12015年国民经济和社会发展统计公报http://www.stats.gov.cn/tjsj/zxfb/201602/t20160229_1323991.html22015年度中国主要城市交通分析报告http://report.amap.com/download.do的车辆数目来减少交通压力。虽然该方法简单易行，但与社会发展规律存在冲突；二是提高交通运输效能，例如增设新的道路提高城市道路容量或者通过现代化交通调度技术提高现有道路的运输效率。其中增设道路、提高基础交通设施容量方法虽然简单，却需要消耗大量的人力物力资源。因此使用现代化交通调度技术，合理配置现有资源，提高交通系统运输效率成为目前解决交通问题的主要手段。如今，智能交通系统(IntelligentTransportationSystem, ITS)在提升交通系统运行效率方面正发挥着越来越重要的作用。其中车辆导航系统(VehicleNavigationSystem,VNS)是ITS的重要的组成部分。导航系统主要通过使用有效的选路算法来为车辆制定合理的行驶路径，进而降低车辆在道路上行驶的时间，提高城市道路的整体吞吐量。传统的车辆导航系统大多依赖静态道路信息或历史交通数据进行路径规划，但是城市车流的高度动态性使城市交通环境变得越来越复杂，也使得这些信息难以准确反映城市道路的通行状态。车载自组织网络（VehicularAd-HocNetwork，论文在线出版号No.53 吴黎兵等：一种基于车联网的城市车辆协同选路方法 3VANET）是智能交通系统在车辆信息交互方面发展的产物，通过专用短程通信技术（DedicatedShortRangeCommunications，DSRC），车与车、车与设施之间能够建立起实时的无线通信手段。同时，借助车载终端等移动网络接入设备，车辆能够实时与其他车辆或者城市智能交通系统进行网络通信。目前基于车载网络的选路算法能够使用这些实时通信技术来获取道路的实时通行状态，但却没有考虑车辆路径规划过程本身对其他车辆行驶状态的影响，这将可能导致车辆集中选择当前通畅的道路，而在一段时间之后形成拥堵。因此利用这些实时通信技术，分享车辆的行驶路径规划，并对道路未来通行状态的变化加以考虑，进一步提高选路算法的选路合理性就成为了一个亟待解决的问题。针对以上问题，本文提出了一种在车联网环境下基于共享车辆路径规划信息的车辆协同选路算法(CoRP,CollaborativeRoutePlanning)。与现有算法相比，CoRP算法有如下特点：（1）通过对城市车辆运动过程的分析，将车辆通过城市道路的过程归约为车辆的排队问题。（2）利用车载网络通信设备的实时通信功能，在车辆共享其路径规划方案的基础上，考虑了道路车辆选路过程中的相互作用。（3）实现了以最小化全局车辆行驶时间为目标的车辆路径规划方法。仿真实验表明，相对于现有算法，CoRP算法能够更准确地反映目标车辆的实际行驶状态，减少道路滞留车辆数目和全局车辆行驶时间开销，提高城市交通运输效率。本文第2节介绍了车辆选路问题现有的解决方法；第3节本文给出了车联网下协同选路方法的基本步骤；第4节通过分析车辆的行驶过程给出了本文方案的设计依据；第5节详细描述了本文方案的具体策略和实施细节；第6节使用实验仿真对本文方案的性能进行了验证；第7节是本文的总结以及对下一步工作的展望。2相关研究早期研究中，车辆导航系统主要使用静态的选路算法，即以道路的地理信息或历史行驶数据作为决策依据来为车辆规划行驶路径，相关的研究可以追溯到二十世纪七八十年代，技术已经非常成熟[1]。目前大量使用的商用车载导航系统，如Google地图、百度地图、高德地图，大多都包含该功能。在道路条件简单时，静态选路算法能够在一定程度上反映道路的行驶情况。但随着城市车辆数目增多，车辆对道路通行时间的影响逐渐增大，静态的地理信息或历史行驶数据不再能准确地反映城市不同时间段内车辆经过某条道路的行驶时间开销。因此研究者提出了时变车辆选路问题(TDVRP,vehicle routingproblemwithtime-dependent traveltimes)，即车辆在同一条道路但不同时间段内具有不同的通行开销。文献[2]的研究表明，基于时变行驶信息的选路算法在解决小规模选路问题时能够很好地降低车辆进入拥堵道路的概率。文献[3]使用禁忌搜索算法配合时变行驶信息对车辆行驶的最低排放问题进行了研究。文献[4]则使用了遗传算法对时变车辆选路问题进行了研究。虽然基于时变行驶信息的选路方法比基于静态数据的选路方法能够更加准确地反映道路的真实状态，但受限于历史数据的迟滞性，其仍然无法准确地表达实际环境的实时路况。随着交通系统的发展，比如GPS[5]和车辆识别[6]等技术的引进，导航系统可以准确地获得道路的实时交通信息。大量研究者开始对基于实时交通信息的选路问题进行研究。文献[7]的研究表明使用实时的道路行驶信息对道路进行规划可以有效降低道路拥堵的几率，进而降低车辆发生碰撞的可能性，提高车辆行驶的安全性。文献[8]研究了导航系统提供的实时信息对人们进行路径的选择行为的影响。与此同时，车联网的迅速发展也让车辆与车辆、车辆与交通调度中心能够进行实时交互。文献[9]通过车辆间的通信，实现了交通信息的共享，并利用实时交通信息进行最优路径计算。文献[10]在车联网基础上提出了一种考虑车辆隐私的选路算法，能够在使用车间实时信息交互提升驾驶体验的基础上避免产生隐私问题。随着通信技术的进步以及车载终端配置的普及，使用智能导航设备的车辆日益增加，越来越多的车辆开始根据道路的实时状态进行路径规划。但是，当大量车辆同时进行路径规划时，很有可能根据当前交通状态同时选择同一条道路，从而在该道路造成拥堵，并极大地增加这些车辆实际通过该道路的行驶时间。因此，合理的选路算法应该要考虑到车辆选路过程对道路交通状态的影响。早期考虑车辆选路过程对道路交通状态影响的研究主要集中在高速公路场景。在高速公路场景中，车辆的行驶时间基本取决于车辆的密度，因此4 计算机学报 2017年车辆选路过程对道路的影响能够通过统计分析车辆的密度来进行较为准确的量化。例如文献[11]和文献[12]使用基于车辆分流的控制方法，通过对路径通行时间比例的控制达到均衡道路负载和提高行驶效率的目的。文献[13]引入博弈论，通过调整道路的通行费用，来完成道路负载的均衡。文献[14]则利用信息素浓度对道路的负载进行动态反馈，进而提高算法对大规模车辆选路的适应性。城市场景中，由于车辆在道路行驶的过程中受车辆与交通信号的多重影响，直接对其进行量化存在一定难度。对于这种问题，目前已有的一种方案是使用仿真方式对城市场景的行驶过程进行量化。但是仿真过程需要大量计算，因此该方案多用于部分紧急情况的预案设计与决策支持，较少用于实时选路系统[15]。另一种解决方法则是根据道路的变化，对路径进行重新规划来降低车辆选择同一条道路的影响[16]。比如文献[17]通过使用车载网络接入设备，实时获得整体道路行驶状态，并不断变更路径，降低拥塞发生的概率。然而不断的重复选路会对整个导航系统造成极大的负担，因此文献[18]进一步将重选过程变更为分布式方案，使之能够在一定程度上规避重选带来的计算开销。但是，这依然无法从本质上降低重选方案的计算复杂性。此外，考虑到重选过程进行的时间需要一定间隔，确定合适的重选间隔也是一个难以解决的问题。较小的重选间隔会增大整个系统的计算量，而较大的重选间隔则很难达到避免拥塞的目的。3 CoRP算法设计目标与流程现有选路算法几乎没有考虑选路的车辆对未来道路行驶状态的影响。因此当大量车辆采用同一种选路算法时，现有选路方案会导致车辆集中选择当前通畅的道路，容易在一段时间之后形成拥堵。而考虑选路车辆本身影响的基于仿真量化和基于重选路方法的算法存在消耗大量计算资源的问题。为了解决以上两类算法的缺陷，本文提出了一种车联网环境下的城市车辆协同选路算法CoRP。该算法主要需要达成以下三点目标:（1）尽可能降低选路车辆由起点到达目的地的时间开销。（2）体现车辆选择路径过程对相关道路未来车辆通行状态的影响。（3）能够以较低的计算开销满足不同车辆的选路需求。目标1为选路算法的基础需求，要求算法在路径最优化过程中使用趋向于最小化行驶时间的目标函数。以往的研究大多是在选路车辆数量较少，不足以对道路行驶状态产生较大影响的条件下才能较好地达成该目标。但是，一旦当需要选路的车辆数目增加到足以影响道路行驶状态的程度时，这些算法往往不能达到满意的效果。因此新设计的算法需要额外考虑目标2。目标2对算法的要求是目标函数需要考虑其他车辆选路过程对道路行驶状态的影响。在车联网得到足够发展之前，车辆的选路系统往往无法获得道路中其他车辆的信息，车辆的选路结果也不能反馈到其他车辆的选路决策过程中。因此，过去研究大规模车辆路径规划算法往往使用交通信号等指导性信号对车辆实施调度。随着车载设备与智能交通系统的不断发展，驾驶员已经能够及时获得道路的行驶状态。实际生活中已经有大量能够实时反馈道路行驶状态的地图应用，例如Google地图，百度地图等等。但是单纯地考虑道路当前的状态，无法避免选路车辆同时选择当前通畅的道路，并在一段时间之后形成拥堵的情况。为了解决上述问题，选路算法中需要设计一种表达车辆路径选择对未来道路交通状态影响的机制。目标3要求选路算法拥有较为简单的路径代价计算方式，且尽可能避免多次迭代操作。为了达成以上3点目标，本文提出的CoRP算法需要完成以下三个要求：1. 以车辆在道路上的行驶时间作为评价车辆通过道路的行驶开销的主要依据。2. 行驶开销评价方法能够反映车辆选路行为对道路交通状态的影响。3. 不进行复杂的迭代，而是采用单次选路过程确定最优路径。CoRP的基本工作流程如图1所示。论文在线出版号No.53 吴黎兵等：一种基于车联网的城市车辆协同选路方法 5队列通过模型交通调度系统车载导航设备 车载网络接入设备交通信息通信系统 选路算法 选路策略道路n驾驶员道路n+1交通规划系统道路信息管理系统车辆1 3 2图1 CoRP算法流程在CoRP算法中，车辆使用车载网络终端连接至城市交通规划系统。驾驶员通过车载智能导航设备提交选路需求，并使用车载网络终端从交通规划系统获得选路结果。该方法主要的交互过程包括3个步骤:(1)当车辆试图由起点进入城市道路系统向某一目的地行驶时，驾驶员需要向导航系统输入对应的目的地。结合车载设备的GPS定位系统，车载导航设备会将驾驶员输入的信息转换为起点和终点的起止点对（origindestinationpair，OD-pair[19]），并利用车载网络接入设备提交给交通规划系统。(2)交通规划系统在收到车辆提交的起止点对之后，将会根据道路信息管理系统中存储的道路信息，结合其他已经选定行驶路径的车辆对道路可能产生的影响，使用合适的选路策略规划一条满足车辆选路要求的行驶路径反馈给发起请求的车辆。(3)车辆收到规划路径后，经由驾驶员或者车载设备确认后向道路信息管理系统反馈最终确定的行程。道路信息管理系统收到确认的行程后会使用该行程信息对相关道路的行驶状态信息进行更新。在CoRP算法以上几个步骤中，步骤(1)需要车辆具有GPS和地图系统，并能够接入网络。随着智能终端的普及，目前已经有大量诸如Google地图、百度地图等成熟的解决方案被广泛使用，因此该步骤的内容不做更多探讨。步骤(2)需要一种对应的选路算法。该选路算法首先要能反映和量化其他选路车辆对未来道路通行状态的影响，其次要有依赖以上量化结果的优化策略。步骤(3)需要研究车辆选路过程对整个道路网络未来交通状态的影响，并设计一种量化和表达该影响的方法。本文将在后续章节依次描述以上内容的解决方案。4 CoRP算法下行驶过程的量化分析停车线辅道iγ图2 城市道路的结构示意图研究城市环境中道路交通状态和其他车辆的路径规划对当前车辆行驶过程的影响，首先需要分析城市道路的结构以及车辆在道路上的行驶方式，并对车辆的行驶过程进行建模。在城市环境中，道路一般包含多个车道，每条车道在交通信号的调度下经过一段辅道与其对应的下一条道路连接。图2所示为城市环境中的一种典型路口的结构。受交通信号控制的道路中，车辆离开道路的时间被交通信号分割为不同周期。每一个周期按照控制信号的状态可以分为绿灯、黄灯和红灯3个状态。当车辆行驶至道路停车线附近时，如果对应车道为绿灯状态，那么车辆可以自由通过道路。而当对应车道为黄灯或红灯状态时，则需要减速并停留在道路末尾停车线内。表1变量含义列表变量示例 变量说明i 车辆编号p,q 道路编号iv 车辆i在道路中行驶的最大速度ie 车辆i进入道路的时间点it 车辆i抵达道路队列的时间点io 车辆i实际离开道路的时间点ih 车辆i离开道路占用的通行时间ig 车辆i由进入道路直到到达停车线消耗的时间( , )ipq i 车辆i通过道路p与道路q间辅道消耗的时间il 车辆i到达队列时队列前方已有车辆的数目RT,GT,YT 交通信号控制灯红色、绿色、黄色信号长度0T 交通信号控制灯绿灯信号起始时间点pL 道路p的长度, pql 道路p延伸至道路q的辅道长度()pt Q t时刻道路p的车辆队列中车辆的数目0 1[ , ]pt t W 时间0t 至1t 内抵达道路p路口的车辆数目6 计算机学报 2017年( )px G x时刻道路p进入道路车辆数目的密度函数( )px X x时刻道路p离开道路车辆数目的密度函数文献[20]使用动力学模型对车辆的行驶状态进行抽象，描述了车辆通过道路过程中的动力学轨迹，如图3所示（图3和后文所使用的主要变量及其具体含义见表1）。停车线行驶方向T0T’0GT ηGTiτ iok η =k η =( )p iτ Θ图3 车辆通过道路的动力学轨迹车辆在进入道路后，按照大致均匀的速率行驶。一段时间后，车辆会受交通控制信号的控制，进入由路口停滞车辆组成的车辆等待队列。当交通信号由阻塞变为允许通行后，车辆会跟随前方车辆在交通信号允许通行的周期内按照进入路口时的顺序依次离开道路。对某一车道中所有车辆的行驶轨迹进行归纳，可以抽象得到如图4所示的车辆行驶过程。图4中车辆离开道路存在的主要瓶颈为交通信号通行周期，文献[20]的分析表明每辆车离开道路占用的时间长度h相差不大，每个通行周期能够离开的车辆数目相对恒定。道路前方每增加一辆车，则后方车辆需要多等待一个车辆离开的时间h。同时如果车辆进入道路的速率较快，超出了道路的最大吞吐量，车辆会积累在道路路口形成车辆队列（以下简称队列）。时间离停车线距离iRTGTYTi+1 i+2 i+3 i+4 i+5 i+6 i+ki+3τiηi+3οi+3εi+3γ图4 交通信号控制下车辆行驶示意图图4中，中部加粗的线段表示交通控制信号状态，图中方框表示具体车辆。标注于中部分段线下方的变量表示车辆进入某一状态的时间点，其下标表示对应的车辆编号；标注于上方的变量表示某一段时间的长度。车辆在受交通信号控制的城市道路上行驶时具有很强的顺序性，并且与控制信号存在密切的关联[20]。本文将同一个车道上的车辆行驶过程简化为M/G/1队列模型。如图4所示，车辆按照某个密度函数为 ()pt G 的分布进入道路p，同时根据交通信号的变化周期性的离开道路，并通过辅道进入下一条道路q。4.1城市车辆行驶特征的分析为了完成车辆选路任务，CoRP算法需要对车辆在城市道路中的行驶过程进行分析和量化，并在此基础上建立选路所需要的目标函数。车辆i进入道路p后会进入一段自由行驶状态，若无其他车辆干扰且交通信号畅通，则在到达路口后将直接离开道路p。车辆i在自由行驶阶段近似为匀速行驶，可以使用公式计算车辆i由进入道路p到抵达道路路口消耗的时间ig 。假设车辆i进入道路的时间为ie，那么车辆i抵达路口时间it可以使用公式计算。/i p iL v g = \*MERGEFORMAT(1)i i ie t g = + \*MERGEFORMAT(2)如果车辆i在时间it抵达道路p的路口时，前方车辆 1 i- 还未离开道路p，则认为车辆i通过道路p的过程受到前方车辆 1 i- 的阻碍，车辆进入道路p的队列，并在交通信号的控制下依次离开道路。由于车辆 1 i- 经过路口需要占用长度为ih的通行周期，因此当不等式成立时，认为车辆i经过道路p路口时会受车辆 1 i- 阻挡。论文在线出版号No.53 吴黎兵等：一种基于车联网的城市车辆协同选路方法 71 1 i i io t h- -< +\*MERGEFORMAT(3)不考虑交通信号的影响，当车辆i离开队列区域时，如果车辆i经过路口时的行驶状态受前方车辆 1 i- 的阻挡，如图4中车辆 1 i+ 、 2 i+ ，设不考虑交通信号的影响时车辆i离开道路p的时间为io¢ ，则io¢ 为前方车辆 1 i- 离开道路路口的时间 1 io-加上其经过路口占用的时间 1 ih- 。反之，若前方不存在阻挡车辆，那么车辆i离开道路p路口的时间即为车辆i抵达道路p路口的时间it。因此在不考虑交通信号影响的前提下，车辆i离开街道的时间io¢ 可以使用公式求得。1 1 1 11 1,  ,i i i i iii i i io ooo oh t ht h- - - -- -+ < + ì¢ =í³ +î若若\*MERGEFORMAT(4)考虑交通信号影响时，若其处于绿灯状态，那么车辆不受交通信号灯阻碍，可直接离开道路。若控制信号已经变为黄色或者红色状态，车辆将会减速并止步于停车线。判定车辆i在队列前端离开路口过程是否受交通信号影响的条件为：车辆i离开队列时间io¢ 是否位于绿灯周期内。当车辆i离开队列的时间io¢ 满足不等式时，车辆i不受交通信号影响；否则车辆i 会受交通信号阻碍。公式中all G Y RT T T T = + + 表示一个完整的交通信号周期。0( ) mod( )i all Go T T T ¢ - £\*MERGEFORMAT(5)在未受交通信号阻碍的情况下，车辆i离开道路p的时间等于其离开队列的时间。反之，车辆i受到交通信号阻碍将会止步于停车线，并等下个通行周期开始后离开道路。此时，车辆i离开道路p的时间io可以使用公式计算。000 0,  ( )%( ),  ( )%( )i i all Giii all Gallo o T T To o TT o T T TT¢ ¢ - £ ìï= é ù ¢ - í+ ¢ - >ê ú ïê ú î若若\*MERGEFORMAT(6)如图2所示，车辆在交通信号控制下离开当前道路后还需要经过一段辅道才能完全进入下一条道路。由于辅道距离较短，为简化模型，CoRP算法假设车辆在辅道上匀速行驶。因此CoRP算法中车辆i在由道路p进入道路q的辅道上消耗的时间( , )ipq i 可以使用公式表示。,( , ) /i pq ipq l v i =\*MERGEFORMAT(7)车辆i经过道路p抵达下一条道路q的时间( )ie q可以使用公式计算。( ) ( ) ( , )i i ie q o p pq i = +\*MERGEFORMAT(8)至此，车辆i完成了由进入道路p到进入道路q的行驶过程。4.2车辆行驶时间的量化在4.1节的计算中，车辆i经过道路p抵达下一条道路q的时间( )ie q与道路长度pL、车辆i的速度iv以及车辆 1 i- 离开道路的时间io有关。其中道路长度pL与车辆i的速度iv能够直接获取。但车辆1 i- 离开道路p的时间io则需要结合道路状态和其他车辆对道路的影响进行估计。在城市道路中，每个交通控制信号周期内，车辆离开道路的时间近似均匀地分布在周期的可通过阶段。对某一车辆离开道路的时间量化可以转换为对车辆离开道路的周期和对车辆在该周期中所处位置的估算。文献[20]和文献[6]表明，在传感器设备或者智能交通系统(ITS)的帮助下，能够较为准确地获取t时刻道路p队列中车辆的数目 ()pt Q ，也能够通过历史数据较为准确地预测某一段时间0 1[ , ] t t 内抵达道路p队列的车辆数目 0 1[ , ]pt t W 。进入队列离开队列进入队列 绿灯车辆红灯离开队列S3S2 S1图5 车辆抵达道路队列与离开队列情况示意图在交通信号控制下，城市道路上车辆离开队列的过程可以分为图5中所示的三种情况。S1空闲状态：队列中不存在等待中的车辆；S2半饱和状态：队列中存在车辆，但能够在下一个绿灯周期内全部离开；S3饱和状态：队列中存在车辆，且无法在下一个绿灯周期内全部离开。假设车辆i抵达道路p队列的时间为it，当道路p为空闲状态时，若交通信号为绿灯的状态，那8 计算机学报 2017年么车辆i可以马上离开道路p。反之，如果交通信号为黄灯或者红灯，那么车辆i需要等待至下一个周期的绿灯状态才可以离开。0T表示it时刻交通信号周期绿灯状态的开始时间。则在空闲状态时，车辆i离开道路p的时间( )io p可以使用公式表示。010 0( ), ( ( ) )( ), ( ( ) )i i GiSall i Gp p T To pT T p T Tt tt- £ ì=í+ - >î若若\*MERGEFORMAT(9)当道路p为半饱和状态时，it时刻存在两种情况：①队列中存在未离开的车辆，如图5S2中第1-3辆车，这些车会在交通信号切换为绿灯状态后按序离开道路。②队列中车辆均已离开，如S2中第4辆车，该车辆的离开过程应按照空闲状态车辆处理。若it时刻队列中存在il辆还未离开的车辆，车辆编号分别为 1 i- 、 2 i- … ii l - ，那么车辆i离开道路的时间io取决于前方队列车辆离开道路所占用的通行时间。时间io等于0T加上车辆 1 i- 、2 i- …ii l - 占用的通行时间。因此车辆i离开道路p的时间( )io p可以使用公式计算。102( )iii iSi io p Tlh-¢¢=-= +å\*MERGEFORMAT(10)在CoRP算法估算( )io p的过程中，考虑到车辆离开道路的占用时间h可以认为近似相等，可以使用平均值h表示。因此车辆i离开道路p的时间( )io p可以使用公式计算。02( )i iSo p T l h = + ´\*MERGEFORMAT(11)当道路p为图5中S3所示的饱和状态时，车辆i在道路p上的行驶情况分为两种：(1)能够在当前交通信号周期离开，例如S3中的前5辆车；(2)无法在当前交通信号周期离开，例如S3中的最后一辆车。如果车辆i能够在当前交通信号周期离开道路p，那么其离开时间io可以直接使用公式计算。如果车辆i无法在当前交通信号周期离开道路p，那么需要分两个步骤确定车辆i的离开时间io。即首先确定车辆i会在几个交通信号周期后离开道路p，然后将问题转化为半饱和状态进行计算。假设0T为道路p某一个交通信号周期中绿灯状态的开始时间，道路p从0T时刻起一直为饱和状态。车辆i在0T之后的( )ip t 时刻抵达道路p队列，在0T时刻车辆i前方有il辆车等待离开道路p，且一个交通信号周期中允许通行的时间为G YT T + 。因此，每个交通信号周期内能够通过道路p的最大车辆数目p N可以使用公式计算。G YpT TNh+ ê ú=ê úë û\*MERGEFORMAT(12)以0T为起始点，车辆i离开道路p需要等待的周期数 0( )i CT 可以使用公式计算。0( ) / 1i i pCT N l é ù = -ê ú\*MERGEFORMAT(13)在 0( )i CT 个周期后，车辆i前方剩余车辆的数目il¢ 可以使用公式计算。%i i pN l l ¢ =\*MERGEFORMAT(14)之后车辆i离开的过程类似于半饱和状态。最终车辆i在饱和状态下离开道路p进入道路q的时间( )io p可使用公式计算。0 03( ) ( )i i all iSo p T CT T l h = + ´ + ¢ ´\*MERGEFORMAT(15)当车辆i经过上述3种状态离开道路p后，车辆i将沿着道路p末端的辅道继续行驶，并进入下一条道路q。因此，车辆i离开道路p进入道路q的时间( )ie q 为车辆i离开道路的时间( )io p 加上其在道路p至道路q辅道上消耗的时间( , )ipq i ，即公式。( ) ( ) ( , )i i ie q o p pq i = +\*MERGEFORMAT(16)4.3饱和状态时间的判定在4.2节中，计算车辆i在道路p上的行驶时间需要使用车辆i前方车辆的数目il，并对车辆进入道路时的状态进行判定。在车辆进入道路后，il可以由道路p上的传感器获得。但在车辆i还未到达道路p时，il与前方车辆离开时间 1 io- 一样无法直接通过测量获得。因此，CoRP算法需要对车辆i前方车辆的数目il进行估计。时刻x进入道路p的车辆数目的密度函数( )px G 可以使用历史数据进行估计，0t 时刻道路p队论文在线出版号No.53 吴黎兵等：一种基于车联网的城市车辆协同选路方法 9列中车辆的数目 0( )pt Q 可由交通监控设备获得[6]。设 ( )px G 和 ( )px X 分别为x时刻进入和离开道路p队列的车辆数目的密度函数，则t时刻队列中的车辆数目 ()pt Q 满足等式。00() ( ) ( ( ) ( ))tp p p ptt t x x dx Q =Q + G -Xò\*MERGEFORMAT(17)如果车辆i抵达道路p队列的时间为it，则此时队列中车辆数目il等于 ( )p it Q ，即 ( )i p il t =Q 。根据如图5所示的道路状态，车辆i离开道路p的过程可以分三种情况。其中，半饱和状态可以按前方车辆数目il是否为0，转化为空闲状态和0( )i CT 为0的饱和状态。因此离开道路p的车辆数目的密度函数 ( )px X 可分两种情况讨论：1) 0il= 时，车辆离开道路时间符合公式。2) 0il¹ 时，车辆离开道路时间符合公式。每个交通信号周期能够通过道路p的车辆数目p N可以由公式计算。若某一周期中任意时刻il都大于0，则该周期可以通过p N辆车。若存在某时刻 0il= ，则此后 ( )px X 也变为0，直至有新车辆进入队列。考虑到信息收集精度与算法开销的问题，CoRP算法使用交通信号自身的循环周期作为( )px G 的统计周期。如果队列中已有车辆数目 0( )pt Q与0 1[ , ] t t 时间内抵达队列的车辆数目 0 1[ , ]pt t W 之和大于p N，则认为道路p在该周期为饱和状态。该周期是否为饱和状态0 1[ , ] t tS 可以通过公式判断。0 10 0 1[ , ]0 0 1true ,if  ( ) [ , ]false ,if  ( ) [ , ]p p pt tp p pt t t NSt t t NQ +W > ì=íQ +W £î\*MERGEFORMAT(18)5 CoRP算法路径优化与拥塞避免城市环境下车辆选路问题的优化目标主要包括行驶时间开销、行驶距离开销和行驶过程对环境的影响开销等方面[21]。由于车辆能源消耗与污染物排放均与车辆在道路上行驶的时间直接相关，因此本文采取行驶时间开销作为主要优化目标。5.1基于全局影响的最优化策略在进行选路时，选路车辆需要考虑其他车辆的行驶过程对自身行驶代价的影响，反之亦然。因此，选路算法需要综合考虑车辆的选路结果对车辆自身和其他车辆的影响。假设iR为车辆i所选择的由道路0p到道路np的路径，那么车辆i选择路径iR时，自身行驶时间开销( )iSR 可用公式表示。00( ) ( ( ) ( )), ...npi i i n ip pSR o p e p p p R== - Î å\*MERGEFORMAT(19)此外，车辆i选择路径iR后，会对其他车辆的行驶过程带来以下影响：影响1：车辆i进入道路( )ipp R ΢ 对车辆 1 i+行驶时间的影响。饱和状态下，车辆i进入道路会导致后方车辆1 i+ 离开道路的时间 1 io+ 向后推延，并最终使车辆1 i+ 占据车辆 2 i+ 的离开时间。车辆 1 i+ 行驶代价的变化值 1 io+D 可以使用公式计算。1 2 1 i i io o o+ + +D = -\*MERGEFORMAT(20)影响2：车辆i进入道路( )ipp R ΢ 对后续进入该道路的车辆的影响。如果车辆i后方s辆车，1 i+ 、2 i+ 直至i s + 进入道路p时，道路p处于饱和状态，那么车辆i对后续进入的车辆的影响会经由车辆 1 i+ 、 2 i+ 依次向后传递，直到车辆i s + 退出饱和状态为止。该过程中，车辆i在道路p的行驶过程对整体道路行驶时间的影响包括两部分，即车辆i自身的行驶时间和其他车辆增加的行驶时间。车辆i进入道路p对道路上车辆整体行驶时间的影响 (, )addi p D 可以使用公式估算。11(, ) ( ) ( )iadd i i n nn ii ii p o e o oo ess++=+ +D = - + -= -å\*MERGEFORMAT(21)影响3：车辆选择路径iR对整条路径上其他车辆的影响。当车辆i选择路径iR后，车辆i进入道路对整体行驶时间的影响 ( )add iR D 等于对路径iR中的每一条道路影响的累加，可以使用公式计算。00( ) (, ) , ...npadd i add n ip pR i p p p R=D = D Î å\*MERGEFORMAT(22)影响4：对车辆i的历史路径iR¢ 上的车辆的影响。10 计算机学报 2017年如果车辆i是存在于历史行驶数据中的车辆，在车辆i选择一条新的路径iR后，其历史路径iR¢ 上其他车辆的预计行驶时间会有所下降。与公式类似，对于路径iR¢ 中的每一条道路 ip R ΢ ，车辆i不再进入道路p对其他车辆行驶时间的改变量(, )deli p D 可以使用公式计算。111(, ) ( ) ( )idel i i n nn ii ii p o e o oe oss+-=++ +D =- - - -= -å\*MERGEFORMAT(23)其对整条路径iR¢ 上所有车辆行驶时间带来的影响 ( )del iR D ¢ 可以使用公式计算。00( ) (, ), ...npdel i del n ip pR i p p p R=D ¢ = D ΢ å\*MERGEFORMAT(24)除了直接增减车辆之外，车辆i进入道路p还有可能会改变其他车辆进入下一条道路q的顺序。假设道路p上车辆k因受车辆i的影响而导致进入道路q的时间发生改变，并与道路q中车辆 1 k+ 互换了进入的顺序。由于进入道路q的车辆数目并未改变，因此这种顺序改变只影响道路q上车辆k与车辆 1 k+ 。该影响 ( , 1)swapkk D + 可以使用公式计算。1 11 1( , 1) (( ) ( ))(( ) ( ))0swap k k k kk k k kkk o e o eo e o e+ ++ +D + = - + -- - + -º\*MERGEFORMAT(25)由于 ( , 1)swapkk D + 恒等于0，因此可以认为车辆i进入道路间接造成的行驶顺序改变对全局的影响可以忽略不计。综合考虑以上影响，车辆i的行驶路径由iR¢ 变更为iR后，对整个系统行驶时间的影响( )i iTR R ¢ ®可以使用公式计算。( ) ( ) ( )i i del i add iTR R R R ¢ ® =D ¢ +D\*MERGEFORMAT(26)又因为车辆i在系统中的历史路径iR¢ 为确定值，所以 ( )del iR D ¢ 也是一个固定值。因此，在考虑车辆i 选路过程对全局的影响时仅需要考虑( )add iR D 的大小。5.2拥塞避免策略车辆拥塞是一种比较常见的交通现象，拥塞会降低道路上车辆的通行效率，甚至会导致交通事故的发生。一般而言，导致道路拥塞主要有两种情况：1) 进入道路的车辆数目过多，大于道路的最大容量，导致拥塞。2) 道路上发生突发事故，导致拥塞。车辆对道路的占用率(laneoccupancy)能够极大地反应道路的拥塞情况[22]。因此针对情况1，CoRP算法使用道路占用率( )ir p对车辆通过道路的开销进行修正，避免因进入道路的车辆超出道路最大容量而产生拥塞的情况。道路占用率一般采用车辆在道路的投影距离和道路长度的百分比表示，道路p中的投影面积包括道路中所有车辆的车身长度is，以及其在道路中与前方车辆的间隔距离ig。对于使用CoRP算法的车辆，CoRP算法可以直接获取车辆的长度与车间间距，而对于历史数据中的车辆，则可以通过历史观测数据，使用平均数据进行表示。因此在车辆i进入道路p时，道路p的道路占用率( )ir p可以使用公式表示。( ) ( )/ ,i j j p j i j ir p s g L e e o e = + £ Ú ³ å\*MERGEFORMAT(27)在CoRP算法过程中，如果车辆i进入道路p时，该道路的占用率( )ir p大于50%，且没有被占用的距离( )if p 小于阈值pth，那么CoRP算法需要对车辆i通过道路p的代价 (, )addi p D 进行修正。没有被占用的距离( )if p 和车辆i通过道路p的量化代价 (, )fixi p D 分别通过公式和公式计算。( ) (1 ( ))i p if p L r p = ´ -\*MERGEFORMAT(28)(, )( ) 50%(, ) if( )(, ) ( ) 50%if( ( )) ( )fixiaddi padd ip i i pi pr pi pf p thi p r pMth f p f p thD£ ìDïÚ ³ï=íD + >ï- Ù <î\*MERGEFORMAT(29)公式中M为加值系数，一般而言M需要足够大，以便于区分拥塞路段与非拥塞路段。本文实验部分M取值为41.0 10 ´ 。由于事故处理属于特殊事件，并且不同事故依据类型、波及范围等需要不同应对方式，因此本文暂且不考虑情况2导致的拥塞问题，针对该情况的论文在线出版号No.53 吴黎兵等：一种基于车联网的城市车辆协同选路方法 11处理将在后续工作中继续完善。最终，车辆i选择路径iR的量化代价可以通过对车辆i通过iR中所有道路的量化代价 (, )fixi p D 进行累加获得。因此对于车辆i，CoRP算法优化函数可以用公式表示。() { (, )},pfix iFi min i p p R = D Î å\*MERGEFORMAT(30)确定了优化目标函数后，CoRP算法使用Dijkstra算法计算出最优路径iR，并反馈给车辆i。车辆i确认路径iR后，将行驶方案反馈到整个交通道路信息网络中。收到车辆i反馈的行驶方案后，CoRP算法首先从车辆原行驶路径iR¢ 对应道路的历史密度函数 ()pt G 中移除车辆i对应的信息；其次对路径iR中的道路p添加车辆i的信息。至此，CoRP算法完成了一次完整的选路过程。6仿真实验本节的仿真实验基于Veins[23]完成。Veins是基于OMNeT++[24]和SUMO[25]的仿真框架，其主要包括运动仿真和网络仿真两个部分。其中运动仿真由SUMO完成，网络通信仿真由OMNeT++完成。在OMNeT++平台中，Veins提供的TraCI接口可以对SUMO中车辆的行驶状态进行检测，并能够对车辆的选路决策进行实时控制。考虑到本文研究的内容主要关于车辆路径规划算法，因此在实验中车辆使用理想信道直接与路径规划系统通信，且不考虑丢包与时延问题。6.1仿真场景设置本文实验仿真场景依据武汉大学周边地图构造，具体如图6所示。图6左下角为本文实验所用道路拓扑，所有道路均为双向多车道，路口均有交通信号灯。地图中总计不同方向的道路71条，其中与城市其他区域连通的道路9条。实验中车辆生成速率如图7所示。前600秒，生成速率为5000辆每小时，之后开始逐步增加，1800秒时达到最大值。最大值持续至4200秒，并逐步减少，直至5400秒时恢复5000辆每小时，并于7200秒时变为0。为保证试验条件一致，同一组实验中，车辆部署时间与起止点对相同。图6 仿真场景地图及拓扑图7 车辆生成速率考虑到智能交通系统ITS逐步普及，越来越多的驾驶员开始使用智能设备作为选路参考，本文选取基于ITS实时行驶时间的ITS算法[9]作为第一个对比算法。同时，使用在ITS算法的基础上引入路径重选的动态算法，即DYRP算法，作为第二个对比算法。DYRP算法中，路径重选行为发生在车辆进入新道路的瞬间。实验中CoRP算法需要的历史数据为ITS算法实验的统计数据。6.2不同算法性能比较图8 不同时刻滞留车辆数目本文首先研究的是最大车辆生成速率为30000辆每小时，40%车辆由连接城市的其他区域的道路12 计算机学报 2017年进入并穿过实验区域的情况。图8表示实验中不同时刻各算法在道路上滞留的车辆的数目。实验结果表明，CoRP算法能够让车辆更快的到达目的地，降低滞留在道路中的车辆数目。实验初期车辆数目较少时，道路较为空旷，选路车辆在行驶过程中对其他车辆的影响较小。此时ITS系统提供的信息能够准确反映未来车辆的行驶状态，不同算法的差别并不明显。而随着时间的推移，尤其是1800秒之后，车辆进入道路速率达到最大，从路径选择到实际行驶至对应道路期间，其他车辆对道路的行驶状态的改变逐渐增大。2000秒之后，ITS算法中使用的实时信息已经无法准确描述车辆实际行驶至对应道路时的行驶时间，ITS算法性能开始表现出明显劣势。在ITS算法的仿真过程中，道路中车辆最大滞留数目为6241辆。DYRP算法由于能在道路行驶状态变化后修正行驶路径，其效果略好于ITS。但是车辆改变路径的过程只能发生在离开道路进入下一条道路时，而此时前方可选道路可能已经无法避免拥塞，所以其算法性能依然落后于CoRP算法。在使用DYRP算法的仿真过程中，道路中车辆最大滞留数目为5280辆。本文提出的CoRP算法考虑了车辆路径选择对道路未来状态的影响，对道路一段时间内通过状态变化进行了估算，并采用基于全局最优的选路策略综合考虑了对其他车辆的影响，因而能够明显加快整体车辆的消散过程，显著降低道路上滞留车辆的数目。在使用CoRP算法的仿真过程中，道路中车辆最大滞留数目为4340辆，较使用ITS算法和DYRP算法的情况分别降低了约30%和18%。图9 不同时刻系统车辆二氧化碳排放速率此外，使用CoRP算法对车辆路径进行规划能够减少道路中滞留的车辆数目，从而也能够降低城市车辆行驶过程中的二氧化碳(CO2)排放。二氧化碳排放速率如图9所示。图9中，使用ITS、DYRP和CoRP三种算法时，道路中车辆最高总二氧化碳排放速率分别为41.21 10 ´ g/s、41.15 10 ´ g/s和41.04 10 ´ g/s，在整个实验过程中排放二氧化碳总量依此为74.99 10 ´ g、74.54 10 ´ g和74.18 10 ´ g。此场景下，CoRP算法比ITS算法和DYRP算法最高总二氧化碳排放速率降低了15%和10%，二氧化碳排放总量减少了16%和8%。6.3车辆生成速率对选路效果的影响为了准确展现本文提出算法的各项特征，本文将依次分析车辆生成速率、车辆起止点特征以及采用率三个关键因素对各算法性能的影响。本文使用所有车辆行驶总时间开销(TTS, totaltimespend)作为衡量选路算法性能的标准。不同车辆生成速率下各算法性能如图10所示。图10 车辆生成速率对算法效果的影响实验结果显示，在最大车辆生成速率为较低水平时(20000辆/小时)，后续车辆对道路行驶状态的改变有限，道路状态在未来一段时间内相对变化较小，此时ITS、DYRP以及CoRP三者TTS分别为71.25 10 ´ 、71.24 10 ´ 和71.17 10 ´ 秒，CoRP算法小幅领先于其他算法。当车辆生成速率逐渐增大，使得车辆对道路后续行驶状态的影响逐渐增大，此时基于实时信息的ITS算法无法准确反映未来一段时间内车辆对道路行驶状态的改变，行驶时间开始大幅上升。而本文提出的CoRP算法由于能够考虑车辆在未来一段时间对道路交通状态的影响，因此在车流量增大后依然能够取得较好效果，以最大车辆生成速率30000辆/小时为例，该情况下ITS、DYRP以及CoRP算法TTS分别为72.47 10 ´ 、72.04 10 ´ 和71.75 10 ´ 秒，此时CoRP算法的TTS分别比ITS、DYRP算法减少了约29%和14%。综上证明，CoRP算法与ITS、DYRP算法相比，能较为明显地降低城市环境中车辆行驶总时间开销。论文在线出版号No.53 吴黎兵等：一种基于车联网的城市车辆协同选路方法 136.4起止点特征对选路效果的影响城市中行驶的车辆在不同的时段起点和终点的构成比例往往各不一样。例如上班高峰期城市内行驶的车辆占主要地位，而随着上班高峰的结束，城市外部进入并穿过城市的穿行车辆数目会逐渐增多。本文通过改变穿行车辆的比例，来测试不同场景测试各算法的性能。实验中车辆最大生成速率为30000辆每小时，实验结果如图11所示。图11 穿行车辆比例对算法效果的影响实验中，当大部分车辆起点与目的地都位于城市内部道路时，城市内部道路会变得十分拥挤。在这种情况下，本文提出的CoRP算法考虑了车辆未来的行驶过程对道路行驶状态的影响，利用车间通信技术共享路径规划方案，可以在选路时提前避开可能产生拥堵的内部道路，因而算法性能最好；传统的ITS算法更倾向于集中选择某一些内部道路，进而在这些道路形成拥堵，导致总体行驶时间较高。DYRP算法虽然能够根据拥堵情况进行重选路操作，但受到重选路时机的限制，性能依然落后于CoRP算法。当穿行车辆较多时，多数车辆需要行驶较长距离穿过城市，在道路中停留的时间变长，因此随着穿行车辆比例提升，三种算法的车辆总体行驶时间均有所上升。针对全部穿行车辆比例的情况，CoRP算法由于能够提前规避可能产生拥堵的内部道路，因此在三种算法中行驶总时间开销最小。6.5算法采用率对选路效果的影响在实际生活中，可能存在使用不同选路算法的车辆。本组实验研究了算法使用比例对各算法性能的影响。实验中车辆分为A、B两类：A类车辆使用实验算法；B类车辆总是使用ITS算法。实验中分别测试了A类车辆比例为20%至100%的情况。实验中最大车辆生成速率依然为30000辆每小时，实验结果如图12所示。图12 算法采用率对算法的影响图12中，柱状图较细的部分为所有车辆行驶总时间开销。由于B类车辆均使用ITS算法进行选路，因此实验结果中ITS算法整体性能不受A类车辆比例变化的影响。当A类车辆占用比例为20%时，采用ITS、DYRP和CoRP算法的TTS分别为72.47 10 ´ 、72.25 10 ´ 和71.92 10 ´ 秒，此时，CoRP算法TTS相较ITS算法和DYRP算法分别降低了22%和15%；而当所有车辆均为A类车辆时，三种算法的TTS变为72.47 10 ´ 、72.04 10 ´ 和71.75 10 ´ 秒，CoRP算法的TTS比ITS、DYRP算法减少的比例约为29%和14%。以上结果表明，即使仅20%的车辆使用CoRP算法，也能够成功通过规避未来可能发生的拥塞，提高城市道路的整体通行性能。图12中，柱状图中较粗部分表示实验过程中A类车辆的个体平均行驶时间与其使用ITS算法进行选路时的时间开销的比例。粗线条的行驶时间比例显示，由于能够规避发生拥堵的道路，CoRP算法除了可以降低整体通行时间开销外，也可以明显降低使用CoRP算法的A类车辆的通行时间开销。7结论与展望随着GPS与智能网络终端、车载导航设备的普及，人们越来越习惯于使用智能化的导航功能。针对现有的车辆选路方法已经无法满足人们多元化出行需求这一现状，本文提出了一种车联网环境下的城市车辆协同选路方法——CoRP选路算法。结合车载设备与城市交通信息系统，CoRP选路算法通过汇集城市中选路车辆的路径选择信息，在考虑车辆行驶过程相互作用的前提下，为选路车辆规划出一条合理的行驶路径。实验结果表明，本文提出的CoRP选路算法具有以下3个优势：14 计算机学报 2017年1）CoRP算法根据城市道路的具体特点，提出了针对受交通信号控制车辆的行驶时间量化方法，并且考虑了车辆选路行为对道路未来通行状态的影响，能够更加准确的反映城市车辆的行驶状态。2）CoRP算法使用基于全局影响的最优化策略，相较于单纯基于实时交通信息的选路算法，本算法能够避免由于个体车辆选路行为造成道路拥塞的现象，提高车流高峰时期车辆的行驶效率。3）CoRP算法在仅有部分车辆使用该算法时也能取得较好效果。由于该算法能够对道路未来的拥塞情况进行估计，即使仅有部分车辆使用该算法，也能够通过规避可能产生拥塞的道路，降低这些道路上车辆的行驶时间，从而提高交通系统的整体性能。实验结果表明，本文提出的CoRP选路算法能够减少14%~29%的全局车辆行驶时间消耗并降低8%~16%的二氧化碳排放，达到提高城市道路的交通容量和降低环境污染的目的。下一步我们将对处理突发事件，保护车辆隐私安全和提高车辆导航时的通信效率等问题展开进一步的研究。参考文献[1] PillacV, GendreauM, Guéret C, MedagliaAL. Areviewof dynamicvehicleroutingproblems. EuropeanJournal of Operational Research,2013,225(1):1-11[2] KokAL,HansEW,SchuttenJM.Vehicleroutingundertime-dependenttravel times: the impact of congestion avoidance. Computers &OperationsResearch,2012,39(5):910-918[3] Qian J, Eglese R. Fuel emissions optimization in vehicle routingproblems withtime-varyingspeeds. EuropeanJournal of OperationalResearch,2016,248(3):840-848[4] Elhassania M, JaouadB, AhmedEA. Solvingthe dynamicVehicleRouting Problemusing genetic algorithms //Proceedings of theInternational Conference on Logistics andOperations Management.Rabat,Morocco,2014:62-69[5] HuangY, YaoH, GaoY, ZhangH, XuY. Development of thehighreal-timeGPStimetransfer receiver //Proceedingsof theInternationalConference on Precision Electromagnetic Measurements, Rio deJaneiro,Brazil,2014:150-151[6] TianB, MorrisBT, TangM, LiuY, YaoY, GouC, ShenD, TangS.HierarchicalandnetworkedvehiclesurveillanceinITS:asurvey. IEEETransactions on Intelligent Transportation Systems, 2015, 16(2):557-580[7] Genders W, Razavi SN. Impact of connectedvehicle onworkzonenetworksafetythroughdynamicrouteguidance. JournalofComputinginCivilEngineering,2015,30(2):04015020[8] TanakaM, UnoN, ShiomiY,AhnY. Experimental studyofeffectsoftravel timedistributioninformationondynamicroutechoicebehavior.JournalofIntelligentTransportationSystems,2014,18(2):215-226.[9] TianD,YuanY,ZhouJ,WangY,LuG, XiaH.Real-timevehiclerouteguidance based on connected vehicles //Proceedings of theInternational ConferenceonGreenComputingandCommunications.Beijing,China,2013:1512-1517[10]Sur C, ParkY, RheeKH. Anefficient andsecurenavigationprotocolbased on vehicular cloud. International Journal of ComputerMathematics,2016,93(2):325-344[11]WuLi-Bing, NieLei, LiuBing-Yi, WuNi, ZouYi-Fei. AnIntelligentTraffic Signal Control Method in VANET. Chinese Journal ofComputers,2016,39(6):1105-1119(inChinese)(吴黎兵,聂雷,刘冰艺,吴妮,邹逸飞. 一种VANET环境下的智能交通信号控制方法. 计算机学报,2016,39(6):1105-1119)[12]WenMeng-Fei, PengJun, ZhuZheng-Fa, LiuWei-Rong. DistributedCooperative Methods for Traffic FlowOptimization in IntelligentTransportationNetwork. Journal ofChineseComputerSystems, 2012,33(4):852-855(inChinese)(文孟飞, 彭军, 朱正发, 刘伟荣. 交通网络车流量的分布式协同优化方法研究. 小型微型计算机系统,2012,33(4):852-855)[13]Groot N, De Schutter B, Hellendoorn H. Toward system-optimalroutingintrafficnetworks:areverseStackelberggameapproach, IEEETransactionsonIntelligentTransportationSystems,2015,16(1):29-40[14]DallmeyerJ, SchumannR, LattnerAD, TimmIJ. Don't gowiththeantflow: Ant-inspiredtraffic routinginurbanenvironments. Journal ofIntelligentTransportationSystems,2015,19(1):78-88[15]Qin Xu-Yan. Research and Implementation of Simulation BasedDynamic Traffic Assignment Model [PhDdissertation]. TsinghuaUniversity,Beijing,China,2008(秦旭彦, 基于仿真的动态交通分配模型研究及实现[博士学位论文]. 清华大学, 北京, 中国,2008[16]SmithM, MounceR. Asplittingratemodel of trafficre-routeingandtrafficcontrol. TransportationResearchPart B: Methodological, 2011,45(9):1389-1409[17]Pan J, Popa IS, Zeitouni K, Borcea C. Proactive vehicular trafficrerouting for lower travel time. IEEE Transactions on vehiculartechnology,2013,62(8):3551-3568[18]PanJ, PopaIS, BorceaC. DIVERT: ADistributedVehicular TrafficRe-routingSystemfor CongestionAvoidance. IEEETransactions onMobileComputing,2016,PP(99):1-14[19]YeP, WenD. Optimal TrafficSensor Locationfor Origin-DestinationEstimation Using a Compressed Sensing Framework. IEEETransactionsonIntelligentTransportationSystems.2016,PP(99):1-10[20]HaoP, BanX, WhonYuJ. Kinematicequation-basedvehiclequeuelocationestimationmethodfor signalizedintersections usingmobilesensordata. JournalofIntelligentTransportationSystems, 2015, 19(3):256-272[21]KimG, OngYS, HengCK, TanPS, ZhangNA. Cityvehicleroutingproblem(City VRP): a review. IEEE Transactions on IntelligentTransportationSystems,2015,16(4):1654-1666论文在线出版号No.53 吴黎兵等：一种基于车联网的城市车辆协同选路方法 15[22]Gonzalez-FeliuJ, Ambrosini C, Pluvinet P, Toilier F, Routhier JL. Asimulation framework for evaluating the impacts of urban goodstransport in terms of road occupancy. Journal of ComputationalScience,2012,3(4):206-215[23]SommerC,GermanR,DresslerF.Bidirectionallycouplednetworkandroadtrafficsimulationfor improvedIVCanalysis. IEEETransactionsonMobileComputing,2011,10(1):3-15[24]Varga, A. "OMNeT++"Chapter inthebook"ModelingandToolsforNetworkSimulation".Berlin:SpringerVerlag,2010[25]KrajzewiczD, ErdmannJ, BehrischM, BiekerL. Recent developmentand applications of SUMO–simulation of urban mobility.International Journal on Advances in Systems and Measurements,2012,5(3&4):128-138WuLi-Bing,bornin1972,PhD.,professor.Hismainresearchinterestsincludewirelesssensor networks, network management and distributedcomputing.FanJing, bornin1989, Ph.D. candidate. Hismainresearchinterestsincludeinternetofvehiclesanddistributedcomputing.Nie Lei, bornin1989, Ph.D. candidate. His mainresearchinterestsincludewirelesssensornetworksandvehicularad-hocnetwork.Cui Jian-Qun, born in 1974, PhD., professor. Her mainresearch interests include computer network andhigh-performancecomputing.ZouYi-Fei, bornin1994, undergraduate student. His mainresearchinterestsincludevehiclead-hocnetworksandwirelesssensornetworks.BackgroundDuetothecontinuouslyincreasingscaleofmodernurbantraffic, moreandmoreattentionhas beenpaidtotheurbantraffic optimizationproblem. The focus of this paper is thevehicle routingproblem(VRP), whichaims at reducingthetravelcostforvehiclesandimprovetheefficiencyofthewholetransportationsystem.ByutilizingthetechnologyofIntelligentTransportation System (ITS), researchers have alreadyachievedsomegreatimprovementonthisproblem.However,itstill hasroomtobeimproved. Incurrent researches, manyofthemtrytocalculatetheoptimizedroutesforvehiclesbyusingthereal-timetrafficinformation, but fewof themconsider thefutureeffectscausedbytheroutingalgorithmitself. Therapiddevelopment of Internet of Vehicleduringthepast tenyearsenablesvehiclestocommunicatewiththeinternet smoothly. Inprevious research's foundation, this paper proposed acollaborativerouteplanningmethodthat considers thefuturechangesof trafficsituation. Byimport theinternet of vehicle,thismethodalsocanimprovethecooperationof vehicles. Inaddition, thesimulationshowsthatcomparedwiththemethodsjustdependingonthereal-timetrafficinformation, ourmethodcan reduce the travel time for vehicles and improve theefficiency of the whole transportation system. In thesimulations, ourmethodcouldreduce18%~30%maxvehiclesnumberonall roadsofthesystemandreduce14%~29%traveltimefor all vehicles. At thesametime, our methodalsohasgoodfeasibilityandadaptability, sinceit workswell evenjustusedbyasmallpartofvehicles.Thisworkis supportedbytheNational Natural ScienceFoundationofChina(No.61472287). Thisfoundationisaboutresearch the collaboration mechanism and the reliablecommunicationmethodwhenusinginternet of vehicle. Thegoal of this work is trying to improve the collaborationmechanismof transportation systemby using internet ofvehicle.Beforethis work, our teamhas alreadypublishedsomepaper about traffic signal control method; safety messagebroadcast methodandcooperativedownloadingapproachforvehicles..