基于遗传算法的城市轨道交通接运公交线网规划

未来大城市的客运交通系统一般会采用以下模式:以快速轨道交通为骨干,常规公交为主体,个体交通为补充.目前,全国约25座区域中心城市和省会城市都进行了不同程度的轨道交通线网规划,但这些轨道交通规划还局限于轨道交通系统本身,缺乏公共交通对轨道交通的竞争-支持影响分析.现阶段的问题是轨道交通与常规公交一体化的思想体系还不够完善,为了构筑快速轨道交通与常规公交相互支撑的协作体系,形成成熟的城市公共交通系统,在完成轨道交通线网规划工作后,要及早开始常规公交对轨道交通的接运客流研究工作.文中主要研究城市轨道交通接运公交线网规划方法[1]. 1 接运公交线网规划 接运公交(feederbus)是指以为轨道交通接运乘客为主要功能的公共汽车等公共交通方式,与轨道线网共同组成轨道-接运公交系统,又是常规地面公交系统的一部分(如图1所示)[2]. 接运公交线网规划通常采用以下两种方法. 1) 逐条选取法　即每次在备选接运站点集{N}中选出一个接运站点,在该站点上搜索出一条最优(接运效率最大)的接运公交路线,然后调整轨道交通路线上的客流量,进行下一条接运路线的选取直至没有可行的接运站点或没有可行的接运公交路线,每次所选中的路线构成接运公交线网. 2) 路线推荐法　即在各个可行接运站点上分别搜索一条或几条最优接运路线作为推荐接运路线,由决策者根据实际情况酌情进行选取,组成接运公交线网.在实际运用中可将两种方法结合使用.其中的关键部分是接运站点的选取和接运路线的优化布设. 文中采用第二种方法,在模型建立和求解过程中借鉴了模拟生物进化过程与机制求解问题的遗传算法使得精度更高,搜索速度更快. 2 轨道交通车站影响区离散化表示　　 轨道交通车站影响区可定义为轨道通过的重要客流集散枢纽点的影响范围,这部分的常规公交主要用于接运轨道交通上下客流,也就是接运公交线网规划的地理范围,其受轨道交通的影响程度从轨道车站向外逐渐减小.日本地铁建设经验认为,车站直接吸引范围为车站两侧各750m以内;在线路终端是以车站为中心,以750m为半径的圆形圈内.另据第36届国际轨道交通会议的资料,对于大多数城市来说,步行去轨道交通车站的最适宜距离,在城市中心区为500～600m,在边缘区为800～1000m. 轨道交通车站影响区范围的界定,一般方法是在调研车站附近居民步行到公交站台和轨道交通站台的时间差异,建立模型,最后根据不同站点(换乘站和中间站)给出不同的影响面积[3].一般来说与车站预测吸引客流量成正比向外辐射,同时结合车站所处地理位置和周边重要基础设施分布情况界定. 为了搜索影响区接运公交线网方案,遗传算法求解的轨道交通影响区是基于如下假设. (1)该地区的接运公交线网全部服务于一条轨道交通线路,当有两条或两条以上轨道线路时忽略其它的线路.(2)轨道交通车站上下客流已知,且不受接运公交线网优化的影响,视为恒定不变.(3)接运公交网络中各个站点上下车延误只与站点性质有关,与通过的公交车型无关.(4)仅考虑轨道线路一侧的交通影响区接运公交线网规划. 轨道交通车站影响区离散化表示形式如图2所示.图中不规则的影响区域被近似划分为m×n的规则小方块,公交车在每一节点只能水平或垂直移动.图中灰色区域为规划中障碍建筑的近似划分. 假设常规公交按由左往右的方向行驶,公交线路上的任一节点只能水平或垂直向前发展,一条由节点和弧组成的可行链,为了表示公交线路的延伸,定义 3 接运公交线网优化模型 公交系统的优化一般考虑的目标有总交通时间最小、服务乘客数最大、换乘率最小以及公交部门经济效益最大或路线每公里载客数最大等.这些目标是相关的.处理这个多目标规划问题有多种方法,如先以一个最重要的目标进行优化,保留多个较优解,再对各解进行多目标评价和决策;或将多个目标简化、合并为一个目标等.这里以总消耗CT(接运公交线网运营提供者消耗CS和使用者消耗CU之和)最小为优化目标[4]. 式中:uB为公交运营的平均费用;W为小方格的长宽;Tij为站点ij的延误消耗. 使用者价值CU由3部分组成,CA为到达消耗函数,指乘客步行到公交车站的时间消耗,CW为出行者等待时间消耗,CV为在车辆内的时间消耗.如式(5). 4　算　　法 用遗传算法求解这个最优化问题,按如下步骤进行. 1) 编码方式　以一辆公交车的工作路径为一个个体.如图2所示,公交车由起始位置沿图中粗实线运动到终点位置的路径.按矩阵形式路径可表示为{(6,1),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7),(5,8),(5,9),(4,10),(4,11),(3,12),(3,13),(2,14)}.每一坐标用二进制编码表示,则该个体为{0000,0110,0101,0010,0101,0011,…,0010,1110}. 2) 产生初始群体　初始群体是遗传算法迭代运算的起点,它由一定数目的个体所组成,当栅格数目较大时产生初始群体并非易事,若采用人工选择法,则费时费力;若采用计算机随机生成法,则要求路径具有目的性、无障碍性,使得路径生成算法比较困难,为此可截取原有公交线网的一段作为初始群体. 3) 适应度函数CT　个体适应度评价函数直接影响到遗传算法的优化效果,如前所述,以接运公交消耗最小为目标按式(9)计算CT. 4) 设计遗传算子. (1)选择算子　采用比例选择算子,使个体按照与适应度成正比的概率向下一代群体繁殖.(2)交叉、变异.(3)插入算子　把间断路径用自由栅格弥补,使之成为连续路径.可采用下列判别式来判断两相邻序号Nk,Nk+1是否连续. Δ=max{abs(xk+1-xk),abs(yk+1-yk)} 式中:xk,yk,xk+1,yk+1分别为Nk,Nk+1所对应的直角坐标,如图2所示.若Δ=1,则Nk,Nk+1连续,否则为不连续,按中值内插. (4)删除算子　将个体中两相同序号之间的冗余序号,连同两相同序号中的一个一并舍去,并简化路径. (5)输出几条推荐线路　仿真计算结果表明,利用遗传算法进行接运公交路线搜索与利用传统的二进制编码形式相比,初始群体产生简化,插入算子和删除算子又弥补了其中不至于出现间断路径,具有编码长度短、易于进行遗传操作等优点[5,6]. 参考文献 1 王兴海,陶志祥.江苏省沿江地区轨道交通线网布局研究.武汉理工大学学报(交通科学与工程版),2005,29(2):262～265 2 蒋冰蕾,孙爱充.城市快速轨道交通接运公交路线网规划.系统工程理论与实践,1998(3):130～135 3 刘伟华,刘惠敏,晏启鹏.轨道交通环线站点环内吸引区域研究.长沙铁道学院学报,2002,20(4):94～98 4 StevenChien,ZhaoweiYang,EdwinHou.Geneticalgorithmapproachfortransitrou teplanningandde-sign.JournalofTransportationEngineering,2001(2):200～207 5 潘劲松,李腊元.基于GA的动态时延受限多播路由算法.武汉理工大学学报(交通科学与工程版),2004,28(2):74～76 6　孙宝林,李腊元,陈　华.基于遗传算法的定时QoS多播路由优化算法.计算机应用,2004,24(11):1～3 信息来源于：中国城市轨道交通网