收稿日期:2009 09 27;修回日期:2009 11 02 基金项目:国家自然科学基金资助项目(20079862);国家教育部博士点基金资助项目(20040699025);2009年度浙江省教育厅科研项目研究课题;2010年度浙江省社科联研究课题和2010年度衢州市社科规划课题
作者简介:余燕芳(1976 ),女,浙江衢州人,讲师,主要研究方向为计算机信息安全与智能化信息处理等(yuyanfang2008@126.co m );陆军(1975 ),男,湖南长沙人,副教授,博士,主要研究方向为人工智能、计算机应用.
基于动态交通仿真模型的最优路径选择方法
*
余燕芳1,2
,陆 军
2
(1.衢州广播电视大学,浙江衢州324000;2.国防科学技术大学计算机学院,长沙410073)
摘 要:采用动态交通仿真模型I NTEGRATI O N 搭建了动态交通仿真平台,应用组件式蚁群算法来求解动态交
通信息诱导下的最优路径选择问题。
实例表明,基于动态交通仿真模型的最优路径选择方法是可行的、正确的和有效的。
该方法易于理解和使用,具有很强的可重用性和可扩展性,为求解各类优化问题提供了可持续发展的框架。
关键词:动态交通仿真;组件式蚁群算法;最优路径选择中图分类号:U 491 1 文献标志码:A 文章编号:1001 3695(2010)05 1662 03
do:i 10.3969/.j i ssn .1001 3695.2010.05.014
Shortest path se l ecti on approach based on dyna m i c traffic si m u l ati on m odels
YU Y an fang 1,2,LU Jun 2
(1.Quzh ou Rad i o &TV Un i versit y,Quzh ou Zheji ang 324000,C hina;2.C oll ege of Co mpu te rs ,N ationa l University of De fense T ec hnology ,
Chang sha 410073,Ch i na )
Abstract :Constructed dynam ic traffic sm i u l ati on s ystem by usi ng the dynam ic traffic m odel I NTEGRATI ON.Tack l ed the s hortest pat h sel ection w it h dynam ic traffic i n f or m ati on by t he component based ant colony optm i i zati on .The sm i u l ati on exa m ple s uggests that t he shortest path selecti on approach based on dyna m ic traffic sm i u lati on m odel s i s feasi ble ,correct and effecti ve .This proposed approach is very easy to understand and use ,it has the robust reusage and expansi b ility ;i ndeed provi de an excel lent fra m ework that can continuall y m i prove f or solvi ng d ifferent optm i izati on proble m s .Key words :dyna m ic traffic sm i u lati on ;co m ponent based ant col ony algorith m (C ACA);shortest path selection 随着机动车拥有量急剧增长而带来的交通拥堵、交通事故增多和环境污染加剧等交通问题,越来越成为影响城市正常功能发挥和城市可持续发展的重大难题。
事实和经验证明,城市交通拥堵等问题仅仅依靠交通基础设施的建设是不能完全解决的。
造成城市交通拥堵等问题的原因不仅是交通供给不能满足交通需求所产生的供需矛盾,而且现有交通系统的运行效率未得到充分利用,由交通网络效率浪费带来的交通问题同样严重。
目前,对交通信息条件下的路径选择行为的研究主要基于意向调查和模拟仿真等方法。
这些研究多局限于不同交通信息措施对驾驶员路径选择决策本身影响的研究,或通过虚拟路网简单研究交通信息下路径选择对路网运行状况的影响,而较少结合实际交通网络分析交通信息下路径选择对整个路网运行状态的影响,从而对信息策略与实施措施的制定和决策过程提供不了紧密联系实际路网交通状况的理论与技术支撑。
鉴于上述背景,提出了一种基于动态交通仿真模型的最优路径选择方法。
应用蚁群算法(ant co lony algor i th m,A CA )求解交通优化问题是近年来研究的新方向[1]。
蚁群算法[2]是一种源于自然界中生物世界的新的仿生类随机型搜索算法,通过其内在的搜索机制,已在一系列困难的组合优化问题求解中取得了成效。
蚁群算法已经在求解旅行商问题[3]、二次分配问题[4]和车间作业调度问题[5]中取得了非常理想的结果。
同时,为了克服基
本蚁群算法的不足,人们对其进行了各种改进,以期提高搜索效率,避免过早停滞。
其中主要有D origo 等人[6]提出的An t Q Syste m 、Stutzle 等人[7]提出的MM AS 和G a m bardell a 等人[8]提出的HA S 等。
尽管蚁群算法在相当广阔的领域内均取得了很大的成功,但现有方法仅从蚁群算法的基本结构出发设计软件,很难用来求解不同种类的问题。
研究者还经常需要尝试使用不同的状态转移规则、信息素更新及参数调整策略来改进算法性能。
如果没有一个好的软件结构实现关注分离,任何小的变化都有可能影响到整个软件结构,给算法的调整带来困难。
鉴于此,提出了一种组件式蚁群算法(CACA )。
为了提高算法的可理解性、可重用性和可扩展性,CACA 强调以接口为中心的设计理念,在结构上直接反映蚁群的本质思想和关键概念,最大程度降低与问题的相关性。
仿真优化方法研究的是基于仿真的目标优化问题,基于模型仿真给出的输出量通过优化算法得到最佳的优化结果。
由于实际交通系统的复杂性及其本身的随机性,最短路径的合理规划问题需要使用仿真优化方法来解决。
本文研究的总体思路如图1所示。
1 动态交通仿真模型
本章主要研究了动态交通仿真模型的构建与标定方法,搭建了实例动态交通仿真平台。
动态交通仿真的基本原理是:对
第27卷第5期2010年5月 计算机应用研究Application R esearc h of C o m puters V o.l 27N o .5
M ay 2010
引入动态交通模型进行需求分析,选取合适的动态交通仿真模型作为搭建平台的基础;研究动态OD 需求获取和交通流参数标定方法;搭建与标定实例仿真平台,并对仿真平台的效果进
行检验。
本章所建立的仿真平台将作为研究动态交通信息下最优路径选择的基本平台。
本文以真实交通网络为实例研究动态交通信息诱导下的最优路径选择问题,要求应用的交通仿真模型能够满足以下条件:a)能清晰地表现路网的几何形状,如信号灯等;b )能清晰地表现车辆间的相互作用,如跟车、车道变换时的相互作用;c)能够细致地仿真路网交通流的状况,如交通需求的动态变化、交通拥堵、排队溢出现象等;d)能模拟先进的交通信息策略,如提供实时交通信息、动态车辆诱导、可变信息板设置等;e)提供结果分析的工具和输出反映路网实时运行状态的相关运行参数;f)能提供图形化的交互界面。
由于传统的静态交通仿真模型不能反映路网的动态特性的特点,本文研究需要引入动态交通仿真模型。
1 1 仿真区域的选择
本文选取了浙江省丽水市城区的某区域路网作为交通仿真路网实例。
该区域路网东西两端距离约4k m,南北两端距离约5k m 。
该区域路网包含了城市快速路主路、辅路、主干路、次干路、支路五种不同等级道路,路网功能较为全面完整。
该区域作为丽水市中心区域之一,该区域路网具有代表城市路网一般交通特性的典型特征。
本区域路网规模适中,既有代表一般城市交通网络的典型特征,又可以保证基本路网数据调查工作量在一个可接受的合理范围内。
在选取了上述实例路网区域后,本文对该区域道路基本属性、交通信号控制等进行了实际调查,并根据实际调查结果在I NTEGRAT ION 中搭建了路网平台。
所构建的路网平台包括266个节点,378条路段,内外OD 小区共20对。
1 2 动态O D 需求获取
本文采用的双层动态OD 获取方法是一种结合传统OD 反推和浮动车OD 随时间变化比例拆分的新方法。
该方法通过I NTEGRAT ION 模型中的OD 反推模块QUEEN SOD 反推得到仿真测试时段2h 长的总OD,然后应用浮动车OD 时变比例将该2h 总OD 拆分为更小时段的动态OD 矩阵。
采用的双层动态OD 获取方法技术路线如图2
所示。
1 3 交通流参数标定
为了获取交通流的速度 流量 密度三要素之间的关系,使得交通仿真平台更能精确模拟实际路网,需要对仿真路网内
不同功能路段进行交通流参数标定。
针对I NTEGRAT I ON 模型,具体需要标定的交通流参数是自由流速度、最大通行能力下的速度、通行能力和阻塞密度。
在开展交通流参数标定之前,要先确定路段交通流参数标定的细致程度,设计相应的标
定方案。
1)分道路等级 由于不同等级道路在城市路网中承担的功能和设计标准不同,其交通流参数也各有不同。
对于同等级的道路,由于相似的功能和设计标准,可近似认为其交通流参数相同。
对于全网路段,可以分道路等级进行标定,即对每个等级的道路选取一定数量的代表路段作为标定样本,标定后的交通流参数应用于该等级道路的所有路段上。
2)分路段位置 快速路出入口附近路段由于受到合流、分流及交织等影响,其交通流特性与其他路段并不一致。
对快速路的基本路段和出入口路段交通流参数分别进行标定。
3)分交通流方向 由于快速路的内环和外环的差异性,其交通流参数也有一定差异性。
快速路在路网中占据着重要地位,对其内环和外环进行细致的标定。
综合上述标定原理及标定方案,交通流参数标定的流程如图3所示。
2 组件式蚁群算法
本文将基于组件的软件工程技术(component based so ft w are eng i neeri ng ,CBSE)[9]来指导蚁群算法的软件设计,提出一种新的组件式蚁群算法。
CBSE 强调的软件重用思想[10]在蚁群算法的广泛应用中能够大大减少重复性的设计工作,提高研究和开发效率。
CBSE 以接口为中心的设计思想[11]及组件本身的黑盒性质,能有效地将对算法某一方面的调整控制在一个组件中,从而有利于蚁群算法的实验研究。
CACA 的主要思想是:把蚁群算法软件中的各个组成部分作为可重用的软件组件来开发;然后组装这些组件来开发整个蚁群算法软件系统;替换和增加新的组件就可以实现整个系统的维护和扩展。
2 1 算法框架
本文组件式蚁群算法的软件设计从总体上划分为相对独立而又相互联系的四个部分:优化问题定义、蚁群算法的搜索机制、求解过程的观察和控制、蚁群算法的求解策略。
相应地,CACA 把这四个部分组织成四个逻辑包,每个逻辑包将密切相关的概念组织到一起,不同逻辑包中的概念相对来说关系较为松散。
本文CACA 的算法框架如图4所示。
在本文组件式蚁群算法的框架下,可以通过向该框架上组装即插即用的软件组件来开发软件,软件的维护和扩展则是定制和替换这些软件组件。
在这样的模式下,需要严格地将组件
1663 第5期余燕芳,等:基于动态交通仿真模型的最优路径选择方法
的接口与实现完全分离,并且使用接口来组装组件。
2 2 CA CA组件接口设计
蚁群算法中的每个概念都有多种不同的具体实现方法,而在组件软件设计中的一个重要方面就是对具体实现细节进行抽象,表达这种抽象的一种方式就是接口。
接口是一个被命名
的操作集合,用来描述子系统提供的一个服务而不指定其实现。
一个好的接口定义表示了一组最小的、完全的和内聚的概念集合,并与其他的接口之间的关系简单而明确。
下面仅以优化问题定义组件为例,说明本文组件式蚁群算法组件接口设计的结果。
优化问题定义组件刻画了蚁群算法必须用到的待求解问题的关键特征,它的接口通过使用abstract factory模式封装了几个与实现有关的概念(可行解个体和可行解群体),保证了该模型不会因为表示方式的变化而变化;通过应用strate gy模式隐藏相关优化操作的实现细节,保证了该模型不会因为优化操作的变化而变化;问题组件接口使得该模型可以应用于不同的具体问题的蚁群算法求解。
2 3 CA CA的可视化
为了获得对算法更好的理解,需要从多个方面同时观察CACA的优化过程,因此同时有多个视图依赖于蚁群算法搜索机制(search eng ine)的计算结果。
即当CACA计算得到新的结果时,CACA需要同时刷新多个视图。
这里实际上是多(视图)对一(search eng ine)的依赖关系。
在行为型设计模式中,ob serv er模式就是处理多对一依赖关系的。
在本研究中,笔者把abstrac t facto ry模式与observer模式相结合,设计了CA C A可视化软件设计方案。
2 4 CA CA的可重用性
蚁群算法的形式多种多样,常见的一些算法有M AX M I N 蚁群算法和蚁群系统(ant co l ony sy stem)等。
这些算法从结构上看基本上是完全一致的,只有优化过程中的状态转移规则和信息素更新策略等不一样。
因此,可以在多个不同的蚁群算法组件中重用蚁群算法的结构,而不同的状态转移规则和信息素更新策略等推迟到不同的蚁群算法组件的具体实现中处理。
3 仿真实例
本文系统的一个规划实例如图5和6所示。
在该图中,最宽的道路为国道,在国道上消防车可以120k m/h的速度快速行驶;比较宽的道路为省道,在省道上消防车可以90k m/h的速度快速行驶;最窄的道路为县道,在县道上消防车可以60 k m/h的速度快速行驶。
在非交通高峰期时,采用本文方法规划出来的路径如图5所示。
最短路径的距离为4.56k m,从消防站到火灾现场耗时171s,这个时间满足从消防站到火灾现场耗时不超过5m i n的基本要求。
当前情况下的规划时间为1.3s,满足路径规划时间在3s内的约束条件。
当前实例结果表明,采用本文系统规划出来的路径是正确的、可行的和有效的。
在交通高峰期时,采用本文方法规划出来的路径如图6所示。
最短路径的距离为4.38k m,从消防站到火灾现场耗时239s,这个时间也满足从消防站到火灾现场耗时不超过5m in 的基本要求。
当前情况下的规划时间为1.3s,满足路径规划时间在3s内的约束条件。
为了验证本文方法的有效性,笔者在每个工作日早高峰期间
(7:00~9:00)在浙江省丽水市来实际测试本文的系统。
笔者一直持续对本系统进行了为期3个月的测试。
测试结果表明,在动态交通信息的诱导下,本文系统能以98.3%的概率规划出最短路径。
同时,本文系统已经广泛地应用到丽水市的消防领域。
根据消防系统的反馈结果,本文系统可信性和实用性都非常好。
测试结果和运行结果表明,采用本文系统规划出来的路径是正确的、可行的和有效的。
4 结束语
本文的主要创新点是提出了一种基于动态交通仿真模型的最优路径选择方法。
组件式蚁群算法力求在结构上直接反映蚁群的本质思想和关键概念;最大程度降低与问题的相关性;强调以接口为中心的设计理念。
数据实例表明,基于动态交通仿真模型的最优路径选择方法是可行的、正确的和有效的。
参考文献:
[1]刘志硕,申金升,柴跃廷.基于自适应蚁群算法的车辆路径问题研
究[J].控制与决策,2005,20(5):562 566.
[2]DOR I GO M,M AN I EZZ O V,COLO M I A.The an t s yste m:op ti m i zation
by a colony of cooperati ng agen ts[J].I EEE T rans on Syst ems,
Man,and Cyberneti c s,Part B:Cyberneti c s,1996,26(1):29 41.
[3]DOR I GO M,GAM BARDELLA L M.An t colony s yste m:a cooperati ve
l earn i ng app roach to the traveli ng s ales m an p rob l e m[J].I EEE T r ans on Evolutionar y C o mput ation,1997,1(1):53 66.
[4]M AN I EZZ O V,COLO M I A.Th e an t syst e m appli ed to the quad ratic
ass i gnm en t p rob l e m[J].I EEE T rans on Know ledge Data Eng i neering,1999,11(5):769 778.
[5]COLORN I A,DORI GO M,MANIEZZO V,et al.An t sys t e m for j ob
shop schedu li ng[J].JORBEL Be l g i a n Journal of O perations Re search,S t atis tics and Computer Science,1994,34(1):39 53.
[6]DORIGO M,GAM BARDELLA L M.A study of so m e properties of
ANT Q[C]//Proc of the4t h Internati onalC onference on ParallelProb le m Solvi ng Fro m Nat u re.Berli n:Sp ri nger Verlag,1996:656 665. [7]STUTZLE T,HOOS H H.TheM AX M I N ant syste m and l ocal search
for the traveli ng sales m an p rob l e m[C]//Proc of the4t h Inter n ati on al
C onference on E voluti onary Co m putation.P iscat away:I EEE Press,
1997:308 313.
[8]GA M BARDELLA L M,DOR I GO M.H yb ri d an t s yste m HAS SOP:an
an t colony syst e m hybri d ized w i th a ne w local search for the sequen tial orderi ng prob le m[J].I NFORMS Journal on Computing,2000,12
(3):237 255.
[9]LEHMAN M M,RA M IL J F.Soft w are evol u tion i n t he age of co m po
nent based soft w are engineeri ng[J].I EE P r oceedings Soft ware,
2000,147(6):249 255.
[10]CHAUDET C,GREEN W OOD R M,OQUENDO F.A rch itect u re
dri ven soft w are engi neeri ng:s pecif y i ng,gen erati ng,and evolvi ng co m ponen t bas ed soft w are s yste m s[J].I EE Proceedings Soft ware,
2000,147(6):203 214.
[11]RASTOFER U,BELLOSA F.Co m ponen t based s oft w are engi neering
for d i stri bu ted e m bedded rea l ti m e syste m s[J].I E E Proceedings Soft ware,2001,148(3):99 103.
1664计算机应用研究第27卷。
