基于PSO的公交调度优化问题研究_增加改进的QPSO

摘??? 要 随着公共交通的兴起，城市公交的发车安排对城市居民的出行有着很大的影响。公交调度受到人流量、站点、时间、线路等多种因素的制约，错综复杂。本文以发车间隔为自变量，建立了以公交公司费用最小和乘客平均等待时间最短为目标函数的优化调度模型。由于不同时段有着不同的人流特点，每个时段的发车间隔应独立计算，因此这是一个多维度的函数优化问题。 粒子群优化算法是一种精度高、收敛快的进化优化算法。量子粒子群算法在粒子群的基础上引入量子特征，效果有明显提高。量子粒子群算法还在算法中嵌入有效判断早熟现象的方法，一旦发现早熟的特征，立即添加扰动，使粒子跳出局部最优，从而减少无效迭代。本文将量子粒子群算法引入到公交调度排班问题中，优化和仿真结果表明算法能有效地解决公交车辆的发车时间安排问题。 关键词：公交调度；粒子群算法；量子；早熟 引言 公共交通在疏散客流缓解交通压力方面有着其他城市交通运输工具无法比拟的优点。在现代城市中，公共交通的车辆资源是有限的，因而资源使用者之间对有限车辆资源的需求在时间上和运输服务上存在冲突和矛盾。公交车辆运营调度的任务就是有效管理和合理分配有限车辆资源，调整供需平衡，以解决供需矛盾，达到所求目标最佳。调度问题实际上是一个多目标优化问题，即在满足调度限制的解空间内，寻找使调度选择中提出的目标函数都满意的优化解。 ?由于公共交通是一个复杂的系统，在公交线路中车辆运行是一个动态过程，乘客到达和交通需求都是不确定和随机的，公交车辆在运行当中还会碰到很多不确定的其他影响因素，例如：车辆出现故障，没办法再行驶、出现交通阻塞、发生交通事故等，这些都是无法预知的，出现车辆晚点到站，同时到站车辆数过多的情况。这样就得需要对公交实行调度，及时采取实时调度方法，最大限度地消除突发问题对线路运行所造成的影响，以弥补可能出现的损失。 粒子群优化算法(Particle Swarm Optimization，PSO)是一种全局优化算法，能够有效解决各种约束或不带约束的复杂优化问题。算法源于对鸟类捕食行为的模拟，其突出特点是结构简单，运行速度快，计算量小，程序实现非常简洁，需要调整的参数少。相比遗传算法和其他优化算法，粒子群算法具有收敛快、局部寻优能力强等优点。 1.2 国内外研究现状 美国、欧盟、日本、新加坡等发达国家对于先进的公交系统(APTS)的研究给予了高度重视和巨大的投入，大量研究成果和先进技术被应用于城市公交系统之中，传统公交管理中存在的诸多问题得到了根本改善，其共同做法是强调公交信息的采集、信息的处理和信息的输出服务。各类传感器、摄像设备、GPS接受设备的大量采用使得公交信息采集技术日益完善。目前 ,应用较成熟的技术主要有:现代通讯技术、公交车辆自动定位技术、乘客自动计数系统、地理信息技术等。;车辆自动定位技术由定位技术和数据传输技术组成，通过该技术的使用可实时监控每一辆车所在位置并把信息传至控制中心。1993年英国的Malachy Carey研究了车辆的非准点到站分布，以及不同发车间隔下乘客到达分布，基于个体对费用、出行时间等因素的考虑研究了时刻表的制定问题［1］；1995年美国的Adamski等运用SIMULINK仿真工具对处于准点控制、发车间隔控制、协同控制和随机控制四种调度控制模式下的公交线路运营状况进行了仿真研究[2]；1999年美国的Maged Dessouky的等运用车辆跟踪技术研究了大间隔发车的公交车辆到站的延误分布，发现车辆的晚点与起始时间无关，为实时控制提供了一定依据[3]；以色列的A-Ceder等人于1999年对最大一致性的公交时刻表做了研究，建立了多条公交线路协调发车的调度模型[4]；美国的Randolph Hall等于2001年提出以线路上固定的控制站对公交车辆到站时刻进行控制的自动控制策略，有效解决了控制信息传输的延误[5]。 我国的公共交通发展主要是常规的地面公交，有些大城市开始发展轨道公交，公交线网布局不合理、出行时间过长，造成在站点等待时间过长都是在各个地方的城市公交系统常见的问题。需要一个更加优化的公交调度方案来完善城市公共交通，给人们带来更加方便、省时的出行环境。要达到这种要求，城市公交运输系统还存在很大的差距，体现在：为社会提供服务信息的水平低，乘客缺乏必要的乘车服务信息；调度缺乏必要的信息与辅助处理手段，主要是以经验为主被动、滞后的实施调度；企业管理信息化水平低，信息采集、传输初始仍以手工作业为主。因此，如何将众多的公交车辆纳入现代化、信息化、高效率的管理之中，解决由原始调度模式造成的低效率问题，是现代公交行业急需解决的问题。 北方交通大学ITS研究中心黄溅华等人对公共交通实时调度控制模型和方法做了深入研究[6-8]；吉林工业大学李雄飞等对路牌调度系统做了一定研究[9]；北方交通大学结合北京公交ITS示范工程对公交智能调度及相关技术进行了平台专家系统设计与开发、区域调度运营组织与调度体制等做了重点研究[10-12]；在智能系统方面，吉林大学的杨兆升教授对智能公交系统框架做了一定研究，并且深入研究城市公共交通智能化调度的关键理论和实施技术，提出了公交调度方式自动生成的基本原理和新方法，为公交智能化调度系统提供了关键的理论保证，并创造性的开发了功能齐全且实用的“智能公交车载机”，被称为IPTC（Intelligent Public Transit of Computer）型车载机[13]。北方交通大学的张庆国在公交调度优化中引入了遗传算法，构造了符合行车规律的编码方式、遗传操作和适应度函数。但是采用基本遗传算法，运算效率低，而且遗传算法的目标函数只是考虑了车辆的运行时间，没有考虑到乘客的等车时间[14]；上海交通大学的郭振宇在《上海巴士公交信息化中的关键技术》一文中也引入了遗传算法，同样目标函数只考虑了车辆的运行时间，用基本的遗传算法求解[15]；哈尔滨工业大学的刘翠所研究的排班模型，目标函数考虑了乘客的等车费用、乘客的车内费用和公交公司的可变运营费用，模型过于复杂，不利于求解[16]。 ???? 综上所述，对于公交调度研究，在引入各种计算方法的时候，过于简单的模型计算会导致结果的不够准确，过于复杂又不便于求解。从国内外对公共交通智能化的研究和开发可以看出，要实现公共交通实时调度，必须建立完善的支持调度的硬件系统(即调度系统)和相应的调度的软件(包括调度的方法和模型等)，这两者的结合才能真正达到公共交通调度和管理的智能化。采取最有效的计算方法求解得出最优化的公交系统模型，可以更有效的缓解城市交通压力。 1.3 本文主要研究内容 本文首先介绍了公共交通在现代城市生活中的重要地位，然后介绍了交通调度的主要难点。粒子群算法是一种寻优能力非常强的优化算法，本文介绍了基本粒子群算法和量子粒子群优化算法，并将其用在交通调度中，最后进行了实验仿真。本文的结构安排如下： 第一章? 绪论。介绍了公共交通调度问题的背景和意义，并说明了本文的主要研究内容和结构安排。 第二章? 基本粒子群算法。介绍了基本粒子群算法的优化原理，了解其优势，并与其他算法相比较。 第三章? 量子粒子群算法。介绍了加入量子运动特性的量子粒子群算法。 第四章? 公交调度实现。建立公交调度模型，以发车间隔为自变量，使用量子粒子群算法进行优化，并进行仿真实验。 第五章? 总结与展望。对本文的工作进行了总结并提出了未来工作研究的方向。