基于遗传禁忌算法的城市公交线网优化研究＊

周 媛 邓 卫 胡启洲

(西安外事学院工学院1) 西安 710077) (东南大学交通学院2) 南京 210096) (清华大学交通研究所3) 北京 100084)

城市公交线网优化旨在以公交乘客OD分布量为依据,以方便居民出行为目的,并兼顾公交企业效益,寻求使目标函数达到最优的公共交通线网布局方案.而公交线网优化的理论模型是一个多目标非线性规划问题,其影响因素和约束条件也很多.特别优化模型中目标函数和约束条件的确定以及实际问题规模的大小与其复杂程度呈指数增长关系.对于规模较大,布局复杂多样的公交线网优化问题,可行方案数较多,传统的优化算法不易得到满意的近似解,故笔者将建立合理的、可实施的优化模型,并采用遗传禁忌搜索算法弥补传统算法的不足,在所有可行的线路中选取整体最优的线路集.

1 公交线网优化模型的建立

公交线网优化目标可归结为公共交通效率最大化,而公共交通效率则是在一定的公共交通投入与该投入产生的对人们公共交通需求满足程度之间的对比关系[1].能够影响公共交通投入和需求满足程度的相关因素很多,本文从乘客利益、企业效益及社会环境的角度出发,运用系统科学的思想,确定相应的目标函数,分析相关约束条件,建立公交线网优化模型.

1.1 目标函数

1)乘客总出行时间最短[2]公交线网优化中应首先考虑乘客利益,合理线网应尽量节约乘客出行时间,保证较低的换乘率,提高乘客公交出行的直达率.因此,乘客总出行时间最短是公交线网规划社会整体效益最显著的目标.

2)公交运营收益最大[3]公交线网优化过程中,必须适当考虑公交企业的运营收益,使其能获得较好的收益而提高企业的运营活力.

式中：Vij为从交通区i到交通区j的公交客流量,人◦次;Pi为公交车运营票价,分/(km◦人◦次);Lij为从交通区i到交通区j的公交线长, km;Yh为公交车运营的油耗价值,分/km.

3)公共交通污染物排放最少 设污染物种类组成集合为G,则由公共交通引起的第g种污染物的排放量为

1.2 约束条件

公交线网的优化受到客运交通需求、道路场站及车辆条件、交通效率、交通政策等诸多方面因素限制,其主要约束条件归纳如下.

1)线路长度l 线路长度与城市规模、城市居民的平均乘距大小等有关.线路过长会增加系统的运营费用,过短则不利于运营调度,也增加了乘客的换乘次数.

式中：lmin,lmax分别为线路长度的上、下限,一般取公交线长约束为5 km≤l≤10 km.

2)线路的路段客流量不均匀系数 μ的限定[4]路段不均匀系数是指统计时间内营运线路某路段客流量与平均路段客流量之比值.路段不均匀系数大于1的路段被称为客流高峰路段,必要时考虑在规定时间内开辟区间车,一般不大于1.5为宜.

3)乘客平均转换次数η的限制 平均转换次数指全部乘客的换乘次数总和除以全部乘客人数的商.换乘要增加乘客途中耗费的时间和精力,使之感到不便.一般情况下,整个城市的平均换乘次数应少于1.5.

4)线路非直线系数δ的限制 线路拐弯过多,行驶不便,也易引起车辆的延误,所以一般情况下线路非直线系数δ＜1.4.

1.3 公交线网优化模型

在对公交线网优化基本原则、主要目标函数以及关键约束条件详细分析的基础上,本文将建立以寻求乘客出行时间最短、公交企业运营收益最大以及对环境污染最少,即以取得城市公共交通系统效率最大化为总体目标的可持续发展的公交线网优化模型,具体形式表述如下.

式中：α1,α2,α3分别为各分项目标的效率均衡系数,其他符号同前.

此模型旨在给定的关键约束条件下,获取目标函数的最优值,以达到公交线网的优化目标,属于多条线路的搜索组合优化,是一个典型的多约束0-1规划问题,这一复杂大规模优化问题必须借助先进的数学方法求解.遗传禁忌算法(tabu search,TS)是一种通用性和优化性能好的近似搜索算法,非常适于复杂大规模优化问题的求解[5],是解决这个问题的适宜算法.

2 遗传禁忌算法基本原理

本文提出的GATS混合算法就是先用GA进行全局搜索,使群体中的个体分布于各个最优解附近,再从群体中每个个体开始,用 TS算法进行局部搜索,改善群体的质量,有效结合GA并行的大范围搜索能力和 TS算法的局部搜索能力,力图在算法的收敛性能和避免局部极小方面有较大改善.混合策略的计算步骤如下.

步骤1 给定初始参数(包括最大迭代次数T,群体规模N,交叉概率Pc和变异概率Pm).

步骤2 确定编码方式,令t=0.

步骤4 选择.根据适者生存原则选择适应性强的个体为下一代的父本为个体1,…,N)的适应度,其被选择的概率

步骤5 交叉.对于选中用于繁殖下一代的个体,随机选择2个个体的相同位置,按交叉概率Pc在选中位置实行交换.

步骤6 变异.根据生物遗传中的基因变异原理,以概率Pm对个体进行变异运算,即对执行变异的串的对应位求反(0变为1,1变为0),产生子代群体

步骤7 准则判断.t＜T,令t=t+1,转步骤4;否则转步骤8.

步骤8 调用TS搜索过程,对子代群体中的每个个体进行局部搜索,改进群体点的质量,若改进后的群体点为 x1,x2,…,xN,其中目标函数最优的即为最终计算结果.

步骤9 停止运算,输出最终计算结果.

3 公交线网优化的遗传禁忌算法

城市公交线网由多条线路组成,在城市中符合既定约束条件的公交线路很多,在进行线网优化时,可对每一条线可行线路给出布设与不布设两种选择,在数学上可以归结为 0-1规划问题[6-9].对于规模较大、布局复杂多样的城市公交线网的优化则构成了大规模复杂函数的优化问题,用传统计算方法难以得到满足.采用GATS算法计算公交线网优化的过程如下,令xit代表第t次迭代的第i点,它是l维向量,代表一个线网布局方案.优化目标是寻找最优公交线网布局方案x＊使f(x＊)最小.

步骤1 优化模型的建立.根据兼顾乘客利益、企业效益最大以及环境影响最小的优化目标及与该目标密切相关的约束条件建立合适的城市公交线网优化模型.

步骤2 确定初始参数.公交线网优化模型目标函数值f(x)可用来衡量不同线网方案的优劣,若其被选方案较多则计算量很大,鉴于此,用GATS算法进行公交线网优化时,取最大迭代次数T=10,群体规模N=16,交叉概率变异概率

步骤3 可行线路集的形成和编码.根据节点性质及线路长度、非直线系数、路段客流量不均匀系数的约束,在整个网络中选取可行线路纳入可行线路集,每条线路在优化线网中有布设和不布设两种方案,分别用0和1表示,即将公交线网优化转化为0-1规划问题.

步骤4 初始化.令t=0,对可行线路集中的每条线路用0或1随机选取可构成一个初始公交线网,对每个公交线网进行检查,不合理网络取其适应值为0或某一固定值,继而产生 N个相对合理的初始公交线网方案.计算公交线网优化目标函数值.令

步骤6 若t＞T,转步骤8;否则转步骤7.步骤7 运行优化模型

1)运用GA进行线网搜索,对初始线网集进行选择、交叉、变异计算,输出N个新的公交线网方案

步骤8 调用TS算法,对GA最后一代公交线网中的每个方案进行局部搜索,改进线路质量,设改进后的公交线网为 x1,x2,…,xN,其中最优方案为x＊.

步骤9 停止运算,输出结果x＊为近似最优的公交线网优化方案.

4 案例分析

银川市全市总面积9 170.3 km2,建成区面积89.2 km2,中期规划(2015年)市域户籍人口160万,流动人口25万.公交出行在居民非体力出行中所占比例最高,达17.42%,根据居民出行产生和分布预测,规划年银川市中心区公交出行量为125万人◦次.

依据2015年银川市中区全日居民公交出行OD量预测结果,结合预测年居民出行方式结构以及城市用地规划布局,选取适当的效率均衡系数α1,α2,α3,建立银川市公交线网优化目标函数

进行银川市公交线网优化时,取最大迭代次数T=10,群体规模N=16,交叉概率Pc=0.95,变异概率Pm=0.005,运用GATS算法得到中期公交线网优化方案,由中心城区99条公交线路构成的公交网络.公交线路总长度为1 456.1 km,有公交服务的城区面积118 km2,纯线网密度3.73 km/km2,站点覆盖率(规划区内,R=300 m) 76.01%,路线重复系数2.0,乘客直达率26. 12%,线路路段客流量不均匀系数1.46,公交分担率可达到29%左右,公交出行成本约为0.036元/(人◦km).由此结果可知,银川市公交线网在乘客利益、公交企业效益以及社会效益方面都基本达到了优化目标,取得了令人满意的效果.

5 结束语

1)利用遗传禁忌算法对公交线网优化问题的计算方法进行了新的尝试,有效结合GA并行的大范围搜索能力和TS的局部搜索能力,在算法的收敛性能和避免局部极小方面有较大改善,为公交线网优化问题的求解提供了合理有效的新方法.

2)以公共交通效率最大化为公交线网优化的目标,选取与该目标密切相关的关键约束条件,建立兼顾乘客利益、公交企业效益以及对环境的影响程度的公交线网优化模型.充分考虑到城市公交所涉及的重要方面,所以对进一步发展公共交通系统,改善城市公共交通具有重要的理论意义和实用价值.

[1]吴世江.基于交通效率的城市公共交通路网布局模型[J].土木工程学报,2005(1)：117-119.

[2]胡启洲,石 琴,张卫华.城市公交线网优化的理想决策方法[J].交通运输工程学报,2005(5)：87-91.

[3]王 炜.城市交通规划理论及其应用[M].南京：东南大学出版社,1998.

[4]韩 印.城市公交线网调整优化PSO算法[J].中国公路学报,1999(3)：101-104.

[5]孙艳丰.基于GATS算法的城市土地使用规划问题研究[J].公路交通科技,2002(4)：122-125.

[6]胡 刚.城市公共交通网络及站点优化技术研究[D].南京：东南大学交通学院,2003.

[7]王 炜,杨新苗,陈学武.城市公共交通系统规划方法与管理技术[M].北京：科学出版社,2002.

[8]汤可夫,吴大为.基于改进遗传算法的公交线网整体优化方法[J].重庆交通学院学报,2004(6)：97-101.

[9]倪 捷,刘志强.基于蚂蚁算法的公交网络优化方法研究[J].交通与计算机,2007(1)：36-39.