您的当前位置：首页基于蚁群算法的公交路线走向模型

基于蚁群算法的公交路线走向模型

来源：化拓教育网

第6卷第2期江南大学学报(自然科学版)Vol.6　No.2　　　　　　　2007年4月Apr.　2007JournalofSouthernYangtzeUniversity(NaturalScienceEdition)

　文章编号:1671-7147(2007)02-0239-04

基于蚁群算法的公交路线走向模型及其求解

金孟合,　王慧3

(浙江大学系统工程研究所,浙江杭州310027)

摘　要:建立了新的公交路线走向的数学模型.该模型以动态直达人数为目标,路线的非直线系数为条件,并结合蚁群算法给出了求解路线优化设计模型的相应步骤.通过对案例的仿真,证明了该模型及求解算法的可行性和有效性.

关键词:公交网络;路线走向;动态直达人数;蚁群算法中图分类号:O224文献标识码:A

ANewBusRoutingProblemModelandItsSolution

AlgorithmBasedonAntColony

JINMeng2he,　WANGHui3

(InstituteofSystemsEngineering,ZhejiangUniversity,Hangzhou310027,China)

Abstract:Busroutingproblemisanimportantpartofpublictrafficnetworkdesign.Inthispaper,themathematicmodelofbusroutingproblem,whichtakesthemaximumsumofdynamicnonstoppassengerswithbendingmodulusrestricted,isestablishedandthesolutionalgorithmbasedonantcolonyalgorithmisdeveloped.Thefeasibilityandefficiencyofthealgorithmareverifiedbyapplyingittoasamplesystem.

Keywords:publictrafficnetworkdesign;busroutingproblem;dynamicarrivedpeople;antcolonyalgorithm

　　公交网络设计中路线走向问题是指在公交网络优化设计过程中,在确定起讫点以后,以某一优化指标(如直达人数最多、路线最短等)为目标函数,选出一个最佳的公交路线走向方案.但在现实生活中,一条公交路线除了起点及终点外,中途所经过的站点和路段也很重要,因为公交路线的走向选择会受到各种,如最好避开拥挤路段、非直

　　收稿日期:2005-11-23;　修订日期:2006-01-12.　　基金项目:浙江省自然科学基金项目(601119).

线系数(指公交路线的实际长度与空间直线距离之

比)不能太大等等,所以必须考虑公交路线的走向问题.

目前,许多研究者将这一问题简单处理,即起讫点A和B一旦配对,AB间的路线直接按最短路线法则确定[123],这样做虽然简单,但却不太符合实际,也可能不符合优化目标.因为在不是以路程长

　　作者简介:金孟合(1982-),男,浙江温州人,系统工程专业硕士研究生.

　　3通讯联系人:王慧(1959-),女,江苏无锡人,教授,硕士生导师.主要从事复杂过程模型化及优化,智能控制与

计算智能研究.Email:hwang@iipc.zju.edu.cn

240

　　　江南大学学报(自然科学版)　　　　　　　　　　　第6卷　

以及富于建设性贪婪启发式搜索[426].

在运用蚁群算法时,首先将公交路线规划区内的所有n条路段从1到n编号,每一条路段的初始信息量都是相等的.设τx=C(x=1,2,…,n),C是一个常数.寻优过程中,其信息量τx会随着蚁群经过后所留下的外激素量的变化而变化.

在运动过程中,蚂蚁k在路口根据路线x上信息量的转换概率决定选择哪一条路线,转换概率k

Px(t)表述为

αβτx(t)ηxk

(2)Px(t)=αβτx(t)ηx∑l∈A度为单一优化目标的情况下,最短路线不一定是最优路线.针对这种情况,文中提出了一种基于蚁群算法求解的公交网络设计中路线走向问题模型,设计了相应的求解算法及程序,并用该算法对文献[1]中的一个算例进行了仿真.结果表明,文中提出的优化方法是可行、有效的.如果将文中模型和交通出行矩阵(OD)流量分配算法相结合,还可以依次生成多条路线,进而形成公交路网.

1　模型的建立

在公交网络设计中,一条路线所确定的直达人数是一个重要的优化目标.大多数文献都是将起讫点之间的OD量视为一个不会随着路线改变而变化的固定值.然而,由于出行手段的多样化,人们外出有了更多的选择.例如一条公交路线的非直线系数必然会对这条路线的吸引人数产生一定影响,即若这条公交路线绕弯太多,使乘客出行的时间成本过高,那么乘客就会减少,该条路线的直达人数随之减少.一般要求非直线系数k≤115

[3]

式中:A为蚂蚁在路口能够选择路段的集合,不包括

已经过的路段;α,β为蚂蚁在运动过程中所积累的信息及启发因子在蚂蚁选择路段时所起的不同作用;η为选择路段i的期望程度,如路段交通太拥挤,希望能避开,那η的数值就可以取路段流量的倒数.

在蚂蚁k到达终点以后,所有路段的信息量都需要更新

ττx(k-1)+Δτx(k)=ρx(k-1,k)

(3)　　

　　　　　　x=1,2,…,n

ρ为设定的一个系数,指路段上的信息量会随式中:

着时间的增加而减少;1-ρ为信息量的蒸发系数;Δτx(k-1,k)为在蚂蚁k到达终点以后路段i上信息量的改变量,表达式为Δτx(k-1,k)=

F(k)Q

.因此,为了兼

顾直达人数和路线非直线系数,考虑到路线非直线系数对直达人数的影响,文中提出了动态直达人数概念,因为设计的公交路线可能是非最短路径,有部分乘客可能会选择其他的出行方式,导致直达人数存在一定的变化,故将动态直达人数定义为直达人数除以路线的非直线系数.以规定的起讫点之间动态直达人数最多为目标函数,非直线系数为约束条件,建立了设计公交路线走向的数学模型

maxF=

cijkij

(1)

若蚂蚁k经过x若蚂蚁k未经过x

(4)

其中

　　　s.t.　　

kij=

SijDij

kij≤k′

式中:k′为kij所能取的最大值,是一个设定的常数;

F为起讫点i,j配对后整条线路上动态直达人数;cij

式中:Q为一常数;F(k)为蚂蚁k所得规划方案的

目标函数值,可由式(1)计算而得.

基于蚁群算法的公交路线走向优化计算步骤如下:

1)指定起讫点,计算循环次数为Nmax,N=0;2)设所有路段的初始信息量τx(0)=C　x=1,2,…,n,共有m只蚂蚁,F=0,k=1;

3)N=N+1,若N>Nmax,退出计算;4)蚂蚁k从起点出发,根据可选路线x上信息

为起讫点i,j配对后整条线路上的直达人数;Sij为起讫点i,j配对后整条线路的长度;Dij为起讫点i,j在地理上的直线距离.

量的转换概率Pkx(t)决定选择哪一条路线,一直到到达终点,若还没有达到终点就没有可选路线,说明寻路失败,重复步骤4;

5)到达终点,计算Sij,Dij,kij,若kij>k′,则重复步骤4;

6)kij≤k′,计算F(k),由式(3)、式(4)重新计算所有路段的信息量τx(k)　x=1,2,…,n,若

F(k)≥F,则F=F(k),画出蚂蚁k所经过的路线;

2　蚁群算法原理及在公交路线走向

问题模型中的应用

　　根据公交路线走向设计的优化命题,作者选择了蚁群算法.这是由意大利DorigoM等首先提出的一种模拟蚂蚁外出觅食时在所经过路径上留下一种“外激素”行为的启发式优化算法[4],其主要特点是整个蚂蚁群的行为形成了正反馈、分布式计算

7)k=k+1,若k=m+1,则重复步骤2,反之,

　第2期则重复步骤4.

金孟合等:基于蚁群算法的公交路线走向模型及其求解241

3　仿真结果

利用文献[1]例子,图1为某区域的交通分区及交通网络,该区域的乘客OD量见表1.

蚁群算法参数设置为:C=018,α=1,β=1,ρ=018,η=1,Q=10000,m=50,Nmax=50,反复计算表明优化结果对初值并不敏感.

表1　公交乘客OD量表

Tab.1　PassengersODtableOABCDEFGHIJKL

FGHI

图1　某区域的交通分区及交通网络

Fig.1　Regiontrafficnetwork

035751175835020241108381502851

3470501799381108507040703080

50149107014711235267611012339

7638016910684241131506112842113

3473774017010128404158783929

20141081112311110393618794150

395162128384102714152051

1126773141473228015192825

31396272621613140202527

1428096121588116182102839

23283339413421282829024

597741103805860302941210

　　现以A为起点,C为终点,求解.当非直线系数

k′取不同值时,所对应不同的最优路线.仿真结果如图2所示.

(c)k′=117

图2　仿真结果

Fig.2　Simulationresult

(a)k′=114

　　1)图2(a)中,当k′=114时,Fmax=3982195,输出道路是AaFDKLC.

2)图2(b)中,当k′=116时,Fmax=410115,

输出道路是AaEbFDKLC.

3)图2(c)中,当k′=117时,Fmax=4216190,

输出道路是AGEbFDKLC.

仿真结果显示,当非直线系数k′=114,此时的最佳路线就是最短路线;而当非直线系数

(b)k′=116

k′=116或k′=117时,程序所得起讫点之间路线

242

　　　江南大学学报(自然科学版)　　　　　　　　　　　第6卷　

对问题,文中提出动态直达人数的概念,据此概念

建立了一个确定公交路线走向的模型,应用蚁群算法给出了求解路线走向的具体步骤,并进行了算例的仿真.

运用文中的模型可以很容易地求解任意两点配对所能够得到的最大直达人数,为优化配对提供数据;如与OD流量分配算法相结合,还可以依次生成多条优化的公交路线,进而形成更趋合理的公交路网.

的优化目标函数值都要大于最短路线的优化目标函数值.

　　上述计算结果表明:在k′=114时,最短路线就不是最优路线,这时使用最短路法则所确定的路线不符合优化目标.

4　结　语

为解决公交网络设计中的如何确定起讫点配

参考文献:

[1]王炜.数学规划方法在公交网络优化中的应用[J].系统工程,1990,8(3):44251.

　WANGWei.Applicationofmathematicalprogrammingmethodinoptimizationofpublictrafficnetwork[J].SystemsEn2

gineering,1990,8(3):44251(inChinese).

[2]王炜.一种简便实用的公交网络优化方法[J].交通与计算机,1990(3):40247.

　WANGWei.Asimpleoptimalmethodinpublictransportationnetwork[J].ComputerandCommunications,1990(3):402

47(inChinese).

[3]杨超,李彬.城市公共交通线网优化的图论模型与算法[J].同济大学学报:自然科学版,1998,26(3):2942298.

　YANGChao,LIBin.Graphtheorymodelandalgorithmofurbanpublictransportnetwork’soptimization[J].Journalof

TongjiUniversity:NaturalScience,1998,26(3):2942298(inChinese).

[4]DorigoM,ManifzzoV,ColorniA.Theantsystem:optimizationbyaclonyofcoperatingaents[J].IEEETranslationon

Systems,ManandCyberneticsPartB:Cybernetics,1996,26(1):29241.

[5]刘闯,韩印,江丽炜.智能化城市公共交通网络优化和设计模型研究[J].佳木斯大学学报:自然科学板,2003,21(3):2472

251.

　LIUChuang,HANYin,JIANGLi2wei.Studyontheoptimizationanddesignaboutintelligentpublictransportnetwork[J].

JournalofJiamusiUniversity:NaturalScienceEdition,2003,21(3):2472251(inChinese).[6]张纪会,徐心和.一种新的进化算法———蚁群算法[J].系统工程理论与实践,1999(3):84287.

　ZHANGJi2hui,XUXin2he.Anewevolutionaryalgorithmantcolonyalgorithm[J].SystemsEngineering2Theory&Prac2

tice,1999(3):84287(inChinese).

(责任编辑:邢宝妹)

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文