改进遗传算法的公交线网优化研究

韩天齐 宋波

摘 要：

公交是一种主要的城市公共交通工具，针对现有城市公交线网设计时普遍存在缺乏层次性规划的问题，提出了改进遗传算法的公交线网优化方法。首先对当前城市公交线网优化的研究现状进行分析，然后设计相应的城市公交线网优化数学模型，采用改进遗传算法对城市公交线网优化数学模型进行求解，并通过引入动态惩罚系数确定适应度，以调整收敛速度;通过自适应机制确定交叉概率和变异概率，以调整搜索空间。最后采用具体算例对本文方法的性能进行分析。结果表明，这个方法不仅可以找到更优的城市公交线网优化方案，而且求解的效率得到了明显提升。

关键词：

城市公交线网; 层次性规划; 遗传算法; 收敛速度; 数学模型

中图分类号： TP301

文献标志码： A

Research on Bus Network Optimization Based on Improved Genetic Algorithm

HAN Tianqi， SONG Bo

（School of Cybersecurity， Chengdu University of Information Technology， Chengdu， Sichnan  610225， China）

Abstract：

Bus is a major urban public transport. Aiming at the problem of lacking hierarchical planning in the design of urban public transport network， this paper proposes an improved genetic algorithm for the optimization of urban public transport network. Firstly， the current research situation of urban public transport network optimization is analyzed， the corresponding mathematical model of urban public transport network optimization is designed， and then an improved genetic algorithm is used to optimize the mathematical model of urban public transport network optimization. Finally， the performance of the proposed method is analyzed by a specific example. The results show that the proposed method can find a better urban public transport network optimization scheme， and efficiency of solution has been improved obviously.

Key words：

urban public transport network; hierarchical planning; genetic algorithm; convergence rate; mathematical model

0 引言

相對于其它交通工具，公交能耗小，乘坐方便，价格低廉，人们出行乘坐公交频率高，许多城市提出了“公交优先”的口号，以解决城市交通拥塞问题[1-2]。但是，在平常出行过程中，亦存在如换乘难、等车时间长等问题，对公交竞争力产生不利影响，而城市公交线网设计与优化可以得到最优的公交线路，解决乘客等车时间长等难问题，因此公交线网优化研究成为城市公共交通管理领域中的一个重要研究方向[3]。

为了解决城市交通拥塞问题，世界各国都投入了大量的人力、财力进行了深入的研究，其中如美国、英国等国外发达国家的研究时间比较早，研究技术比较成熟，提出了许多有效的公交线网优化方法，而国内的公交线网优化研究起步相对比较晚，但是由于受到众多学者的关注，发展速度相当快，学者们提出了一些性能比较优异的公交线网优化方法[4]。公交线网优化研究可以划分两个阶段：第一个阶段是手工阶段，另一个阶段是自动智能阶段。手工阶段主要为城市公共交通管理领域的专家根据相关数据、资料和自身的经验建立一些公交线路，该阶段主要是由于公交线路少，路线比较简单，但是该种方法得到最优公交线路耗时比较长，需要大的人力，公交线网优化不仅成本高，而且不灵活，难以保证得到最优的公交线网，对于大规模的公交线网，其缺陷就更加明显，无法满足公交线网优化的在线、实时性要求[5]。自动智能阶段是信息技术、智能技术、遥感技术以及一些优化理论融合的结果，它们首先对一个城市交通的公交线路进行分析，设计公交线网优化目标，如：用户费用和运营者费用最低，用户出行时间最短等，根据优化目标建立公交线网优化数学模型，然后采用动态规划算法、非线性整数规划算法、遗传算法、蚁群算法等进行求解，对最优公交线路进行搜索，得到了比较好的公交线网优化方案[6-8]。然而在实际应用中，这些算法存在一定的缺陷，如动态规划算法、非线性整数规划算法的公交线网优化问题求解效率低，无法满足现代大型城市交通管理的要求;遗传算法的交叉概率、变异概率固定，易使种群多样性变差，无法获得全局最优的公交线网优化方案;蚁群算法的初始激素深度采用随机方式确定，使得初始解比较差，从而影响最终的公交线网优化结果[9]。

针对当前公交线网优化方法存在的计算时间复杂度高、优化速度慢、求解精度差等难题，设计了一种改进遗传算法的公交线网优化方法，首先对基本遗传算法的工作原理进行分析，对其不足进行相应的改进，然后将其引入到了公交线网优化问题的求解中，最后进行了仿真对比实验，结果表明，本文方法加快了公交线网优化问题求解的速度，提高了公交线网优化问题求解精度，可以应用于具体的城市交通管理中。

1 公交线网优化的数学模型

1.1 相关概念

在一个城市交通系统中，公交线网是一种主要线路，通常对客流需求大的点进行连接，其运行效率直接决定了整个城市交通运营的效率，是一个城市人口出行的动脉。公交线网的线种包括两种类型，一种类型为骨架线路，其相当于主动脉，另一种为城市公交接运线路，相当于小动脉，对交通网络起着补充作用，这样一个公交线网可以划分为2个层次：骨架线网和接运线网，它们具体如图1所示。从图1可知，当两个点之间的乘客量很大，那么就可以在它们之间建立骨架线路，如果两个点之间的乘客量小，那么就没必要布设骨架线路，建立接运线网，方便乘客的换乘，如图1所示。

1.2 建立公交线网优化的数学模型

根据相关研究，两个节点i，j之间经常包括许多个可行线路，它们组成一个集合rij，线路之间相互交织形成一个公交线网，公交线网优化目标为：直达客流量最大、线网可达性最大，具体如下[10]。

（1） 直达客流量为公交网各线路的直达客流量和，如式（1）所示。

式中，当点i，j之间的第a条路径属于构造网络的线路时，xij=1否则，xij=0，ηaij表示i，j之间的第a条路径的直达客流量密度具体如式（2）所示。

式中，daij和laij分别表示i，j间的第a条路径的直达客流量和路径长度。

（2） 线网可达性为不超过两次换乘的客流量（R）和总客流量∑∑odij比值，计算式如式（3）所示。

式中，odij表示两个节点i，j之间的所有客流量。

那么公交线网优化的数学模型如式（4）所示。

2 改进遗传算法的公交线网优化方法

2.1 遗传算法以及不足

遗传算法是一种模拟自然界生物进化过程的群智能优化算法，将要解决问题的可行解与个体相对应，所有个体组成一个种群，通过种群模拟自然界生物进化过程，个体进入下一代主要通过适应度值的高低来决定，通过选择概率选择当前种群中适应度函数值最高的个体直接进入到下一代种群，根据交叉概率和变异概率产生新的个体。常规遗传算法的交叉概率、变异概率的值采用固定方式，到了进化后，种群多样性变差，搜索停滞不前，影响问题求解的速度和精度，为此本文对其进行改进。

2.2 遗传算法不足的改进

改进遗传算法的基本思想为：如果个体适应度小于种群适应度均值，那么表示其性能比较差，一旦它被选中，那么就要采用较大的交叉概率和变异概率，不然就采用较小的交叉概率和变异概率，交叉概率和变异概率的自适应变化形式如式（5）、式（6）所示。

式中，fmax为群体中最大适应值，favg是群体的平均适应值;f′和f分别为交叉和变异后的最大适应度值，ki（

i=1，2，3，4）為0～1中的常数。

3.3 改进遗传算法的公交线网优化方法

3.3.1 改进遗传算法的公交线网优化方法设计

（1） 个体编码，编码是遗传算法解决公交线网优化问题，首先需要根据公交线网优化问题的特征点设计，本文采用十进制编码方式，个体长度为n，个体编码表示公交网中的线路数量，个体代表一种公交线网优化方案。

（2） 初始种群生成，常规遗传算法采用随机方式产生初始种群，即公交线网优化方案的可行解集合，这样种群个体单一性比较严重，影响公交线网优化问题的求解，为此本文采用均匀方式产生初始种群，使得个体在公交线网优化方案的可行解空间均匀分布，有利于获得更优的公交线网优化方案。

（3） 建立适应度函数，因为适应度函数决定着种群的进化方向，结合公交线网优化问题的特点，引入动态惩罚系数构建适应度函数，具体如式（7）所示。

式中，ω表示动态惩罚系数。

（4） 选择策略的确定，当前遗传算法有两种选择策略：轮盘赌策略和锦标赛策略，相对于轮盘赌策略，锦标赛策略的稳定性更好，因此本文采用锦标赛策略选择部分优秀个体直接进入下一代种群。

（5） 交叉和变异操作的确定，根据公交线网优化问题的特点，本文采用单点交叉概率和随机变异方式。

3.3.2 改进遗传算法的公交线网优化步骤

Step1：设计城市公交网络的层次性规划图像，并建立公交线网优化问题的数学模型。

Step2：建立公交线网优化方案的可行解集合，初始化种群。

Step3：初始化种群中个体采用十进制方式进行编码，每一个个体代表一种公交线网优化方案。

Step4：采用适应度函数值对每一种公交线网优化方案进行评价，并对它们进行排序。

Step5：根据锦标赛策略选择部分适应度函数值较高的个体进入下一代种群。

Step6：根据式（5）计算交叉概率，并随机选择两个个体进行单点交叉操作，选择较优的个体进入下一代种群。

Step7：根据式（6）计算变异概率，并随机选择一个个体进行变异操作，与父代个体进行比较，选择较优的个体进入下一代种群，进化迭代次数增加。

Step8：判断是否达到终止条件，若达到就输出最优个体，不然跳转到Step4继续执行。

Step9：对最优个体进行解码，得到最优的公交线网优化方案。

3 公交线网优化方法的算例分析

采用Vc++6.0语言编程公交线网优化问题求解的改进遗传算法程序，仿真测试环境为：Intel 酷睿i3 8100 CPU，金士顿DDR3 1600 8G RAM， Windows 10操作系统为，选择常规遗传算法进行对比测试。改进遗传算法的相关参数如表1所示。

对于一个具体公交线网优化问题，采用改进遗传算法和常规遗传算法对最优公交线网优化方案进行求解，两种算法均进行5次实验，它们找到最优解的迭代次数分别如图2所示。从图2可以清楚的看出，改进遗传算法找到最优公交线网优化方案的迭代次数明显减少，加快了公交线网优化问题求解的速度，可以更好满足大中城市交通管理要求。

统计改进遗传算法和常规遗传算法的公交线网优化方案对该城市道路覆盖率和公交乘客不需换乘百分比如表2所示。从表2可以发现，改进遗传算法的公交线网优化方案道路覆盖率达到90%以上，远远高于常规遗传算法的公交线网优化方案道路覆盖率，同时公交乘客不需换乘百分比也明显高于常规遗传算法的公交线网优化方案，结果表明，改进遗传算法获得更加理想的公交线网优化方案。

4 总结

本文提出了改进遗传算法的公交线网优化方法，以最大化网络直达客流量和网络可达性为优化目标建立公交线网优化数学模型，引入改进遗传算法对公交线网优化数学模型进行求解，并通过了仿真实验验证了改进遗传算法的公交线网优化方法的有效性和优越性。

参考文献

[1] 李贞镐，金德鹏. 基于移动大数据的城市深夜公交线路改进方案[J].计算机工程， 2018， 44（4）： 23-27.

[2] 袁长伟，吴群琪，袁华智，等. 考虑轨道交通作用效应的城市公交线网优化方法[J]. 公路交通科技，2014，31（8）：119-125.

[3] 齐振涛，李文勇，余子威，等. 基于直达客流量的公交路径优化模型及求解算法[J].桂林電子科技大学学报，2016，36（5）：412-415.

[4] 钱萌，彭张节，程树林，等. 基于综合评价指数的城市公交线路选择优化模型[J]. 吉林大学学报（信息科学版），2008，7（2）：180-185.

[5] 王健，曹阳，王运豪. 考虑出行时间窗的定制公交线路车辆调度方法[J].中国公路学报， 2018， 31（5）： 143-150.

[6] 陈丹，徐文远. 基于遗传算法的轨道交通与常规公交线路优化方案[J]. 西北大学学报（自然科学版）， 2016，46（3）：364-370.

[7] 潘若愚，褚伟，杨善林. 基于Dijkstra-PD-ACO算法的大城市公交线路优化与评价方法研究[J].中国管理科学， 2015， 23（9）：106-115.

[8] 于晓冬，孙宇. 混合策略遗传算法的公交线路优化模型研究[J]. 计算机与数字工程， 2012， 40（1）： 14-15.

[9] 王宁，曹为政，储晓雷. 采用元胞遗传算法的轨道交通接运公交线路优化[J]. 交通科技与经济， 2018，20（4）：13-18.

[10] 王佳，符卓，杜靖毅. 基于遗传算法的城市公交骨架线网优化设计[J].计算机应用研究， 2012， 29（12）： 4518-4521，4533.

（收稿日期： 2019.02.13）