基于遗传算法的BRT站距双层优化模型研究

商泽

摘 要：为了准确求解最优BRT站距，综合考虑了BRT站点服务范围和公交企业的利益，建立了双层优化模型。上层微观模型以公交车辆和BRT站点营运成本最小为目标，下层宏观模型作为辅助，以BRT站点服务范围最大为目标。针对该模型设计遗传算法进行求解，并给出算法的具体实现步骤，最后结合算法案例验证了模型和算法的有效性。

关键词：BRT站距；遗传算法；双层规划

中图分类号：U491.17 文献标识码：A 文章编号：1671-2064（2018）16-0050-02

BRT站点间距优化最早于1968年由Vuchic和Newell[1]提出，以乘客出行时间最短为目标函数对轻轨和地铁线路的站距进行优化。其后，S C Wirasinghe和N S Ghoneim[5]逐步完善了基于需求连续分布的站点间距优化理论。近年来，国内相继提出了基于全局最优化理论的BRT站点布设模型[2]、基于乘客平均出行时间最小的公交站距优化模型[3]和基于社会福利最大的公交站距优化模型[4]等理论。本文在此基础之上，提出了基于遗传算法的BRT站距双层优化模型，综合考虑了BRT站点服务范围和公交企业的利益两方面的因素，建立上层以BRT车辆和站点营运成本最小为目标，下层以BRT站点服务范围最大为目标的双层模型，能够更全面的对BRT站距进行优化。

1 双层公交站距优化模型

1.1 基本假设

本文所研究的是BRT最优站距问题，所以可以做以下假设：

（1）BRT线路至少采用半封闭路权模式，节点采用公交信号优先，即公交车辆通过交叉口时的延误忽略不计；（2）为了研究方便，将公交车运动划分成为匀速运动、匀减速运动以及匀加速运动；（3）为了研究方便，公交车以固定时间间隔发车；（4）为了建立上层微观模型的需要，忽略公交车辆调头延误，即将BRT线路近似看做闭合回路的形式，公交车辆由起点到终点循环营运，假设采取中央式布站，BRT线路设有N个站，每个站点均需停车两次，公交车辆每次由起点到起点一个循环共需停车2N次；（5）为了建立下层宏观模型，假设BRT线路可以由部分近似直线段组成，并且直线段数目尽量少，即忽略BRT线路转弯造成的覆盖率损失。在BRT线路中共有N个站，以站点为圆心形成圆形服务范围。

1.2 上层微观模型

1.2.1 车辆营运时间计算模型

车辆由起点到起点一个循环运行时间可表示成：

T车=T1+T2+T3 （1）

T1=2L/V （2）

（3）

（4）

N=L/D+1 （5）

式中：T车为车辆由起点到起点一个循环运行时间（s）；T1为车辆以稳定车速V运行时间（s）；T2为车辆因进出站而减速或加速所损失总时间（s）；T3为车辆在各站点的停车总时间（s）。L为起点到终点长度（m）；V为车辆的运行速度（m/s）；D为站距（m）；N为站点数；、分别为第i站台进、出站时减速或加速时间（s）；为在第i个站臺的停车时间（s）。

1.2.2 车辆营运成本计算模型

车辆营运成本c车等于车辆每次由起点到起点一个循环所对应的运行成本之和，一个车辆由起点到起点一个循环运行成本等于该车辆以正常行驶时的时间乘以其时间成本和车辆在站点停站时的时间乘以成本之和。在上边车辆由起点到起点一个循环运行时间的推导基础上，可以求出车辆营运成本c车为：

（6）

式中：m为发车次数；T1j、T2j、T3j分别为汽车在第m次发车中正常行驶、加速或减速行驶和停车的时间；c1、c2、c3分别为汽车在正常行驶、加速或减速行驶、停车时的单位时间成本（单位：元/s），其值的的大小有汽车单位时间的油耗值和汽车损耗程度等因素确定。

将（2）、（3）、（4）式代入（6）式得车辆营运成本：

（7）

式中：、分别为第m次发车过程中在第i站台进、出站时减速或加速时间（s）；T3ij为第m次发车过程中在第i个站台的停车时间（s）；其他符号与上面提到的一致。

1.2.3 站台营运成本计算模型

BRT的站台的营运情况不同于普通公交站台，其营运成本不可忽略。站台营运成本c站等于所有站点单位时间的营运成本与营运时间之积。假设每个站点的单位时间营运成本相同，则站台营运成本可表示为：

c站=60t（m-1）nQ （8）

式中：t为固定的发车时间间隔（min），Q为每个站点的单位时间营运成本（元/s）。

1.2.4 上层微观模型的建立

假设车辆营运成本c车和站台营运成本c站的加权系数分别为a和b，且a+b=1。加权系数的取值由实际营运下的权重情况综合决定。则上层模型的目标函数可表示为：

Z1=c车+（1-）c站 （9）

1.3 下层宏观模型

1.3.1 BRT站点服务范围c范

BRT站点服务范围等于本条BRT路线的总服务面积乘以服务面积折算系数。假设每个BRT站点的服务面积为以半径为R的圆，以BRT线路的起点为坐标原点建立直角坐标系，忽略BRT线路转弯造成的覆盖率损失，可以按一条直线路线计算服务范围，则BRT路线的服务面积示意图如图1所示。

基于以上假设，BRT路线的总服务面积为各个站点的服务面积减去重叠服务区的面积。则BRT路线的总服务面积可表示为：

（其中：R

式中：S为BRT路线的总服务面积；R为每个BRT站点的服务区半径；D为公交站距。

假设服务面积折算系数为c，则BRT站点服务范围c范可表示为：c范=cS （11）

1.3.2 下层宏观模型的建立

下层宏观模型是以BRT站点服务范围最大为目标函数的宏观模型。其目标函数可表示为：

Z2=c范（R

2 遗传算法设计

2.1 编码

本算法采用二进制编码，每一个十位的二进制染色体对应着一个十进制的站距值（单位：m），由二进制编码的站距值足以包括城市公共交通最优站距的取值范围。

2.2 初始种群的產生

初始种群是通过随机函数randperm产生n个十位的二进制染色体构成。

2.3 适应度

适应度是对该问题的一个解的评价值和目标值，按一定的数学变换规则生成适应度函数F（k），采用如下表达式：

（13）

式中d值取1z1（i）、z2（i）表示第k个染色体上、下层规划的目标函数值。K∈M，M表示种群数量。

2.4 选择

本文采用轮盘赌选择法对每个染色体进行选择。

2.5 交叉和变异

交叉：对于随机从种群中选出的某对染色体，按交叉概率随机地在其上选择一个断点，交换双亲上断点的左端，生成新的后代。

变异：按变异概率选取染色体的某个位置实行变异，该位置若是0的则变成l，若是1的则变成0。

3 算法步骤

Step0：参数初始化。

Stepl：设定种群数目M、染色体长度l、迭代总数、交叉概率、变异概率。

Step2：采用0-1编码，随即产生初始种群。

Step3：将各染色体转化成站距值并计算各染色体对应的上、下层目标函数值z1、z2。

Step4：计算种群的各染色体适应度函数值。

Step5：通过旋转赌轮每一个染色体。

Step6：将各染色体转化二进制的形式，按照概率进行交叉、变异操作，转向Step3。

Step7：结束，从进化的代染色体群中选取适应度最好的染色体，该染色体就是问题的较优解。

4 算法案例及分析

4.1 案例的提出

本文以济南市BRT1线路为算法案例，对其站距进行优化。BRT1西起黄岗，东至全福立交桥，全长11.5km，采用专用车道全封闭运行，沿途共设有17个实际营运站点，2个备用站点。实地调查BRT1线路工作日和周末的每次发车中在每个站点的实际延误时间做为初始数据，并结合实际情况确定时间成本、营运成本、加权系数和服务区半径等参数的取值。

4.2 利用Matlab遗传算法工具箱求解算例

使用英国设菲尔德（Sheffield）大学推出的Matlab遗传算法工具箱作为辅助工具通过编程对算例进行求解[7]。遗传