基于混合遗传算法的轨道交通接驳公交线路的设计

刘 霞，李 楠

（江汉大学 物理与信息工程学院，湖北 武汉 430056）

0 引言

轨道交通的出现不仅顺应了城市高速发展的需要，也逐渐成为了人们出行必不可少的乘车方式之一。我国近年来轨道交通建设大步向前，轨道线路的数量和长度都在稳步上升，但由于建设的经济成本高、耗时长、技术难度高和城市地形的复杂度不同，轨道交通的服务范围主要是围绕着城市中心地带和一些人流大的地区，没能很好地顾及到城市各个地区交通出行需求［1］。相比之下，传统的常规公交城市覆盖率非常高，其建设成本较低，可实施性也较高，公交系统基本上可以涵盖城市不同区域的交通出行，但相较于轨道交通，常规公交的运行效率低，乘客乘车体验感也较差［2］。结合两者的不同性质，将轨道交通和常规公交相互协调起来工作，可以很好地发挥它们各自的优势，提高城市交通的效益［3］。

在轨道交通与常规公交衔接研究方面，国内外已经有了大量理论基础，研究的切入点较多集中在以不同的优化算法去减少乘客换乘时间、乘车时间和公交运营成本等［4］。CHOWDHURY等［5］以总费用最小为目标函数构建模型，以接驳公交线路的开行频率一致为前提，对常规公交开行频率进行确定。任芳［6］通过分析和总结现有城市轨道交通和常规公交的相关理论，对公交接驳站点的设置以及线路优化的方法作了具体研究。方晓丽［7］在先定性调整既有的公交线路去保证线路布局的合理性和新增接驳公交线路去优化乘客的成本方面进行了研究。在这些问题的研究中，大多数都是在轨道交通线路不变的情况下，对已有的公交线路进行部分的整改优化，从而达到预期的效果。本文研究的问题是在没有初始公交线路的基础上，以一个轨道交通站点为中心点，在其服务半径内，结合周边乘客出行需求，对接驳轨道交通的公交线路进行设计，使乘客出行成本和公交公司运营成本的总和最低。

1 建立问题求解模型

1.1 问题描述

接驳公交线路是以一定的顺序和方向将各个公交站点以及轨道交通站点进行彼此之间的联通，由轨道交通接驳站点和公交站点组成的一个城市交通网络［8］。本文以魏超［9］提出的接驳公交线路问题为基础，以单个的轨道交通站点为圆心，以一定的接驳线路长度为半径，将区域范围内的接驳公交站点进行连接，从而达到该区域的乘客出行成本和公交运营成本的总和最小的目的。在该问题中规定每个公交站点只出现于一条接驳公交线路上，每条接驳公交线路只连接一个轨道交通站点，公交车在每个站点都停靠。

1.2 变量定义

在该线路设计的模型中，公交站点的个数为n，站点集合V={1，2，…，n}。轨道交通站点的个数为1，设为站点0，两者组成的网络节点集合记为N=0⋃V，任意两个站点i和j之间的距离为dij，接驳公交线路的条数为k，接驳线路集合为K={1，2，…，k}。公交车行驶的平均速度为v，线路k的开行频率为fk，表示一小时发车的次数。qi表示一小时内i站点的出行量，表示k线路上公交从i站点出发驶向j站点时输送的乘客数量。采用0-1变量来表示站点与站点关系，如公式（1）所示；站点与线路的关系，如公式（2）和公式（3）所示。

1.3 约束条件

1.3.1 接驳线路的完整性 每条接驳线路仅有一个起始公交站点，即满足

设站点i是公交线路k的起点，则站点i只存在后续站点，没有前续站点，即满足

每条接驳线路均以轨道交通站点为终点，即满足

除终点外，若站点i在线路k上，则站点i必有一个后续站点j，即满足

1.3.2 站点与线路之间的关系 每个公交站点只存在于一条公交线路上，即满足

为保证公交线路运行距离的均衡性，对每条线路经过的站点数量做出约束，即满足

其中α表示每条线路上站点数量的波动幅度，Nk表示公交线路k经过的站点总数。

任意一条线路必须是无环的简单链，即满足

1.3.3 车上乘客数量和公交运能守恒 线路k上公交驶离站点i后输送的乘客数量等于到达站点i之前输送的乘客数量与站点i出行需求之和，即满足

任意公交线路的运能应该大于该线路总的客流需求，即满足

其中pmax为公交车最大载客量。

1.4 系统费用

接驳公交线路设计考虑的两个主体为乘客和公交运营商，在保证方案可实施的前提下，需要整体考虑两者的利益。因而系统总费用由乘客出行成本和公交运营成本两部分组成［10］。

1.4.1 乘客出行成本 乘客的候车时间成本：乘客候车时间主要取决于公交车的开行频率，开行频率越高则乘客候车时间越少，反之越多。乘客候车成本可表示为

其中Cw表示单位时间候车成本。

乘车时间成本：乘客的乘车时间主要取决于公交线路的设计和公交运行速度。乘客的总的乘车时间成本可以表示为

其中Ct表示单位时间乘车成本。

1.4.2 公交运营成本 公交车辆运营成本包括燃油费、人工费和折旧费等，与接驳线路的长度正相关。此外，公交开行频率越高，公交运营成本也就越高。公交运营成本可以表示为

其中C0表示公交车辆单位时间运营成本。

通过上述分析，以乘客出行总成本和公交车辆运营成本之和最小为目标，建立双向接驳线路优化模型的目标函数为

当公交线路给定并且忽略公交运能约束，则上述优化模型将变成无约束优化问题。利用函数最优性条件，通过对目标函数求导可以得到无运能约束下最优公交开行频率为

因在本文中需要满足运能约束，则最优公交开行频率的计算如公式（18）所示：

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

2.1 算法的基本步骤

本文研究的是一个典型的优化组合问题，遗传算法作为一种启发式智能搜索算法在解决此类问题时效果较好［11］，本文在算法基本框架上做出局部优化处理，形成一种混合遗传算法，使算法收敛性更佳［12］。基本步骤如下［13］：

第一步确定接驳公交线路的总条数。

第二步种群初始化。随机生成含有若干个初始个体的种群，并设置最大的繁衍代数。

第三步选择算子。采用锦标赛选择策略将初始种群中适应度值较优的个体进行保留，形成新的种群。

第四步交叉算子和变异算子。设置进行交叉操作和变异操作的概率，采用顺序交叉方式和单点变异方式，形成新的种群。

第五步局部优化。采用opt-2和单点插入局部处理方式对种群进行优化，使种群跳出非最优解的局部收敛。

第六步判断繁衍是否结束。检测繁衍的代数是否到达上限，若到达，则输出当前最优的值；否则返回第三步。

2.2 解的编码和初始种群的生成

用数字1，2，…，n分别代表对应的站点编号，数字0代表轨道交通站点，每条接驳公交线路以轨道交通站点0为结束标志。图1所示为3线路，分别为1-2-0、7-3-0、6-4-5-0，线路1-2-0是以站点1为起点，接着经过站点2，最后到达轨道交通站点0。

图1 解的编码表示Fig.1 Coding representation of solution

初始种群的生成过程为：首先将所有公交站点进行随机排列，然后根据预设的线路条数k在公交站点数列中随机插入k个0，形成一个完整初始解。重复该过程生成含有N个初始解的初始种群。

2.3 选择策略

在遗传算法中，可以采用轮盘赌、随机遍历抽样、最优保存、排序选择和锦标赛选择等选择策略。为使系统总费用最小。本文采用锦标赛选择策略，具体的操作步骤如下：

1）首先确定每次从种群中选择进行优劣性比较的个体数量n。

2）从种群中随机选择个体数量为n的小种群，在小种群中选择最优的个体进入新种群。

3）重复步骤2），直到构成一个与初始种群个体规模相同的新种群。

2.4 交叉策略和变异策略

2.4.1 交叉策略 交叉算子的设计和实现与所研究的问题密切相关，既不能过多地破坏个体编码串中表示优良性状的模式，又需要有效地产生一些较好的新个体模式。考虑到本文的模型主要是站点之间的匹配顺序问题，这里采用顺序交叉方式。过程如下：

第一步随机选择一个染色体中两个基因作为待交叉片段的起始位置（两个父代染色体被选的位置相同），如图2所示。

图2 选择交叉片段Fig.2 Selection of cross section

第二步生成一个子代，并保证子代中被选中基因的位置与父代相同（其中父代中的轨道站点不参与交叉，即后代中0的位置不变），如图3所示。

图3 子一代产生过程（1）Fig.3 Generation process of the first offspring（1）

第三步在另一个父代中剔除第一步选中的基因，将剩余基因按顺序依次放入上一步生成的子代中，如图4所示。

图4 子一代产生过程（2）Fig.4 Generation process of the first offspring（2）

在本例中另一个子代如图5所示。

图5 子二代Fig.5 The second offspring

2.4.2 变异策略 遗传算法中的变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。本文采用单点变异，首先随机选择一个变异点，然后随机生成一个变异基因（这个基因来自本身存在的编号），最后交换产生的变异基因与该基因的位置，如图6所示。

图6 单点变异Fig.6 Single point variation

2.5 局部优化

在单纯采用传统遗传算法的时候，形成最优解的过程收敛速度慢、不稳定性也较大，并且容易陷入到局部最优解［14］。检测发现，由于该问题解结构的特殊性，加上交叉方式的特殊性等一些潜在影响因素，在每次交叉和变异结束后对较优的后代进行局部优化。本文采用2-opt法和随机插入法进行局部优化。

2.5.1 2-opt法 2-opt是一种随机性局部优化的方法，是解决优化组合问题的有效工具，这里以问题的子线路来说明（设最大循环次数为n，单次循环次数为c）：

第一步随机选择1条子线路（如1-2-3-4-5-6-0），计算出该条子线路的总费用为mincost。

第二步随机选择该条子线路中的两个站点，依次对调两个站点形成新的子线路，如选择站点3和站点6，则新的子线路为1-2-6-5-4-3-0。

第三步若新的子线路总费用比mincost要小，更新最优子线路为当前子线路，并更新mincost的值，将c的值改为0，回到第二步，否则将c的值加1，回到第二步，当c的值大于n时，结束算法。

2.5.2 随机插入法 随机插入法是针对该问题所衍生出来的一种局部处理当前解方法。具体步骤如下：

第一步随机选择一条子线路和该线路上的一个站点。如图7所示，选择子线路8-9-10-0中的站点9。

图7 站点选择Fig.7 Site selection

第二步将该站点随机插入到另一条子线路中，并在原始的子线路中删除该站点。如图8所示，将站点9插入到子线路1-2-3-0的站点2和站点3之间。

3 算例

魏超［9］提出的接驳公交线路问题的算例中使用了遗传算法进行求解，本文采用混合遗传算法来求解相同算例，并在算法的收敛速度上对遗传算法和混合遗传算法进行比较。

3.1 基于混合遗传算法的算例求解

假设有一个轨道交通站点，在这个站点的接驳半径内有25个公交站点。并且设置求解模型的其他参数为α=2，v=20 km/h，pmax=80人/车，C0=100元/（车·小时），Ct=10元/（人·小时），Cw=20元/（人·小时）。各公交站点的乘客出行需求和坐标分别如表1和表2所示。这里设初始种群规模为50，交叉概率为0.9，变异概率为0.1。2-opt法和随机插入法的内部循环的次数为10，种群遗传的代数为100。

本文采用Python语言在PyCharm编译环境下编写的仿真程序来生成最优公交接驳线路。在程序模拟求解过程中，首先设定接驳线路条数为4，接着实现混合遗传算法的仿真运算，在遗传至70代左右时可得到最优解。并且每次模拟结果稳定，程序运行时间较快。如图9所示，给出了3次混合遗传算法求解过程中系统总费用随遗传代数增加的趋势图。

表1 站点乘客出行人数需求Tab.1 Site passenger travelling demand

表2 站点坐标Tab.2 Site coordinates

图9 系统费用走势图（1）Fig.9 System cost chart（1）

得出最优的4条接驳线路分别为：1-5-10-14-18-22-0、2-6-9-13-17-21-0、3-8-12-16-20-23-25-0、4-7-11-15-19-24-0，系统的总费用为10 834.26元。形成4条最优接驳线路如图10所示。

3.2 与遗传算法求解的对比

保持两个算法的选择策略、交叉算子、变异算子均相同，去掉混合遗传算法中局部优化处理的操作，其他参数不变，单纯采用遗传算法求解。结果如图11所示，给出了3次遗传算法求解过程中系统总费用随遗传代数增加的趋势图。

图10 最优线路图Fig.10 Diagram of optimal routes

图11 系统费用走势图（2）Fig.11 System cost chart（2）

比较图9和图11可看出，当遗传代数到达100时，遗传算法还未收敛到最优值，并且从图11中也可以看出随着遗传代数的增加，收敛的速度也在变慢，而混合遗传算法在100代之前已经收敛于最优值。所以，采用混合遗传算法可在一定程度上提升收敛的速度。

4 结语

本文研究的对象是城市轨道交通与常规公交接驳的线路优化问题。首先提出如何将轨道交通站点和常规公交站点有效衔接的问题，接着建立问题的求解数学模型，并描述了采用混合遗传算法求解该问题的具体步骤，最后用该算法求解了一个具体算例，并在收敛速度上与遗传算法进行对比，可看出混合遗传算法收敛效果更好。此外，由于算例中所需的数据是参考实际情况而设定的，也表明了混合遗传算法在解决该问题上的可行性。由于本文约束条件的理想化，对于一些实际问题的考虑不足，还有很大的改善余地。并且，算例中的轨道交通站点数量和公交站点的数量不多，对于多个轨道站点接驳多个公交站点的研究也有待进一步探讨。