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

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

作者：韩天齐 宋波

来源：《微型电脑应用》2020年第04期

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

关键词：

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

中图分类号： 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：设计城市公交网络的层次性规划图像，并建立公交线网优化问题的数学模型。