改进遗传算法在公交调度优化中的应用

龚成清

0 引言

公交调度是影响公交系统运行效率和服务水平的主要方面，是智能公交系统研究的核心内容。国内外很多学者运用信息技术从不同的方面对公交调度优化进行了研究，有学者从公交车的总体利益出发，兼顾乘客利益的同时，利用免疫克隆算法求解公交发车频率【1】；有学者通过对固定公交车车次来保证公交公司的利益，建立以乘客等车时间最小为优化目标的公交优化调度模型，然后应用模拟退火算法对模型进行求解【2,3】；有学者从社会总体效益最优出发，利用遗传算法求解公交调度的频率【4,5】；有学者结合模拟退火算法和遗传算法的优点，给出了公交调度的求解方案【6】。 已有的研究基础对公交车的调度优化有很重要的指导意义，但大多数模型都只是考虑公交公司的运营成本最小和乘客的等待时间最小两个主要的因素，缺乏其他因素的考量。

公交车辆智能调度是一类典型的运输排班优化问题，受到很多因素的影响。本文在充分考虑到公交公司的运营成本最小和乘客的等待时间最小的情况下，引入了乘客坐车舒适度来建立数学模型，并改进传统的遗传算法对模型进行了求解。

1 公交调度优化模型的建立

公交调度问题是一个约束多目标优化问题，即在满足调度限制的解空间内，寻找出满足调度问题的目标函数的优化解。【7】公交调度主要要考虑公交公司的利益和乘客利益。对乘客而言，候车时间越短越好，坐车的人越少越好；但这也意味着公交公司在同一时间内需要调动的车辆也就越多，导致公交公司的成本增加，利润降低。公交公司利润和乘客的利益是一对矛盾体，,当一个增加（或减少）必然导致另一个减少（或增加），因此需要找到两者之间的一个最好平衡点。本文以此为目标，只考虑单向线路运行情况建立公交优化调动模型。

为了使模型简化，本文作出以下的假设：

（1） 乘客无论从哪个站上传，票价一律相同（设定为 2元/ 人次）；

（2） 在同一时段无论乘客多少，每辆公交车发车的频率相同，从始发站到终点站的运输成本相同；

（3） 公交车不准等客，每辆公交车的核载人数相同；

（4） 乘客均匀到站，且所有的乘客只能乘坐公交车到达目的地；

（5） 所有的乘客均自觉排队，按照先到先上车的原则，当车上的乘客到达满载上限时，公交车自动停止上客；

（6） 公交车不准越站，且不考虑公交车进站所花费的时间和乘客上下车所花费的时间；

（7） 不考虑公交公司的线路配车，有足够多的公交车供调度；

（8） 站点均匀分布。

设某条线路的总长度是L，调度周期为Tk(k=1,2,3…K，设全天有K个调度时段)，在调度周期内乘客的到达率是P，线路上的公交车站为M，共有N辆公交车在运行，运行速度为V，每辆公交车运行一趟的成本为C，则周期Tk内，公交车的总运营成本为：

公交车发车时间间隔为：

（Smin为最小发车时间间隔，Smax为最大发车时间间隔）

某乘客在第i站（1≤i≤M）等待第j辆公交车（1≤j≤N）的时间为：

设Ri,j是第i站第j辆公交车乘客到达的数量，则线路上乘客的总候车时间为：

把乘客的候车时间转换为候车成本，设乘客的单位候车时间成本为a元，则乘客的总候车成本是：

则公交车调度调度模型满足：

然而，乘客的利益除了受候车时间的影响外，乘客乘车的舒适度也是一个重要的指标。如果车上的人太拥挤，乘客的满意度就会降低，相当于损害了乘客的利益，因此，把乘客的舒适度考虑进来对模型进行改进。设每辆公交车的核定载客量为O，Ei,j是第i站第j辆公交车下车的乘客数量，xij为在第i站第j辆公交车乘客的坐车拥挤度，则：

设车辆的最大满载率大于等于核定载客量的50%，且小于等于核定载客量的120%（即0.5≤xij≤1.2），根据统计，当车上乘客的人数小于或等于车辆核载率时，乘客的舒适度y=1;否则y= xij;如式（8）：

加上乘客舒适度后，乘客候车的成本为：

则公交调度的优化模型转换为求以下问题的最小解：

2 改进遗传算法求解公交车调度

遗传算法（Genetic Algorithm）是模拟生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法具有较高的全局快速搜索能力，己被广泛应用于解决多变量的非线性问题。但基本遗传算法采用的是最简单的遗传算子进行运算，在实际应用中仍暴露出进化缓慢和提前收敛等问题。本文结合实际问题对基本遗传算法进行了改进来提高算法的运算效率和计算的准确性。

2.1 染色体编码

根据公交调度模型特点，把发车时间间隔看成是遗传算法中的染色体的基因，并采用二进制编码方法对其编码。设置发车时间间隔的单位是分钟，本文设置最长的发车间隔不得大于15分钟，因此采用4位的二进制对其编码，则其编码表，如表1所示：

表1 染色体编码

由于全天共有K个调度时段，所以每个染色体的长度是4K。本文设K=4，则每个染色体的长度是16。

2.2 约束条件的处理

为了使算法具有自适应的能力，因此，必须对模型的约束条件进行处理。罚函数是遗传算法中有效处理约束条件的方法。按照式子（10）中的约束条件，设1λ，2λ，3λ，4λ是各个约束条件的罚函数作用强度的系数，则加上约束条件的新目标函数为：

2.3 定义适应函数和适应值

通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础．

对于公交调度中的最小化问题，定义适应函数Fk，采用下述方法：

2.4 初始群体

用启发式方法产生初始群体中各个个体的基因值。依次按照如下规则选择n个染色体作为初始群体：

（1）按整个调度周期内的最高断面通过量确定一个染色体;

（2）随机确定。

2.5 进行遗传操作产生后代

2.5.1 选择

这里我们用到了适应值的比例来作为选择的标准，得到的每个个体的适应值比例叫作入选概率．其计算公式如下：对于给定的规模为n的群体pop={F1, F2, F3,…, Fn}，个体Fi的适应值为g(Fi)，则其入选概率为

利用式子（13）我们可以计算出各个个体的入选概率。计算完了入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体，并用入选概率最大的个体补入种群，得到与原群体大小同样的种群。

2.5.2 交叉

交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体。单点交叉(One-pointCrossover)是常用的方式，即在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。具体步骤为:①以随机配对的配对策略对染色体进行配对。把群体中的n个个体以随机的方式配成n/2对。为了避免两个相同的染色体交叉（重复繁殖）或两个相近的染色体进行交叉（近亲繁殖），在给一个染色体配对时，先把还未被配对的染色体逐一判断与该染色体之间的差异性，再选择差异性最大的染色体与之配对。②以Pc的概率选择配对好的染色体进行交叉操作。对要进行交叉操作的染色体对随机选择交叉点的位置，互换交叉点之后的基因。两个个体的在9号基因的位置交叉过程，如表2所示：

表2 两个个体交叉的过程

2.5.3 变异

在基本遗传算法中，变异算子通常采用对群体中的个体码串随机挑选一个或多个基因值做变异，变异操作是随机的，这样会阻碍搜索效率的提高，有时甚至会出现大量无为的冗余迭代。本文利用蚁群算法具有局部搜索能力强和收敛速度比较快等优点，【8，9】通过蚁群算法来引导变异，加快遗传算法的收敛速度，提高算法的效率。蚁群算法在遗传变异中的应用具体如下：

经过选择和交叉操作，首先在当前群体n中找出最优染色体X0，并将其视为较优解，然后从X0出发，利用蚁群算法，用m（m＞16）只蚂蚁来寻找更优秀的染色体。每只蚂蚁根据信息素的浓度，以的概论选择X0的一个基因：

2.6 终止条件

传统的遗传算法终止条件是通过固定遗传代数，到达后即中止。固定遗传代数若设置不当，会出现遗传代数过多，增加迭代的次数，遗传代数过少，可能得到的是局部最优解的情况。本文以判断种群是否己经成熟并不再有进化趋势作为终止条件，即判断迭代的过程中，若出现连续10代的染色体均小于或等于固定阀值ε时，则终止算法的运行。

3 实例应用

本文选取我国一座特大城市某条公交线路为例子，该条公交线路里程共14公里，设14站，公交公司配给该线路同一型号的大客车，每辆标准载客 100人，据统计客车在该线路上运行的平均速度为20公里／小时。下面给出的是典型的一个工作日早上 5点到9点从A13到 A0上下车的乘客数量统计，如表3所示：

表3 某条公交线路的客流调查和运营资料

A7 A8下 81 800 1793 971上 48 315 523 271下 45 542 1097 621上 90 594 868 549 A9 A10 A11下 48 588 1058 634上 76 589 948 477下 20 239 461 300上 43 256 447 235下 13 164 272 169上 52 333 528 305下 9 105 227 123 A12上 60 376 634 322下 8 99 205 106 A13上 371 1990 3626 2064下 0 0 0 0

根据统计的数据和结合表3中的数据，设置算法的主要参数，如表4所示：

表4 算法的主要参数

在 matlab中，对模型分别用基本遗传算法和本文改进的遗传算法进行求解，得到的数据，如表5所示：

表5 不同算法求解模型对比

7：00—8：00 8：00—9：00基本遗传算法 1 380本文算法 1 265基本遗传算法 3 320本文算法 2 246

由算法的结果可以看出，随着客流数据量的增大，两种算法的迭代次数都增加。基本遗传算法在5：00—6：00发车时段出现了提前收敛的现象，求解结果只是局部最优，有较大的误差。而引入了蚁群引导变异的遗传算法不仅可以加快算法收敛的速度，比基本的遗传算法求解模型不仅要更快，更高效，而且具有更高的精确度。实验结果也证明了这一点。

结语

公交车调度问题的研究是十分复杂的。[10]把调度问题抽象成为一个数学模型，通过加入了乘车的舒适度这一因素的考量，以求模型能更全面地反映乘客坐车的感受。利用蚁群算法的正反馈原理，在传统的遗传算法中融入蚁群算法，建立了自适应的遗传算法来有利于模型的求解。模型还没有考虑乘客上下车的延时和站点的不均匀分布的情况，这是今后要改进的方向。

[1]王敏.免疫克隆算法求解公交发车频率问题[J].计算应用研究,2010,27(12):4483-4485

[2]郑小花,陈淑燕,武林芝. 模拟退火算法在公交调度中的应用[J].信息化研究,2009,35(9):45-47

[3]白子建，宋瑞，贺国光．快速公交线路组合频率优化的禁忌模拟退火算法仿真[J].计算机应用研究,2008,25(2):355—358

[4]韩印.基于遗传算法的智能公交发车频率优化研究[J].计算机工程与应用，2008，44(33)：243—245

[5]CEVALLOS F, ZHAO Fang. A genetic algorithm for bus schedule synchronization[C]//Proc ofAATT 2006.2006:737-742

[6]任传祥．混合遗传一模拟退火算法在公交智能调度中的应用[J].系统仿真学报，2005，17(9)：2075-2081

[7]王琳,王蕾云,王洁琳,潘 峰.城市公交调度优化模型及算法研究[J].城市公共交通，2010.10：37-39

[8]肖宏峰,谭冠政. 基于遗传算法的混合蚁群算法[J]. 计算机工程与应用,2008,44(16):42-45

[9]方旺盛,肖琴. 蚁群算法的收敛性分析及其在TSP上的求解[J]. 计算机与数字工程,2007,35(9):46-48

[10]贺学海， 刘永建. 公交车调度问题的数学模型[J].河南科学,2009,27(6):653-659