本站原创【摘 要】萤火虫算法是一种新颖的群智能优化算法,在该类优化领域中的应用很少.将萤火虫算法应用在公交线网优化问题中.公交线网优化是一个复杂的多目标优化问题,是影响公共交通效率的关键问题.根据算法和问题的特点,设计了基于矩阵的解表示方法.为解决GSO算法优化精度底、收敛速度慢的缺陷,提出自适应调整荧光素挥发因子ρ的萤火虫算法,通过matlab编程仿真,结果表明改进后的算法能将多目标的优化问题收敛到Pareto最优解,并具有均匀分布的Pareto曲线,证明能有效的解决公交线网优化问题.
【关 键 词】萤火虫算法,公交线网,多目标优化,Pareto最优解
1.引言
公共交通一直是节能减耗和缓解交通堵塞的最好交通方式,城市公交网络设计的目标需要考虑公交运营企业的利益和用户的利益这对矛盾体.线网优化以其自身的数学复杂性及约束条件复杂性,使得优化变的非常难.文献[1]将禁忌搜索算法应用在公交线网的优化中,利用已有知识构造禁忌表,优化不能全面反应实际情况,文献[2]以公共交通效率最大为目标,利用遗传禁忌算法进行优化,文献[3]的多目标模型除了考虑出行总时间和公交运营企业年收益率,还考虑进污染排放率、乘客直达率等,并应用遗传蚁群算法进行优化,虽然全面,也增加了计算的复杂性,并且有的目标是重复的,像直达率与出行时间,文献[4]将蚁群算法应用在公交线网的优化中,分别考虑了乘客总出行时间和公交运营投入,本文在此基础上,将乘客利益和运营企业利益作为优化目标,通过混沌加权[5]求得在不同侧重方面下达到的公交效率最大的目标.萤火虫算法（GlowwormSwarmOptimization,GSO）是Krishnanand和Ghose提出的一种新的群智能算法,已在函数优化领域得到成功应用,但在组合优化方面的应用还很少,尤其是针对大规模的多目标优化问题,本文将GSO算法用于公交线网问题的优化,不但丰富了公交线网问题的优化算法,也拓宽了萤火虫算法的应用领域.
2.公交线网优化问题
公交线网的模型对整个线网的优化起着决定性作用,通过已有的站点和路网优化得到最优线网,是多目标规划问题,综合乘客利益和运营企业利益这对矛盾体的考虑,引入权重控制系数,调节双方利益在整个线路运营中的不同权值,求解不同地域不同侧重点下的最优目标.公交线网模型如式（1）所示：
（1）
式中：是权重控制系数,,m公交线路总数,n为站点数目,为问题的解,是矢量的元素,线路被选中时为1,否则为0,为从站点i到j的乘客量,为从站点i到j的总出行时间,为第k条线路的发车次数,为第k条线路的长度.
3.萤火虫算法
3.1基本算法
基本GSO中主要有4个过程：荧光素更新、概率选择、位置更新和动态决策域更新.分别如式（2）～（5）所示：
（2）
（3）
（4）
（5）
3.2改进的萤火虫算法
研究表明,萤火虫算法中萤光素挥发因子ρ影响算法搜索性能.从式（2）可看出,ρ较小时,搜索过程受前一代荧光素影响较大,搜索随机性减弱,易陷入局部最优,ρ较大时,搜索过程受前一代荧光素影响较小,随机性增强,导致收敛速度降低.对于大规模的多目标优化问题,影响更为突出.本文通过自适应变化的荧光素挥发因子ρ来改善算法的性能.当算法陷入局部最优时,以式（6）自适应调整：
（6）
式中：k为迭代次数,C为调节因子,N为解群个数,的最大值,防止过大降低算法收敛速度.
3.3解的可行性检测
检测公交路线是否满足限制条件,就是检验站点之间是否连通,对于不满足条件的公交路线则通过随机交叉站点修正到满足条件.邻接矩阵表示路线连通情况[6],当站点i和j在某条线路上相邻时,,否则,这样TP是公交路线图的临接矩阵表示.
4.改进萤火虫算法在线网优化中的应用
解群的表示是采用矩阵存储当前乘车路线解群,,例如以4*4的矩阵表示有4条公交线路和最多4个公交站点的路线解群,行为公交路线,列为站点标号,对于站点实际数小于最大站点数的情况,在相应位置用0表示.
5.实验仿真
本文采用文献[8]中测试路网实例,以节点2、4、5、9、14、16、22、24为首末站点,以建立5条公交线路为例,应用改进萤火虫算法进行仿真.
表1线网优化结果
线路路经权重值
12-3-4-6-5a124-10-16-19-21-24a132-8-9-13-15-20-21-22a1>a2
414-13-10-11-17-18-22a1>a2
514-15-16-19-21-24a1>a2
由图1可以看出,非劣解在目标那个键分布比较均匀,基本均分布在Pareto最优解的前沿面,并且也可看出乘客利益和运营企业的利益是一对矛盾体,具有博弈特色,在设置公交线路时需要权衡两者设置线路,使两者均能达到能够接受的程度.
图1Pareto最优解
6.结束语
本文分别考虑了乘客利益和公交运营企业的利益,将公交线路模型处理成适合萤火虫算法求解的模型,提出了一种荧光素挥发因子自适应改进策略,实例结果表明了该方法的可行性.并从多目标的角度将最优解收敛到Pareto最优解的前沿,从计算设计的线路网络及Pareto最优解图来看,改进算法在一定程度上提高了规划的质量和效率.因此,改进萤火虫算法应用于城市公交线网规划的方法是可行和有效的.