一种改进公交调度算法的研究

陈 艳，刁志刚

（淮安信息职业技术学院 江苏 淮安 223002）

随着世界城市化进程的快速发展，城市人口逐渐增加、人们的社会生活和经济生活日益丰富，由此对交通的要求也越来越高，智能交通正在不断改善人们的交通状况。公共智能交通调度是近年来世界上受人瞩目且发展迅猛的应用研究开发领域，所谓智能交通系统（Intelligent Transportation System，ITS），就是通过采用先进的电子技术、信息技术、通信技术等高新技术，对传统的交通运输系统及管理体制进行改造，从而形成一种信息化、智能化、社会化的新型现代交通系统。ITS强调的是运输设备的系统性、信息交流的交互性以及服务的广泛性。智能交通系统的7大领域包括:出行和交通管理系统、出行需求管理系统、公共交通运营系统、商用车辆运营系统、电子收费系统、应急管理系统、先进的车辆控制和安全系统。由于ITS是将出行者、道路和交通运输工具三者作为一个整体系统来综合考虑，因此使交通运输基础设施得以发挥最大效能，车辆堵塞和交通拥挤得到有效解决，出行者的安全度和舒适度得到明显改善，并通过节约能源和保护环境使全社会获得巨大的社会经济效益。

文中提出了基于改进遗传算法的思想构造了公共交通线网发车间隔优化数学模型，将遗传算法引入到模型求解中，重点对改进遗传算法应用于城市公交运营优化问题的算法步骤进行阐述。

1 遗传算法基本原理

遗传算法主要操作步骤如下:

1）选择编码策略，把参数集合X和域转换为位串结构空间S；

2）定义适应度函数 f（X）；

3）确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。

4）生成初始种群P；

5）计算群体中各个体的适应度值；

6）按照遗传策略，将遗传算子作用于种群，产生下一代种群；

迭代终止判定。

遗传算法涉及6大要素:参数编码，初始群体的设定，适应度函数的设计，遗传操作的设计，控制参数的设定，迭代终止条件。

遗传操作产生后代:遗传算法在运行早期个体差异较大，当采用传统的转轮法时，即认为后代产生的概率和适值大小成正比。这样会使遗传算法早期个别好的个体的后代充斥整个种群，造成早熟现象。而在遗传算法后期，适值趋于一致，优秀个体在后代中优势不明显，从而使整个种群进化速度趋于停滞。

计算某一代群体中某个染色体被复制产生下一代的概率:

式中:Ri-第i个染色体的选择概率；fi-第i个染色体的适值；N-种群中染色体个数；S-温度；S0-初始温度；l-遗传代数。

计算各染色体的累计概率λk:

式（3）在[0，l]区间内产生一个均匀分布的随机数ξ。如果ξ≤A，则选择第一个染色体进行复制；如果λk＜ξ≤A，则选择第ξ个染色体。如此循环N次，就会产生种群规模同样为N的下一代种群。

2 改进优化遗传算法描述

在GA的应用研究中，应从两个方面加以深入:1）如何充分利用GA的特长和优势，在求解问题时发挥这些优势作用。这其中也包括充分利用GA现有的改进成果，如已提出的优秀遗传算子、参数设置方法、遗传结构及改进的变形GA等；2）如何加强GA的优势，如提高GA的鲁棒性、适应性等。总之，以提高GA搜索效率和鲁棒性为目的，以GA的结构、基因操作和参数设置都向自适应、自组织形式发展，并进行系统综合为主要实现方式的GA综合改进算法的研究是GA应用研究的主要方向。本章基于这一思想，提出一种综合改进遗传算法，它的主要特点在于它充分利用已有各种改进算法的优点，将它们和各种优秀遗传算子综合在一个GA结构中，取长补短，协同作用，使GA的性能得到大幅度提高。

文中的综合改进遗传算法采用了并行结构，共有3个子种群I，II，III。每个种群采用不同的遗传策略，分别以各自的方式并行执行进化。种群II，III的进化采用SGA结构，分别利用实际应用效果较好的自适应遗传算法（AGA）和模拟退火遗传算法（SAGA）执行微进化。为了加快进化速度，除了种群Ⅱ，Ⅲ各自单独的微进化外，加入了第二层种群间的宏进化。它将微进化过程产生的较好个体保留，组成新的个体集-种群I进行强进化。该个体集以较小的交叉率（足）、变异率（只）进行本地进化的遗传操作，主要用于局部搜索，以尽快发现最优解。

3 算法的实现

为了提高GA的搜索性能，人们提出了许多改进GA。在以后的研究中，GA的结构、基因操作和参数设置都会向自适应、自组织形式发展并将进行系统的综合。因此，应将各种不同的改进的GA综合到一个结构中，取长补短，协同作用，得到功能更强大、性能更优越的综合改进GA。

在文中的改进GA中，包含了采用不同方法得到两种各具特色的改进的GA。虽然两种GA的实现方式不同，但它们的基本思想是一致的，即通过GA进化过程中遗传算子和参数的自适应改变，使GA在求解不同问题或同一问题的不同阶段自动调整各种遗传因素的作用强度，以更好的适应复杂、变化的环境。首先初始化随机产生两个子种群II，Ⅲ。而种群I通过选取II，Ⅲ中的较好个体而产生。

3.1 种群II的进化

种群II采用自适应遗传算法，在整个进化过程中，Pc和Pm及适应度函数调整方案都随着遗传进程作自适应改变。

1）适应度函数的调整

为了保证整个进化过程中适当的选择压力，在选择操作之前，借鉴模拟退火思想对个体适应度进行调整，调整公式如下:

式中fi——调整前第i个个体的适应度；

Fi——调整后第i个个体的适应度；

M一种群规模；

n一遗传代数；

T—退火温度；

To——初始温度，可根据具体情况选择。

这样在温度高对（算法的前期），适应度很高的个体优势不会特别突出以至产生超级

个体，适应度相近的个体产生后代的概率相近。而温度不断下降后，拉伸作用加强，使

适应度相近的个体适应度差异放大，从而使优秀的个体优势更加明显，增加了进化后期的选择压力，避免了进化迟滞现象。

2）自适应公式的确定

文中采用两点交叉加高段位突变功能的交叉操作，变异操作采用简单的位点变异，

同时为防止超级个体的产生，加入了强制变异算子，并使用Sriavivas提出的自适应交叉、变异率。当算法提前收敛时，加大£和己，而在算法初期减小只和己。同时为保持优良个体，对于高适应度个体采用较低的只和己；对低适应度的个体采用较高的£和己，以利于较好个体的产生。自适应公式如下:

式中fmax-群体的最大适应度；f¯-该群体的平均适应度；f′-交叉的两个个体中较大的适应度值；f-参加变异的个体的适应度值。

3.2 种群Ⅲ的进化

种群Ⅲ采用模拟退火遗传算法。模拟退火算法和遗传算法两种算法都是全局随机优化算法，它们在传统的基于梯度的优化方法难以解决的复杂优化问题中显示了优良的求解特性，得到广泛研究和应用。虽然遗传算法有较强的全局搜索性能，但它的爬山能力弱，在实际应用中容易产生早熟收敛的问题，且在进化后期搜索效率较低。而模拟退火算法却具有摆脱局部最优点的能力，能抑制遗传算法的早熟现象。因此，考虑将模拟退火的思想引入遗传算法，有效地缓解了遗传算法的选择压力。为了保持GA的基本特点不变，保留GA的优点，交叉算子未作任何改动，仍然使用自适应交叉率。只是在变异算子中引入模拟退火机制。对任一参与变异的个体，随机产生一个新个体串，若新个体的适应度高于变异个体，则接受新个体串（即以新个体代替变异个体）；否则，以下面的概率接受新个体

其中 g=1，2，3，…；

f-变异个体的适应度；

f′-随机产生个体的适应度；

g-随着进化代数而增加；

T0-初始退火温度。

3.3 种群I的进化

种群I为保留种群，由种群Ⅱ，Ⅲ中最好的个体构成，各子种群每经过一定的间隔（实验中取进化8次）选择各种群中的最好个体构成种群I。这样，种群I的个体质量将始终保持较高的水平。种群I的作用主要是将3个种群产生的较优个体集中在一起进行“强制进化”，在它们所形成的较优区域内进行小范围精细搜索，以尽快找到最优解。此时，最优解的区域已基本确定，对算法探索新搜索空间的要求大大下降，应加强算法的局部搜索能力，以算法的利用性为主，提高解的品质。为了防止交叉、变异算子对较优个体的破坏，种群I采用较低的交叉、变异率，以取得类似爬山算子的效果。这里取Pc=0.4，Pm=0.002。由于采用多种群同时进化策略，各子种群以不同的方式并行执行进化以获得适应不同环境的进化种群；该综合改进遗传算法可从不同方向进行搜索，得到各种不同的性能优异的模式和个体。 终止循环的条件采用设定最大代数的方法。

4 流程图

该遗传算法的流程图如图1所示。

5 模拟试验

文中以淮安市科技局2011年立项项目 “智能公交站台预报系统”公交线路1为例。早上第一班车的发车时间是5:30，最后一班车的发车时间是21:30，全天一共运行960分钟，分为20个时段，每个时段48分钟。1路车共有20个站点，线路总长为n公里。1路公交车的车型定员为35人。初次选定 α=0.5，β=0.5，种群大小为 500，初始温度为 500，最大遗传代数为30。经过多次的模拟实验，可以得到线路1的由南向北的最佳的发车间隔是6 4 3 2 4 2 4 5 3 4 5 5 2 4 2 5 3 4 5 8。即发车时间依次为:5:30 5:36 5:42 5:48 5:52 5:56 6:00……6:36 6:40 6:43……7:25 7:28 7:30……8:14 8:16 8:20……9:06 9:08 9:52......10:36 10:40 10:45……11:25 11:30 11:33……12:12 12:15 12:19……13:00 13:04 3:09……13:50 13:55 14:00……14:55 15:00 15:02……15:46 15:48 15:52……16:30 16:32 16:36 16:38……17:22 17:24 17:29……18:9 18:14 18:17……18:59 19:02 19:06……19:46 19:50 19:55……20:35 20:40 20:48 20:56……21:22 21:30

图1 算法流程图Fig.1 Flowchart of algorithm

用同样的方法模拟由北向南的调度时间，和由南向北的发车时间大概是一致的，这主要是因为不同方向的客流量是差不多的，这是因力1路车的南边终点站是汽车南站，北边终点站是汽车北站和火车站，这于现实情况也是相符的。通过以上简单的模拟试验，可以看出，综合改进的遗传算法应用在公交调度系统中，可以快速得出调度结果，具有一定的使用价值。

6 结束语

公共交通线发车调度时长主要集中在优化发车间隔、车次多少等。目前任何城市全面构筑智能公共交通系统，特别是公共交通智能化调度系统还有一定的困难，因此实时地确定所有线路的发车间隔还比较困难。如果智能公共交通系统建立在优化的网络基础上，会使其发挥更加突出的作用。本文是从公共交通线网发车间隔的调度为出发点，对公交网络系统进行优化，提出了公共交通线网发车间隔优化数学模型，将遗传算法引入到模型求解中，实例证明模型和算法具有实用性和可靠性。

[1]Brouwer D R，Jansen J D，Vefring E H，et a1.Improved reservoir mangement through optimal control and continuous model updat—ing[C]//SPE Annual Technical Conference and Exhibition，Houston，Texas，U S A，2004.

[2]Sarma P，Aziz K，Durlofsky L J.Implementation of adjoint solution for optimal control of smart wells[C]//2005 SPE Resevoir Simulaiton Symposium，Houston，Texas，U S A，31 January，2005.

[3]杨晓光.先进的公共汽车交通优先系统结构 （ABPS）[C]//城市交通研究中心，2005.

[4]杨新苗.城市公交发展技术保障体系关键技术研究[D].南京：东南大学，2002.

[5]郭振宇.上海巴士公交信息化中的关键技术[D].上海：上海交通大学，2005.

[6]高自友，吴建军，毛保华，等.交通运输网络复杂性及其相关问题的研究[J].交通运输系统工程与信息，2005，5（2）：79-84.

GAO Zi-you，WU Jian-jun，MAO Bao-hua.Study on the complexity of traffic networks and related problems[J].Journal ofTransportation SystemsEngineering and Information Technology，2005，5（2）：79-84.

[7]高自友，赵小梅，黄海军，等.复杂网络理论与城市交通复杂性问题的相关研究[J].交通运输系统与信息，2006，6（3）：41-47.

GAO Zi-you，ZAO Xiao-mei，HUANG Hai-jun.Reasearch on problems related to complex networks and urban traffic systems[J].Journal of Transportation Systems Engineering and Information Technology，2006，6（3）：41-47.

[8]张晨，张宁.上海公交网络拓扑性质研究[J].上海理工大学学报，2006，28（5）：489-494.

ZHANG Chen，ZHANG Ning.Topology research on shanghai public traffic network[J].Journal of University of Shanghai for Science and Technology，2006，28（5）：489-494.

[9]崔宝侠，姚艳君，段勇.基于改进遗传算法的公交智能高度[J].沈阳工业大学学报，2010，32（4）：405-410.

CUI Bao-xia，YAO Yan-jun，DUAN Yong. Intelligent scheduling of public traffic vehicle based on improved genetic algorithm[J].Journal of Shenyang Un iversity of Technology，2010，32（4）：405-410.