基于遗传算法的城市公交骨架线网优化设计概要.docx

1、基于遗传算法的城市公交骨架线网优化设计概要收稿日期:2012-07-13;修回日期:2012-08-26基金项目:国家自然科学基金资助项目(70671108;湖南省科技厅科技计划资助项目(2011FJ6032作者简介:王佳(1980-,男,湖南益阳人,讲师,博士研究生,主要研究方向为城市公交、综合运输(jiaw_815126com ;符卓(1960-,男,湖南长沙人,教授,博导,主要研究方向为物流系统优化;杜靖毅(1989-,男,河南焦作人,硕士研究生基于遗传算法的城市公交骨架线网优化设计*王佳1,2,符卓1,杜靖毅2(1中南大学交通运输工程学院,长沙410075;2长沙理工大学公路工程省部共

2、建教育部重点实验室,长沙410076摘要:针对现有城市公交线网设计时普遍存在缺乏层次性规划的问题,提出了城市公交骨架网络的布局方法,构建了以线网直达客流密度与线网可达性最大为双目标的公交骨架线网优化模型,设计了一种改进的遗传算法。该算法通过引入动态惩罚系数确定适应度,以调整收敛速度;通过自适应机制确定交叉概率和变异概率,以调整搜索空间。算例分析的结果表明本算法比传统遗传算法具有更好的寻优性能。关键词:公交网络;公交骨架线;线网优化;遗传算法中图分类号:U121文献标志码:A文章编号:1001-3695(201202-4518-04doi :103969/jissn1001-3695201202

3、030Optimal design on urban public transitskeleton-network based on genetic algorithmWANG Jia 1,2,FU Zhuo 1,DU Jing-yi 2(1School of Traffic Transportation Engineering ,Central South University ,Changsha 410075,China ;2Highway Engineering Key Labora-tory of Ministry of Education ,Changsha University o

4、f Science Technology ,Changsha 410076,China Abstract :Aiming at the common phenomenon that lacking of hierarchical quality of the urban public transit network design ,this paper put forward a new method about building the urban public transit skeleton-network ,then it built an optimizationmodel of u

5、rban public transit skeleton-network ,which could achieve the dual goals of maximizing the accessibility of the net-work and the direct traveler density of the public transitIt improved the genetic algorithm to resolve the modelIn order to ad-just the convergence rate ,the algorithm defined the fitn

6、ess by introducing dynamic punish coefficientIt also utilized the cross-over probability and mutation probability by adaptive mechanism to adjust the searching spaceAt last ,the calculating exam-ple shows that the new genetic algorithm performs a better optimization-searching function than the tradi

7、tional onesKey words :transit network ;public transit skeleton ;network optimization ;genetic algorithm0引言优先发展城市公共交通是提高交通资源利用效率、缓解城市交通拥堵的重要手段,也是建设低碳交通系统的重要措施。实践已证明实行公交优先战略是解决城市交通问题最有效的途径之一。然而,许多城市在大力发展公共交通的过程中,由于公交网络设计不合理导致线网覆盖不均衡、乘客换乘不方便、乘客乘车时间长等问题,这严重影响了公交同其他交通方式的竞争力和对公众出行的吸引力。城市公交网络优化设计一直是发展公共交通系

8、统的核心问题,也是学者们研究的热点。Lee 等人1分析了交通需求与线网配置、发车频率的相互关系,提出了一种迭代算法解决TRNDP 的动态特性,在预测交通需求的同时生成新的线网方案1。Ngamchai 等人2研究了基于换乘的公交线网优化设计问题,其模型以用户费用和运营者费用最小为目标,按照线网生成、线路评价与改善的顺序对公交线网进行优化设计。Fan 等人3针对动态公交需求采用非线性整数规划模型进行网络设计,采用遗传算法程序从候选线路集中选出部分线路优化成网。胡启洲等人4利用效用函数建立多目标线性规划模型,采用蚁群算法搜索最佳公交线路。白子建等人5建立以乘客出行总时间最小化为目标的整数规划模型,通

9、过禁忌算法求解来设计公交网络。现有的成果为指导城市公交网络的布局提供了有力的理论与技术支持,但普遍存在着计算复杂、操作不便等问题,尤其是在线网设计时缺乏层次性的规划,导致设计的线路功能不明确、网络的运输效率不高。因此,有些学者提出了多层次公交线网设计理念,并针对不同功能、等级的线网分别采取不同的优化布局方法6,这为公交网络的规划与设计提供了一个更清晰的思路。然而,现有的研究很少有专门涉及到不同层次的公交线网优化。基于此背景,本文提出了城市公交骨架线网的设计思路,并重点研究了基于这一层次线网的优化方法。1城市公交骨架线网优化设计思路1.1城市公交骨架线网的定义城市公交骨架线路是在公交网络体系中起

10、支架作用的线路,它衔接区域内公交客流需求相对较大的点,主要满足直达第29卷第12期2012年12月计算机应用研究Application Research of Computers Vol29No12Dec2012客流的需要,以实现乘客快速、便捷的转移。公交骨架线路效率的高低直接影响整个网络效率,它相当于人体循环系统中的动脉。除了公交骨架线路,还需要一种在整个网络系统中起补充、完善作用的线路,它像毛细血管一样,衔接公交枢纽及其周边公交客流需求相对较小的点,主要是满足集散客流的需要,填补公交盲区。本文定义这一层次线路为城市公交接运线路,并提出建立“公交骨架线网+公交接运线网”的双层网络结构,如图1

11、所示 。如果公交客流点之间的乘客OD 量比较大,如图1中的点I 与J 、点L 与H 之间,为满足直达客流需求,可布设公交骨架线路,它们相交于点K ,形成了公交枢纽点;如果公交客流点之间的乘客OD 量不大,如图1中的点N 与M 之间,但它们与周边公交枢纽点K 有较强的联系,此时这两点之间没必要布设骨架线路,可布设以公交枢纽点K 为中心的放射线,分别辐射至点N 与M ,形成公交接运线路,点N 与M 之间的需求可经由点K 换乘实现。这种“公交骨架线路+公交接运线路”网络的结构,简化了现有主干线、次干线与支线的划分标准,同时还能保证网络层次分明、功能清晰。相对更多层次的网络,这种网络结构的设计相对简单

12、,实践性更强。此外,它更加提升了枢纽的地位,有利于推动城市综合交通的发展7。1.2城市公交骨架线网设计的基本思路根据上述定义,设计的骨架公交线路是将各公交客流需求量较大的点连接起来形成若干线路,并交织成网络,并要求布设的线路要承担区域内大部分直达客流需求,覆盖区域内主要城市道路。公交客流需求量较大的点将作为规划公交骨架线路的起始点。需求量较大是一个相对概念,由区域内总体客流量大小决定,可设定一个阈值,超过这一阈值的OD 点认为是需求量较大的点,本文称它们为公交乘客强需求OD 点。阈值的确定方法详见下节内容,公交乘客强需求OD 点选取后再确定骨架线路的可行集,并进行线网布局与优化8,9,整个流程

13、如图2所示。1.3公交乘客强需求OD 点的选取通过调查或预测建立公交乘客需求OD 矩阵B =(od ij n n10。矩阵中元素od ij 代表(i ,j 两点间的客流量大小,它是两点之间吸引强度的表现。矩阵中任意元素都关联两个公交需求点,只有当这两点之间的OD 量比较大时,也就是属于公交乘客强需求OD 点时布设公交骨架线路才有意义11。因此,通过设置阈值来确定公交乘客强需求OD 点,并将它们作为公交骨架线路的起始点。具体操作过程如下:a 由大到小依次选取B =(od ij n n的点,逐次累加,当选取点累计和超过总需求量(od ij 的20%(阈值时终止,选取的点作为预选OD 点。b 对预选

14、OD 点进行筛选,当预选点关联的起终点的空间距离过短或过长时,会影响线路的效率,直接剔除。将满足上述条件的点全部作为公交乘客强需求OD 点,并放入集合OD 强 。1.4公交骨架可行线路的确定集合OD 强中每个OD 之间均要布设一条公交骨架线路。每个OD 之间往往存在多条路径,不同路径有不同的运输效率。为了整个网络系统效率更佳,在OD 之间布设线路时,不一定选择运输效率最高的路径。因为单条路径运输效率最高并但不能确保整个网络系统效率最高,所以,某些线路布设时会做出牺牲,选择运输效率略低的路径。基于这种思想,将运输效率较高的路径作为布设公交骨架的可行线路。本文选取每个OD 之间效率排名前三位的路径

15、(均认为运输效率较高作为可行线路,以线路直达客流密度(单位长度上的直达客流量作为衡量线路效率的指标。假设OD 强中某点对应(i ,j ,记aij 是点i 与j 之间的第a 条路径,该路径直达客流量为D a ij ,长度为l a ij 。那么,定义aij =D a ij /l a ij (a =1,2,为a ij 的直达客流密度,将直达客流密度排列在前三位的路径放入可行线路集合ij 中。2公交骨架线网优化模型从每个可行线路集合ij 中挑选一路径作为布设线路,若干线路相互交织形成公交骨架网络。构造的网络尽量满足一定的优化目标。本文选定两个优化目标,分别是最大化网络直达客流密度与最大化网络可达性。1

16、线网直达客流密度其为网络中各线路直达客流密度之和,即=a ij x ij ,当aij 属于构造网络的线路时,x ij =1;否则,x ij =0。2线网可达性其定义为不超过两次换乘的客流量占总客流量之比,即=R /od ij ,R 是不超过二次换乘的客流量之和,od ij 是总客流量。因此,公交骨架线网的优化设计的模型可以描述为max =a ij x ij (1max =Rod ij(2st5l a ij max (S /槡/L 非,15/L 非(39154第12期王佳,等:基于遗传算法的城市公交骨架线网优化设计L a ij14(4D k06(5H k05(6x ij=0or1(7上述模型中,

17、式(1是第一优化目标,最大化整个线网的直达客流密度,体现运输的效率;式(2是第二优化目标,最大化整个线网的可达性,体现运输的公平性;式(3是单条线路长度约束,线路长度l a ij是点i与点j间第a条路径的长度,S是城市面积,L非取14;式(4是单条线路非直线系数约束,L a ij是点i与点j间第a条路径的非直线系数;式(5是网络覆盖率约束,网络覆盖率D k是指在第k个方案中,有公交线路经过的道路中心线长度与可通行公交的道路长度之比;式(6为不换乘比约束,不换乘比H k是指在第k个方案中,各线路直达客流量总和与总客流量之比;式(7是定义的0、1变量。3改进遗传算法设计3.1算法简介遗传算法(ge

18、netic algorithm,GA是一种进化算法,它的基本原理是仿效生物界中“物竞天择、适者生存”的演化法则。遗传算法是把问题参数编码为染色体,再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息,最终生成符合优化目标的染色体12。根据该优化问题的特征,本文在求解模型时对传统遗传算法进行了改进。3.2算法实现1编码它是GA中解的表现形式,解的编码称为染色体。根据城市公交网络优化问题的特征,本文构造了正整数编码方式,这种表示方式由直接产生的n个1 M间的正整数排列构成。每个排列构成一个染色体,即一个线网布局方案。n 是染色体的长度,即布局方案中公交骨架线路的条数。每个基因的基因

19、值为正整数,是指ij中被选路径的直达客流密度排名位置,它对应布设的一条公交骨架线路。基因座是根据公交乘客强需求OD的大小,按照由大到小从左至右依次排序。例如,某染色体为“1322132”,它表示一个具体的网络布局方案,该方案由7条公交骨架线路组成(n=7。左边第1位数“1”表示,在布设OD强中最大点时,选择直达客流密度排名第一的路径;左边第2位数“3”表示,在布设OD强中第二大点时,选择直达客流密度排名第三的路径;左边第3位数“2”表示,在布设OD强第三大点时,选择直达客流密度排名第二的路径,依此类推。2初始种群生成随机产生一个长度为n的正整数排列,形成一个染色体。根据可行集选取的方法,设定基

20、因大小不超过M,本文取M=3,即指定仅选择直达客流密度排名前三位的线路。设种群的规模为N,通过随机产生N个这样的个体形成初始种群。初始种群的每个染色体都要经过可行性检验,如果不满足单条线路长度约束、非直线系数约束、网络覆盖率约束和不换乘比约束的任意一项,均将其删除,再重新随机产生一条染色体进行检验。3适应度评估适应度表明个体或解的优劣性,由适应度函数确定。适应度越大适应能力越强,它是进行自然选择的唯一依据。适应度函数的值必须为正数,一般由目标函数或其变换得到。根据建立的城市公交线网优化模型,本文采用目标函数加动态惩罚系数的方法设计了第i个个体的适应度函数:f i=动态惩罚系数线网的直达客流密度

21、线网的可达性其中:动态惩罚系数与当前最好解的值有关,随着算法的逐步执行,惩罚系数逐渐增加。在算法执行初期,使用较宽松的惩罚系数以增大搜索空间,在算法执行末期,加大惩罚效果,使算法更快趋于收敛。4选择操作它是从旧群体中以一定概率选择优良个体组成的新的种群,以繁殖得到下一代个体。个体适应度越大,被选中的概率越大。根据上述建立的城市公交线网优化模型,采用改进的轮盘赌法。传统的轮盘赌法是完全随机地产生选择指针,可能产生大量个体位于区域某一部分,导致种群方差过小,降低种群的多样性。因此,随机生成的选择随机数不再在0,1中产生,而是先将0,1等分成N个子区间0,i/N (i=1,2,N,然后再在各子区间产

22、生随机数。改进后的轮盘赌法使得选择随机数更加均匀。此外,本算法在选择操作时还使用了最佳个体保存策略,将适应度最好的个体直接保存到下一代,以保证当前最优个体不会被遗传操作破坏。5交叉操作它是从种群中随机选择两个个体,通过两个染色体的交换组合,把父串的优质特征遗传给子串,从而产生新的优质个体。根据上述建立的城市公交线网优化模型,共设计了三种交叉算子,分别是单点交叉、两点交叉和均匀交叉算子,如图3 5所示。在交叉操作时,从三种交叉算子随机挑选某一种算子 。6变异操作其主要目的是维持种群的多样性。变异操作从种群中随机选取一个个体,再对选中的个体以一定的概率随机地改变某些基因。根据上述建立的城市公交线网

23、优化模型,采用2-交换变异策略 。7主要运行参数遗传算法的参数主要包括群体规模、进化代数、交叉概率和变异概率等。根据城市公交线网优化模型的特点,群体规模取20,进化代数取150,交叉概率p c和变异概率p m通过自适应机制自动调整。其思路是p c与p m随着适应度的变化调整,以避免发散或陷入局部最优。当适应度高时,降低p c与p m的值;当适应度低时,提高p c与p m值13,14。p c=k1(f0f/(f0*ff*fk3f*fp m=k2(f0f/(f0*ff*fk4f*f0254计算机应用研究第29卷其中:k 1=05,k 2=005,k 3=1,k 4=01;f 0为种群的最大适应值;

24、f为交叉的两个个体中较大个体的适应值;*f 为种群的平均适应值;f 为变异个体的适应值;p c 与p m 的值随着适应度趋向于f 0而减少。4算例分析根据上述设计思路,笔者用MATLAB 语言编制了城市公交骨架线路优化设计问题的遗传算法程序,并在CPU 为186GHz 、内存为512MB 的计算机上对以下案例进行了实验计算。25个公交需求点均匀分布在一个边长8km 的正方形区域内,每个公交需求点的坐标及需求量如表1和2所示,要求合理布设公交骨架线路,使得线网直达客流密度和线网可达性最大。表1各客流需求点分布表站点序号12345678910111213坐标(1,1(3,1(5,1(7,1(9,1

25、(1,3(3,3(5,3(5,3(9,3(1,5(3,5(5,5站点序号141516171819202122232425坐标(7,5(9,5(1,7(3,7(5,7(7,7(9,7(1,9(3,9(5,9(7,9(9,9表2公交OD 表1可行线路集合的确定先选取公交客流强需求点集合,再确定可行线路集合,计算结果如表3所示。表3可行线路集合表客流强需求点序号可行线路序号1231(2,252781318192025(12,25=4832381314192425(22,25=471238914192425(32,25=4552(4,23438131823(14,23=5364914131823(24

26、,23=5224914191823(34,23=4973(7,2471217222324(17,24=60071213141924(27,24=564789141924(37,24=5404(9,17914131817(19,17=688914131217(29,17=636914191817(39,17=5975(13,211318171621(113,21=6221312171621(213,21=5841318172221(313,21=5782优化模型的求解与分析分别采用改进遗传算法和传统遗传算法对上述案例进行优化求解,传统遗传算法在实验计算中采用以下参数:群体规模取20,终止进化代数

27、取150,交叉概率取095,变异概率取005,复制操作采用传统轮盘赌法。连续10次求解该优化问题,这两种算法均寻找到该问题的最优解,如图7所示。对比分析两种优化算法,改进的遗传算法在65次迭代时寻到最优值,比传统遗传算法节约30%左右的迭代次数。现实中公交线网布局涉及的线路更多,优化过程更加复杂,面对更大规模、更复杂的网络,改进的遗传算法寻优性能将更具优势。从优化设计的方案来看,第一优化目标=2772,第二优化目标=91.02%,优化解为“31132”,说明了该区域的公交骨架线网由五条线路交织而成,即“238914192425”“438131823”“71217222324”“91419181

28、7”和“1312171621”,如图8所示 。这五条骨架线路中仅有两条线路是选择直达客流密度排名第一的路径,为了确保整个网络系统效率最高,其他三条线路做出了一定的牺牲,这种局部的牺牲使得D k =0.6,H k =0.59。也就是说该方案在保证线网直达客流密度高达2772人次/公里及满足91.02%的乘客不超过两次换乘可达目的地的同时,还确保了这五条公交骨架线路覆盖了区域60%的道路,59%的公交乘客不需换乘可直达目的地。此外,该方案还充分满足了单条线路长度和非直线系数等条件。从图8可以看出,区域内还有部分道路未覆盖公交线路,可通过布设城市公交接运线路来补充和完善。公交骨架线网布设后,形成了若

29、干公交枢纽,如图8中点17、19等,为下一层次的接运线路布设奠定了基础。公交线网的这种优化设计更强调了骨架公交的优先地位,提升了公交枢纽的作用,符合当前优先发展城市综合交通和公共交通的思路。5结束语本文提出了构建“公交骨架线网+公交接运线网”的双层网络结构设计思路,着重研究了公交骨架线网优化设计问题,建立了以最大化网络直达客流密度和网络可达性为双目标的优化模型,并设计了改进的遗传算法,通过了实验验证,计算的结果表明该算法寻优性能好。公交骨架线网的优化设计为建立一个性能更完善的公交网络系统奠定了基础。对于公交骨架线网没有覆盖到的区域,可参考笔者在综合客运枢纽接运公交线路优化设计中的思路,进一步设

30、计公交接运线网。参考文献:1LEE Y J ,VUCHIC V RTransit network design with variable demandJ Journal of Transportation Engineering ,2005,131(1:1-102NGAMCHAI S ,LOVELL D JOptimal time transfer in bus transitroute network design using a genetic algorithm J Journal of Trans-portation Engineering ,2003,129(5:510-5213FAN Wei ,MACHEMEHL R BOptimal transit route network designproblem with variable transit demand :genetic algorithm approach J Journal of Transportation Engineering ,2006,132(1:40-514胡启洲,邓卫,田新现基于四维消耗的公交线网优化模型及蚁群算法J 东南大学学报:自然科学版,2008,38(2:304-308(下转第4533页1254第1