基于ESGA 遗传算法的公交网络模型设计与仿真

武可心

（西安交通工程学院交通运输学院，陕西西安 710300）

公交网络是城市公共交通系统的重要组成部分之一，是缓解城市交通压力和提高交通资源利用率的重要手段。现有的公交网络研究成果[1-4]存在算法过于复杂、运行效率低等问题，导致公交网络的运行资源得不到充分利用。为满足乘客对公交运行网络的需求，基于需求响应（Demand Responsive Transit，DRT）的公交网络规划策略成为公交网络优化的重要研究方向之一，以乘客需求为导向，在最大限度满足乘客需求的前提下，降低公交运营成本，增加公交收益，从而提升公交网络的利用效率。其中，遗传算法可作为路径搜索和优化的有效方法，适应于公交路径优化问题。该文为提升遗传算法的收敛速度和改善搜索效果，提出了一种基于优质选择遗传算法（Elitist Selection Genetic Algorithm，ESGA）的公交需求模型解算方法，并通过计算机仿真验证了该算法的有效性和快速性。

1 公交网络路径数学建模

为了对公交网络线路进行建模，需要设定一些必要的限制条件，在限定的研究区域内，假定区域内的乘客位置信息、乘车需求、出行费用预算等乘客信息已通过调研获取[5]。公交公司依据所获得的乘客信息规划线路，以响应乘客的出行需求，在车辆数量和容量的限制条件下，规划公交路线的起点、终点、停靠点以及途径路径，将运营利润函数作为目标函数，通过路径的优化实现运营利润的最大化[6-7]。建模限定条件如下：仅当乘客愿意支付的出行成本预算不小于公交公司限定最低成本时，乘客的出行需求才会得到响应；假定乘客均会前往距离最近的站点乘车；假定区域内的公交车辆均具有相同的起点和终点站[8]。

在公交路线数学建模中，将公交运营利润最大化作为目标，建立目标函数公式为：

设定的约束条件一为线路中运行的公交车辆数目小于或等于区域内拥有的车辆总数，约束公式表示为：

约束条件二为每辆公交车辆的载客人数小于或等于车辆允许乘载的最大人数，约束公式表示为：

式中，yai表示第a位乘客在第i个车站是否选择乘车，1 表示肯定，0 表示否定；Qc表示车辆的最大载客数量。

约束条件三表示仅当乘客愿意支付的出行成本预算不小于公交公司限定最低成本时，乘客的出行需求才会得到响应，约束公式表示为：

式中，p0表示公交公司限定的成本下限。

2 基于ESGA遗传算法的模型求解

公交网络路径优化主要包含站点规划和路径规划两方面的内容，首先需要对区域内的公交停靠站点进行优化，这里采用K-means 聚类算法[9-10]规划站点分布问题，该聚类算法可利用乘客所在的地理位置信息将区域分割为K个簇，将每个簇的中心位置作为站点位置，这样可以保证每个乘客与其所在区域簇的站点距离是最短的。基于K-means 聚类算法的站点规划流程如图1 所示。

图1 基于K-means算法的站点规划流程

完成站点规划之后，关键问题在于对公交线路的规划，文中提出一种基于ESGA 遗传算法的公交路径模型求解方法，相对于较常用的RWSGA 遗传算法，该方法具有更快的运算和收敛速度。ESGA 遗传算法的主要原理是通过计算上一代群体的适应度，按照群体的适应度筛选出优质种群，然后在下一代的选择过程中，将适应度值较低的个体替换为优质种群。ESGA 遗传算法的主要流程如图2 所示。

图2 ESGA遗传算法主要流程

2.1 编 码

在公交网络中一般会存在若干条公交线路，公交线路上会分布若干站点，选用十进制的整数编码方法对站点进行编号[11-13]，0 代表公交线路的起始站点，1，2，…,n代表对应的站点编号。假如获得的编码序列号为0-2-4-5-0-4-7-0-6-8，则表示总共投入了三条公交线路，且每一条公交线路的起始站点均为始发站（0），三条公交线路经过的路径分别可表示为2-4-5、4-7 和6-8，最终路线均在相同终点站结束。

2.2 适应度函数

ESGA 遗传算法的核心问题在于利用个体的适应度值对群体进行优胜劣汰，实现优化模型的目标值最大化，从而从中筛选出优质的个体，而个体的筛选主要采用适应度值作为筛选的参考标准。在遗传进化的过程中会出现一些超出约束条件的染色体，为实现对不良个体的筛选和剔除，主要采用的方法分为两种，第一种是引入惩罚因子，通过增加不符合染色体的惩罚因子，以降低其在后续遗传中的存活概率[14-15]；第二种方法是对于不满足约束条件的染色体，对其部分基因片段进行修改，使其满足约束条件。该文采用第一种方法，其适应度函数表达式为：

式中，F代表适应度函数，β代表固定的常数量，Qi代表在i站点上车的乘客数量，通过调节两个参数的数值来控制惩罚因子的惩罚力度。

利用上一代群体的适应度值，ESGA 遗传算法筛选出适应度值较高的个体，构建出优质群体，将不满足模型约束条件的个体适应度置为0，在下一代筛选时，将适应度为0 的个体替换为优质群体，从而通过这种选择淘汰适应度最低的个体。

2.3 交叉、变异和反转操作

交叉主要通过染色体片段的交换以产生新的后代，交叉操作的表达式为：

变异操作是父染色体中的基因片段发生了新的变异，在种群中出现了新的基因信息，父染色体中的某个基因段发生变异，其表达式为：

交叉操作是随机对两个父体的部分片段进行互换；变异是随机对父体的部分片段进行修改，从而提高算法对局部的搜索能力，例如原个体顺序为0-2-3-5-8，随机对站点3 和5 进行交换，交叉后的个体顺序为0-2-5-3-8。反转是将个体排列顺序进行顺序反转，属于变异的一种特殊形式，同样可提高算法对局部的搜索能力，例如个体顺序为0-2-3-5-8，反转之后变为0-8-5-3-2。

3 仿真结果

为了验证ESGA 遗传算法的有效性和快速性，模拟一个限定区域，区域中的乘客总量为100 位，乘客的位置分布如图3 所示。首先利用K-means 聚类算法将乘客划分为10 个簇，将每个簇的中心位置设定为一个公交站点，从而得到10 个公交停靠站点的位置[16]。

图3 乘客及站点位置分布

利用ESGA 遗传算法对公交路径进行解算，将种群的初始规模设定为200 个，总共进化迭代的次数设定为200 次，优质种群的占比设定为10%，交叉操作的随机概率设定为85%，发生变异操作的随机概率设定为15%，发生反转操作的随机概率也设定为15%，将该区域内的公交总车辆上限设定为5 辆，每辆公交车的最大载客量设定为35 人，假设公交公司设定的最低成本为4 元，每辆车的固定成本设定为40 元，每辆车运行1 km 的单位成本设定为10 元。通过ESGA 遗传算法的进化迭代，得到公交规划路径结果如图4 所示，最终方案中共有三条公交路线。

图4 公交规划路径

为了对比ESGA 遗传算法的快速性，在相同乘客需求和群体初始条件下，对比ESGA 遗传算法和FWSGA 遗传算法[17-18]的收敛速度，两种算法的迭代搜索结果如图5 所示，由图中曲线可以看出，ESGA遗传算法在40 代内完成了收敛，且搜索到最佳方案，而FWSGA 遗传算法接近100 代才得到收敛，且最后未能收敛到最佳方案，测试结果表明相比于FWSGA 传统遗传算法，ESGA 遗传算法具有更快的收敛速度和更优的搜索结果。

图5 两种算法迭代搜索结果对比

为了进一步对比ESGA 遗传算法和FWSGA 遗传算法之间的差异，在相同的初始条件下，ESGA 遗传算法分别选取不同的优质种群占比，优质种群的占比分别取5%、10%、15%，并与FWSGA 遗传算法一起进行测试，共进行30 次相同重复实验，不同优质种群占比下的测试统计结果如表1 所示。

表1 不同优质种群占比下的测试对比

由对比数据可知，ESGA遗传算法相比于FWSGA遗传算法，具有更高的最优值，且随着优质种群比例的增加，最优值得到明显的提升，ESGA 遗传算法的平均运行时间仅略高于FWSGA 遗传算法，当优质种群取15%时，两种算法的运行时间基本相同，ESGA遗传算法运行速度未受到较大影响。

4 结论

文中围绕乘客需求响应对公交路径进行建模，将运营收益最大作为目标，同时引入多项约束条件，建立公交路径规划模型，使得模型更能反映公交运行时面临的实际乘客需求问题，有利于公交路径利用率的提升。路径模型解算过程主要分为站点规划和路径规划两方面内容，其中路径规划中创新性地引入ESGA 遗传算法，通过实验验证了该算法的有效性和快速性。