收稿日期:2009󰀁09󰀁27;修回日期:2009󰀁11󰀁02󰀁󰀁基金项目:国家自然科学基金资助项目(20079862);国家教育部博士点基金资助项目(20040699025);2009年度浙江省教育厅科研项目研究课题;2010年度浙江省社科联研究课题和2010年度衢州市社科规划课题作者简介:余燕芳(1976󰀁),女,浙江衢州人,讲师,主要研究方向为计算机信息安全与智能化信息处理等(yuyanfang2008@126.com);陆军(1975󰀁),男,湖南长沙人,副教授,博士,主要研究方向为人工智能、计算机应用.基于动态交通仿真模型的最优路径选择方法*

余燕芳1,2,陆󰀁军2

(1.衢州广播电视大学,浙江衢州324000;2.国防科学技术大学计算机学院,长沙410073)

摘󰀁要:采用动态交通仿真模型INTEGRATION搭建了动态交通仿真平台,应用组件式蚁群算法来求解动态交

通信息诱导下的最优路径选择问题。实例表明,基于动态交通仿真模型的最优路径选择方法是可行的、正确的

和有效的。该方法易于理解和使用,具有很强的可重用性和可扩展性,为求解各类优化问题提供了可持续发展

的框架。

关键词:动态交通仿真;组件式蚁群算法;最优路径选择

中图分类号:U491󰀂1󰀁󰀁󰀁文献标志码:A󰀁󰀁󰀁文章编号:1001󰀁3695(2010)05󰀁1662󰀁03

do:i10.3969/.jissn.1001󰀁3695.2010.05.014

Shortestpathselectionapproachbasedondynamictrafficsimulationmodels

YUYan󰀁fang1,2,LUJun2

(1.QuzhouRadio&TVUniversity,QuzhouZhejiang324000,China;2.CollegeofComputers,NationalUniversityofDefenseTechnology,Changsha410073,China)

Abstract:ConstructeddynamictrafficsmiulationsystembyusingthedynamictrafficmodelINTEGRATION.Tackledtheshortestpathselectionwithdynamictrafficinformationbythecomponent󰀁basedantcolonyoptmiization.Thesmiulationexamplesuggeststhattheshortestpathselectionapproachbasedondynamictrafficsmiulationmodelsisfeasible,correctandeffective.Thisproposedapproachisveryeasytounderstandanduse,ithastherobustreusageandexpansibility;indeedprovideanexcel󰀁lentframeworkthatcancontinuallymiproveforsolvingdifferentoptmiizationproblems.Keywords:dynamictrafficsmiulation;component󰀁basedantcolonyalgorithm(CACA);shortestpathselection

󰀁󰀁随着机动车拥有量急剧增长而带来的交通拥堵、交通事故

增多和环境污染加剧等交通问题,越来越成为影响城市正常功

能发挥和城市可持续发展的重大难题。事实和经验证明,城市

交通拥堵等问题仅仅依靠交通基础设施的建设是不能完全解

决的。造成城市交通拥堵等问题的原因不仅是交通供给不能

满足交通需求所产生的供需矛盾,而且现有交通系统的运行效

率未得到充分利用,由交通网络效率浪费带来的交通问题同样

严重。目前,对交通信息条件下的路径选择行为的研究主要基

于意向调查和模拟仿真等方法。这些研究多局限于不同交通

信息措施对驾驶员路径选择决策本身影响的研究,或通过虚拟

路网简单研究交通信息下路径选择对路网运行状况的影响,而

较少结合实际交通网络分析交通信息下路径选择对整个路网

运行状态的影响,从而对信息策略与实施措施的制定和决策过

程提供不了紧密联系实际路网交通状况的理论与技术支撑。

鉴于上述背景,提出了一种基于动态交通仿真模型的最优路径

选择方法。

应用蚁群算法(antcolonyalgorithm,ACA)求解交通优化问

题是近年来研究的新方向[1]。蚁群算法[2]是一种源于自然界

中生物世界的新的仿生类随机型搜索算法,通过其内在的搜索

机制,已在一系列困难的组合优化问题求解中取得了成效。蚁

群算法已经在求解旅行商问题[3]、二次分配问题[4]和车间作

业调度问题[5]中取得了非常理想的结果。同时,为了克服基本蚁群算法的不足,人们对其进行了各种改进,以期提高搜索

效率,避免过早停滞。其中主要有Dorigo等人[6]提出的AntQ

System、Stutzle等人[7]提出的MMAS和Gambardella等人[8]提

出的HAS等。尽管蚁群算法在相当广阔的领域内均取得了很

大的成功,但现有方法仅从蚁群算法的基本结构出发设计软

件,很难用来求解不同种类的问题。研究者还经常需要尝试使

用不同的状态转移规则、信息素更新及参数调整策略来改进算

法性能。如果没有一个好的软件结构实现关注分离,任何小的

变化都有可能影响到整个软件结构,给算法的调整带来困难。

鉴于此,提出了一种组件式蚁群算法(CACA)。为了提高算法

的可理解性、可重用性和可扩展性,CACA强调以接口为中心

的设计理念,在结构上直接反映蚁群的本质思想和关键概念,

最大程度降低与问题的相关性。

仿真优化方法研究的是基于仿真的目标优化问题,基于模

型仿真给出的输出量通过优化算法得到最佳的优化结果。由

于实际交通系统的复杂性及其本身的随机性,最短路径的合理

规划问题需要使用仿真优化方法来解决。本文研究的总体思

路如图1所示。

1󰀁动态交通仿真模型

本章主要研究了动态交通仿真模型的构建与标定方法,搭

建了实例动态交通仿真平台。动态交通仿真的基本原理是:对第27卷第5期2010年5月󰀁计算机应用研究ApplicationResearchofComputersVo.l27No.5May2010引入动态交通模型进行需求分析,选取合适的动态交通仿真模

型作为搭建平台的基础;研究动态OD需求获取和交通流参数

标定方法;搭建与标定实例仿真平台,并对仿真平台的效果进行检验。本章所建立的仿真平台将作为研究动态交通信息下

最优路径选择的基本平台。

本文以真实交通网络为实例研究动态交通信息诱导下的

最优路径选择问题,要求应用的交通仿真模型能够满足以下条

件:a)能清晰地表现路网的几何形状,如信号灯等;b)能清晰地表现车辆间的相互作用,如跟车、车道变换时的相互作用;

c)能够细致地仿真路网交通流的状况,如交通需求的动态变

化、交通拥堵、排队溢出现象等;d)能模拟先进的交通信息策略,如提供实时交通信息、动态车辆诱导、可变信息板设置等;

e)提供结果分析的工具和输出反映路网实时运行状态的相关

运行参数;f)能提供图形化的交互界面。由于传统的静态交通仿真模型不能反映路网的动态特性的特点,本文研究需要引入

动态交通仿真模型。

1󰀂1󰀁仿真区域的选择

本文选取了浙江省丽水市城区的某区域路网作为交通仿

真路网实例。该区域路网东西两端距离约4km,南北两端距离约5km。该区域路网包含了城市快速路主路、辅路、主干

路、次干路、支路五种不同等级道路,路网功能较为全面完整。

该区域作为丽水市中心区域之一,该区域路网具有代表城市路

网一般交通特性的典型特征。本区域路网规模适中,既有代表

一般城市交通网络的典型特征,又可以保证基本路网数据调查工作量在一个可接受的合理范围内。在选取了上述实例路网

区域后,本文对该区域道路基本属性、交通信号控制等进行了

实际调查,并根据实际调查结果在INTEGRATION中搭建了路

网平台。所构建的路网平台包括266个节点,378条路段,内外OD小区共20对。

1󰀂2󰀁动态OD需求获取

本文采用的双层动态OD获取方法是一种结合传统OD

反推和浮动车OD随时间变化比例拆分的新方法。该方法通

过INTEGRATION模型中的OD反推模块QUEENSOD反推得

到仿真测试时段2h长的总OD,然后应用浮动车OD时变比例

将该2h总OD拆分为更小时段的动态OD矩阵。采用的双层动态OD获取方法技术路线如图2所示。

1󰀂3󰀁交通流参数标定

为了获取交通流的速度󰀂流量󰀂密度三要素之间的关系,

使得交通仿真平台更能精确模拟实际路网,需要对仿真路网内不同功能路段进行交通流参数标定。针对INTEGRATION模

型,具体需要标定的交通流参数是自由流速度、最大通行能力

下的速度、通行能力和阻塞密度。在开展交通流参数标定之

前,要先确定路段交通流参数标定的细致程度,设计相应的标定方案。1)分道路等级󰀁由于不同等级道路在城市路网中承担的

功能和设计标准不同,其交通流参数也各有不同。对于同等级的道路,由于相似的功能和设计标准,可近似认为其交通流参

数相同。对于全网路段,可以分道路等级进行标定,即对每个

等级的道路选取一定数量的代表路段作为标定样本,标定后的

交通流参数应用于该等级道路的所有路段上。2)分路段位置󰀁快速路出入口附近路段由于受到合流、

分流及交织等影响,其交通流特性与其他路段并不一致。对快

速路的基本路段和出入口路段交通流参数分别进行标定。

3)分交通流方向󰀁由于快速路的内环和外环的差异性,

其交通流参数也有一定差异性。快速路在路网中占据着重要地位,对其内环和外环进行细致的标定。

综合上述标定原理及标定方案,交通流参数标定的流程如

图3所示。

2󰀁组件式蚁群算法

本文将基于组件的软件工程技术(component󰀁basedsoft󰀁

wareengineering,CBSE)[9]来指导蚁群算法的软件设计,提出

一种新的组件式蚁群算法。CBSE强调的软件重用思想[10]在

蚁群算法的广泛应用中能够大大减少重复性的设计工作,提高

研究和开发效率。CBSE以接口为中心的设计思想[11]及组件本身的黑盒性质,能有效地将对算法某一方面的调整控制在一

个组件中,从而有利于蚁群算法的实验研究。CACA的主要思

想是:把蚁群算法软件中的各个组成部分作为可重用的软件组

件来开发;然后组装这些组件来开发整个蚁群算法软件系统;

替换和增加新的组件就可以实现整个系统的维护和扩展。

2󰀂1󰀁算法框架

本文组件式蚁群算法的软件设计从总体上划分为相对独

立而又相互联系的四个部分:优化问题定义、蚁群算法的搜索机制、求解过程的观察和控制、蚁群算法的求解策略。相应地,

CACA把这四个部分组织成四个逻辑包,每个逻辑包将密切相

关的概念组织到一起,不同逻辑包中的概念相对来说关系较为

松散。本文CACA的算法框架如图4所示。

󰀁󰀁在本文组件式蚁群算法的框架下,可以通过向该框架上组

装即插即用的软件组件来开发软件,软件的维护和扩展则是定

制和替换这些软件组件。在这样的模式下,需要严格地将组件 1663 第5期余燕芳,等:基于动态交通仿真模型的最优路径选择方法󰀁󰀁󰀁