（控制理论与控制工程专业论文）基于遗传牛顿算法的公交优化调度.pdf

p u b l i ct r a n s p o r to p t i m a ld i s p a t c h i n gb a s e do nt h e g e n e t i c n e w t o na l g o r i t h m b y z h a n g x i a o p e i b e ( a ny a n gi n s t i t u t eo ft e c h n o l o g y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n c o n t r o lt h e o r ya n dc o n t r o le n g i n e e r i n g c h a n g s h au n i v e r s i t yo fs c i e n c e & t e c h n o l o g y s u p e r v i s o r p r o f e s s o rl im a o j u n a p r i l ，2 0 11 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果。除了文中特别加以标注引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律后果由本人承担。 作者签名：歇目抽姥 e l 期：2 0 j 生f5 月2 7 e i 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权长沙理工大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：孑夭现磕 名蘸军 日期：2 州年箩月 日期纱年f 月 日 日 7 1 ， 刁卵 摘要 随着社会经济和城市化进程的快速发展，城市人口和汽车数量有了 突飞猛进的增长，由此对交通的要求越来越高。现有的道路交通容量日 趋饱和，城市交通拥堵问题日益严重。由于城市公交具有运量大、相对 投资少、占有道路少等优点，所以为了适应城市发展，政府和相关部门 大力提倡发展城市公共交通，提高公交出行分担率。提高公交的运营水 平是吸引乘客的关键，公交调度是公交企业运营管理的核心内容，所以 公交车优化调度问题的研究具有越来越重要的现实意义。 本文对传统的优化方法和部分现代智能算法进行了研究和分析，在 总结了它们各自优缺点的基础上，提出了一种将遗传算法和牛顿算法相 结合的混合算法，这种算法将自适应遗传算法和牛顿算法相结合，遗传 算法中的自适应交叉、变异算子确保算法向着有利的方向收敛，牛顿算 法克服遗传算法后期进化能力差的缺点。 本文介绍了公交优化调度的基本原理；根据公交车运营和客流量的 特点，在兼顾公交公司与乘客双方利益的情况下，建立了以发车间隔为 决策变量的公交车优化调度模型；提出运用遗传一牛顿算法来解决公交车 调度问题。采用m a t l a b 对基于遗传一牛顿算法的公交调度模型进行仿 真，仿真结果验证了该混合算法的有效性和优越性。 关键词：公交车；运营调度；发车间隔；遗传算法；牛顿法算；混合算 法 一一 a b s t r a c t w1 t ht h e r a p i dd e v e l o p m e n to fs o c i a l e c o n o m ya n du r b a n i z a t i o n 1 n c r e a s l n gh i g h l yo fu r b a np o p u l a t i o na n dt h en u m b e ro f c a r , t h ed e m a n dt o t r a f f i cb e c o m e s h i g h e ra n d h i g h e r t h ed e m a n d u s u a l l ye x c e e d st h e t r a n s p o r tc a p a c i t y ，a n dr e s u l t si ns e v e r et r a f f i c c o n g e s t i o n b e c a u s eu r b a n p u b l i ct r a n s i th a st h ea d v a n t a g e so f l a r g e rc a r r yc a p a c i t y ，r e l a t i v e l yl e s s l n v e s t m e n ta n d1 0 w e rr o a do c c u p a n c yr a t e ，i n o r d e rt oa d a p tt ot h eu r b a n d e v e i o p m e n t ， s o g o v e r n m e n t sa n dr e l a t e d d e p a r t m e n t sh a v es t r o n 9 1 y a d v o q a t e dt h a t d e v e l o p i n gp u b l i c t r a n s p o r t a t i o n sa n d i m p r o v i n gt h e p r o p o r t i o no f t r i pb y b u s i m p r o v i n g t h e q u a l i t yo fb u s d i s p a t c h i n g m a n a g e m e n ti sv e r yi m p o r t a n tt o a t t r a c tp e o p l et o t r i pb yb u s t h eb u s d l s p a t c h i n gi sv i t a lf o rp u b l i ct r a n s p o r t a t i o n m a n a g e m e n t ，s ot h er e s e a r c h o nb u s d l s p a t c h i n go p t i m i z a t i o nh a sm o r ea n dm o r e i m p o r t a n tp r a c t i c a l s i g n i f i c a n c e t r a d i t i o n a l o p t i m i z a t i o nm e t h o d s a n ds o m e m o d e r ni n t e l l ig e n t a l g o r i t h ma r es t u d i e da n dc o m p a r e di nt h e t h e s i s ，b a s e do nt h e i r r e s p e c t i v e a d v a n t a g e sa n d d i s a d v a n t a g e s ， a na l g o r i t h mw h i c h w a sc o m b i n e dw i t h g e n e t l ca l g o r i t h ma n dn e w t o ni s p r o p o s e d t h i sa l g o r i t h mm a k ea d a p t i v e g e n e t i ca l g o r i t h ma n dn e w t o na l g o r i t h mc o m b i n e d t h e a d a p t i v ec r o s s o v e r a n dm u t a t i o no p e r a t o r so ft h eg e n e t i ca l g o r i t h m e n s u r et h ed i r e c t i o no ft h e h y b r i da l g o r i t h mt ob e c o n v e r g e n t ，a n dn e w t o n a l g o r i t h mi n c r e a s e t h e c o n v 盱g e n c es p e e do fg e n e t i ca l g o r i t h m ln eb u so p t i m i z a t i o nt h e o r yi s i n t r o d u c e di nt h i sp a p e r ；b a l a n c i n gt h e i n t e r e s t so fp u b l i ct r a n s p o r tc o m p a n ya n d p a s s e n g e r s ，t h eo p t i m a ls c h e d u l e m o d e l 7 fp u b l i ct r a n s p o r tw a ss e tu pw i t ht h ed e p a r t u r e i n t e r v a la st h e v a m b l e h y b r i dg e n e t i ca l g o r i t h mw h i c hc o m b i n e dw i t hg e n e t i c a i g o r i t h m a n dn e w t o ni s p r o p o s e dt oo p t i m i z et h es c h e d u l em o d e l u s i n gm a t l a b t o s i m u l a t et h eb u s s c h e d u l i n gm o d eb a s e do ng e n e t i c n e w t o na i g o r i t h m a n d t h es i m u l a t i o nf e s u l t sp r o v et h i sa l g o r i t h m i se f f e c t i v ea n ds u p e r i o r i t y k e yw o r d s ：p u b l i ct r a n s p o r t ；o p e r a t o r g e n e t i ca l g o r i t h m ；n e w t o n n s c h e d u l i n g ；d e p a r t u r ei n t e r v a l ； m e t h o d ；h y b r i da l g o r i t h m 目录 摘要i a b s t r a c t i i 第一章绪论 1 1 公交车调度的研究背景及研究意义1 1 2 国内外研究现状与分析2 1 2 1 国外研究现状2 1 2 2 国内研究现状3 1 2 3 国内外研究的区别4 1 3 论文的主要工作5 第二章公交车调度模型 2 1 公交客流的特点7 2 1 1 客流的构成及特点7 2 1 2 客流的不均衡性7 2 2 公交车调度数学模型9 2 2 1 模型假设1 0 2 2 2 符号说明1 0 2 2 3 模型的建立11 2 3 本章小结1 2 第三章优化算法 3 1 优化算法的综述13 3 1 1 经典的优化方法d dod q 1 3 3 1 2 现代智能优化方法15 3 1 3 经典算法和现代智能算法的比较17 3 2 遗传一牛顿算法1 8 3 2 1 遗传算法1 8 3 2 2 牛顿算法2 7 3 2 3 遗传一牛顿算法2 8 3 3 本章小结2 9 第四章基于遗传一牛顿算法的公交调度 4 1 约束条件的处理3 0 4 2 算法设计3 0 4 2 1 编码方式3 0 4 2 2 初始种群的生成3 1 4 2 3 适应度函数的选取31 4 2 4 遗传算子3 2 4 2 5 终止条件的判断3 3 4 2 6 局部搜索3 3 4 3 算法流程3 3 4 4 本章小结3 4 第五章公交优化调度的仿真实例分析 5 1 调度模型的参数3 5 5 2 算法的比较3 5 5 3 根据客流量变化时间段的调整实验3 8 5 4 模型中加权参数的调整实验41 5 5 结论4 l 总结与展望4 3 参考文献4 5 致谢4 9 附录a( 攻读硕士学位期间发表论文目录) 5 0 附录b( 攻读硕士学位期间参与相关课题) - 51 附录c( 典型工作日客流统计数据) 51 第一章绪论 1 1 公交车调度的研究背景及研究意义 城市交通是城市赖以生存的重要基础设施之一，交通的发展水平是 衡量国家现代化程度的重要指标，同时也体现着国家的综合经济实力。 无论是在发达国家还是在发展中国家，伴随着经济的快速发展和城市化 进程的加快，城市交通问题日益突出。我国也毫不例外，随着我国经济 建设的快速发展，城市的社会、经济结构发生了巨大变化，社会经济文 化活动空前繁荣，各大城市的居民出行总量在逐年增加，城市的交通需 求急剧上升。特别是人们生活质量提高的同时，小汽车的拥有量也在快 速增长，交通流量日趋饱和现有的道路容量远远不能满足车辆数量的增 长需求。私家车的快速增长，使交通拥堵现象越演越烈，随之带来的环 境问题等相关问题也日益严峻，以致交通问题成为2 0 “年全国两会谈论 的焦点问题之一。因为交通拥挤、交通事故和环境污染等问题给社会和 个人造成的经济损失也在逐年的增加，这些问题不仅影响城市居民的生 活、也制约了城市及经济的发展。 解决城市公共交通问题，二方面是要调整交通结构通过道路及基础 设施的建设来提高交通通行能力；另一方面大力发展公共交通。从国际 成功经验来看，受城市发展空间和道路建设周期、资金的限制，单靠修 建道路并不能彻底解决交通拥挤问题；面对能源紧张、环境污染、道路 空间有限等问题，城市公共交通有着运载量大、占用道路空间小、相对 投资少等小汽车无法比拟的优势，所以公交优先发展已经成为国内外城 市交通发展的目标和方向，发展公共交通是缓解交通压力和提高全社会 经济运行效率的一个重要手段。从8 0 年代起，我国政府就明确提出了城 市客运交通以公共交通为主的发展方针，并先后发布了相关政策和文件， 最近几年我国各大城市都在计划实施限制私家车，同时鼓励乘坐公共交 通出行是的政策。要达到这一目的，就必须要提高公交服务质量，让出 行人真正感觉到公共交通工具方便、省钱、快捷等优点。 城市公交运输体系一般包括公交车、地铁、轻轨、出租车、电车、 等，鉴于国内绝大部分城市，公交车是通用省钱的公共交通工具，所以 本文研究的城市公共交通即指的公交车。我国的公交发展普遍比较落后， 公交运营效率低、服务质量差，从而使乘客选择公交出行方式的比例不 。经过深入的调查发现公交调度方案是整个公交企业工作的核心，运 调度合理与否，直接影响到企业生产效率、经济效益和服务质量，并 一步影响居民的公交方式出行比例。合理的运营调度，是提高运输效 、缓解交通拥堵的有效途径。因此，研究城市公交车优化调度问题， 立合理的优化调度方案，对提高公交运营水平，改善我国交通问题的 状，有着重要的理论意义和现实意义。 2 国内外研究现状与分析 1 2 1 国外研究现状 由于经济发展早的原因，国外特别是一些发达国家对于公交调度优 化重视的比较早，研究的也比较深入，所以公交车调度方面的理论和技 术都有了大量的研究成果和成功的应用实例。 在理论上，公交车调度是一个复杂非线性的伺题。所以在公交车调 度中，根据优化的目标不同，现有的研究基本上分四个方向：公交线路 的设计及优化、公交车辆调度、发车时刻表的编制以及司机的人员调度 等。p e t e rg f u r t h 针对同一条线路上、下行两个方向乘客到达率不相同情 况，在研究了优化放车调度过程的基础上提出了有用的优化模型； a v i s h a ic e d e r 在建立了公交车辆调度模型基础上，介绍了利用公交乘客数 据制定公交发车时刻计划的不同方法，并根据不同乘客要求选择不同的 调度方案；m a r q u e s 等研发了一个能够动态编制公交时刻表的计算机软 件系统：m a l a c h yc a r e y 研究了车辆的非准点到站分布，以及不同发车 间隔下乘客的到达率，鉴于费用消耗和出行时间等因素的考虑研究了时 刻表的制定问题 4 1 ；p a o l od e l l es i t e 等对公交线上的调度优化模型进行研 究和分析，并研究了在不同运营模式下的公交线路上的车型配置、发车 间隔和区间车等的优化调度；a c e d e r 等对制定公交时刻表时同步性最 大化做了研究，在考虑了用户的满意度和方便性的基础上，建立了多条 公交线路协调调度的发车模型；c h r i s t o sv a l o u x i s 等人通过分析以出行 费用最少为目标的车辆与司机的组合优化问题，并运用遗传算法进行优 化；a h a g h a n i 等研究了对多车场和带时间窗的多车场的车辆调度模型， 并阐述了相对应的启发式算法，得出了在一定条件下单站点车辆调度模 型优化结果是最好的结论 e l 。 在技术应用上，主要是指系统的设计、集成和应用软件方面。从上 世纪8 0 年代以来美国、日本、加拿大、韩国等国家在这方面取得了不错 的研究成果。9 0 年代产生的智能交通系( i n t e l l i g e n tt r a n s p o r ts y s t e m ) 即 2 i t s ，更是把理论研究和技术应用的发展推上高潮，并使公共交通运营和 管理推向全面的智能化。它的主要体现是将现代电子技术、通讯技术和 控制技术应用到公交的运营调度管理上，例如数据的采集和处理技术， 公交车辆的自动定位技术、电子收费技术、自动乘客计数器等。以美国 为例，目前车队管理中应用的技术有：低轨道地球卫星系统、个人通讯 系统、发散频谱系统、共享频谱技术、移动无线系统、无线数据通讯系 统和综合通讯技术等。应用软件方面，英国、加拿大、德国和英国一直 处于领先位置。例如英国利兹大学与w o o t t o nj e f f r e y 咨询有限公司联合开 发了的应用于微型计算机的公交调度系统b u s m a n t 、加拿大g i r o 公司 的产品h a s t u s ，、美国的m i t e r 公司开发的r u c u s ，除此之外以色列 工程技术大学的o p t i b u s 也是具有代表性的公交调度系统软件 i s j 。 1 2 2 国内研究现状 我国由于国情的原因，公共交通发展的比较晚。随着8 0 年代我国政 府对公交优先战略的确定，公交调度优化问题的研究才受到科学界的关 注。在过去的3 0 多年里，无论在基础理论研究，还是在公交系统建设技 术方面都取得了明显的成果。然而与发达国家相比较不管是在理论研究 方面还是在技术发展方面都还是处于初级阶段。 在理论上，蒋光震等介绍了一种基于乘客分布的公共交通线路静态 区间组合调度模型，；张纲针对公交网络优化问题，建立了以“总乘车 时间、换乘损失和因无路径受到惩罚最小”为目标函数的线网优化模型 等n 钉；王绍林对公交车的运营调度管理做了系统的描述和总结n ；陈继 军结合了上海市公交动态调度系统研究，对调度系统的理论和系统设计 进行了更深入的研究；孙芙灵针对公交车发车时刻问题进行了较为深 入研究，提出了几种确定发车时间间隔的方法：根据乘客需求确定一个 可供选择的发车间隔；当车辆供给受到约束时，相应地改变发车间隔； 在相邻的时间段使用平滑法调节发车间隔；在一个发车时刻表中综合利 用各种间隔设置法n7 】张飞舟对公交车的智能调度及相关的技术做了进 一步的研究，；陈茜对多条线路同步到达的区域调度模型和算法在我国 城市公交调度中的应用做了研究和讨论“】曹更新研究了混合算法在智 能调度管理中的应用，并研究了基于g p s - - g s m 的公交车辆动态调度系统 提供的平台上的动态调度】葛晨等在充分考虑了发车成本和乘客等车 成本对发车频率的影响的基础上提出了一种改进的确定发车时刻表的离 散方法1 ，；宋瑞等通过机会约束规则研究在公交走行时间不确定、乘客 需求不确定、以及乘客等待时间限制等因素影响下，企业利益如何在一 3 4 l 、调度目标 由于国外客流量小，交通发达，运营调度的目标是确保公布的各站 时刻表的准时性；而我国客流量大，在满足服务水平的前提下合理调配 车辆和人员是调度的主要任务。 2 、时刻表的种类一 国外客流量小，客流随日期、季节变化不是很明显，时刻表能保持 相对稳定，所以种类比较单一；而我国客流量大且变化也大，为保证公 交公司合理投入和乘客的利益，一般随着客流的变化，时刻表也是不停 的变化的，一般分为周时刻表、假日时刻表、冬天时刻表和夏天时刻表 等多种。 3 、时刻表的内容 国外客流量小，车辆间隔大，时刻表大多是每个站的停站时间和发 车时间，一般是印在公共交通站牌上的；而我国时刻表里面的内容是首 末站及重点大站时刻表，基本上没有每个站点的到达时间。 4 、车辆管理制度 国外一般有固定的车场，一个车场的车辆服务多条公交线路，车场 到线路的始发站一般有一定距离；我国每条线路均有各自的车场，一般 而言，车场即为始发站或两者距离较近。车辆在线路上的行走时间：国 外路况较好，拥堵现象不很严重，车辆在线路上的行走时间一般变化不 大，国内拥堵严重，特别像上海等大城市，高峰时段和平峰时段车辆在 线路上的行走时间变化比较大。 5 、驾驶人员管理体制 国外一般采用轮乘制，驾驶员可根据需要更换车辆；国内一般采用 包乘制，驾驶员固定在某一车辆，在休息或停在车场时，车辆的使用效 率就大大降低了。 最近几年，智能公交在我国大部分城市开始发展起来了，虽然国外 在这方面有许多可借鉴的成果，但是要研究出符合我国自身特点的智能 公交调度系统，所要做的工作还是很多的。 1 3 论文的主要工作 从国内外研究现状的分析来看，调度时刻表的制定是公交公司运营 的主要工作之一，而发车时间间隔又是制定时刻表的关键。论文针对时 刻表里面的发车间隔问题，对公交调度进行了研究，并根据遗传算法的 基本原理和实际问题的处理，在改进遗传算子的基础上融合了牛顿算法， 将混合的遗传算法应用于公交车调度问题中。主要研究工作有： 5 ( 1 ) 在大量查阅资料的基础上，对比分析了国内外公交车调度的研 究现状和区别。 ( 2 ) 研究了公交车调度的各种模型，分析各种模型的特点，并建立使 公交公司和乘客费用损失最小的调度模型。 ( 3 ) 总结了常用优化问题的经典算法和智能仿生算法的优缺点。在 标准遗传算法和牛顿算法特点的基础上，提出改进的遗传一牛顿算法。 ( 4 ) 详细介绍了混合算法在公交车调度问题中的计算步骤。 ( 5 ) 通过m a t l a b 编程对公交车调度模型进行仿真实验，验证该算 法的有效性，并给出了不同情况下的发车时间间隔。 6 第二章公交车调度模型 公交调度问题是一个复杂的非线性多目标优化问题，它需要同时兼 顾公交公司和乘客两方面的利益。发车间隔的确定充分体现了这两者间 矛盾的关系，公交公司总是希望提供尽量大的发车间隔，单位车辆有足 够高的上座率，以减少其运营成本，增加运营的收入；而乘客则希望发 车间隔要足够的小即获得更加快捷的服务，以降低其出行所消耗的成本。 然而发车间隔过短，公交企业投入的成本越高，不利于公交企业经济效 益的提高，发车间隔过长，又会导致乘客候车时间过长，降低乘客的满 意度。因此根据公交车运营的特点，建立合理的调度模型是研究发车间 隔的关键。 2 1 公交客流的特点 公交客流数据是公交调度工作的前提，在公交调度的公交线路、站 点、发车次数和发车间隔等的确定中它都起决定性的作用，因此研究并 掌握其变化规律是十分重要的。 2 1 1 客流的构成及特点 根据出行目的，将公交客流的构成分为工作性客流和生活性客流两 大类n ”。 ( 1 ) 工作性客流：上班和上学的人员组成的。 特点是：客流量大、规律性强、乘车时间比较集中，是客流高峰时 的主要来源，也是全日客流总量的主要部分。 ( 2 ) 生活性客流：由人们为了丰富和满足自己的生活的出行构成，如 购物、探亲访友、娱乐等。 特点是：在一天中持续时间长，受气候变化和季节变化的影响较大。 一般来讲，节假日的客流量大，平时客流量相对较小，具有较大的稳定 性。 2 1 2 客流的不均衡性 公交客流是动态变化的，但是通过调查这种变化是有规律的，它主 要表现在时间和方向上的不均衡性。 1 、日内小时客流的不均衡 7 客流量在公交车的营业时段分布是不均衡的，尤其是在工作性客流 出现比较多的线路，存在明显的上下班高峰。一般情况下，公交客流量 存在着早晨渐增，上班和上学时达到高峰，午间稍减，傍晚随着下班和 放学又达到高峰，此后逐渐减少，午夜最低的规律。图2 1 为某公交线路 日内客流量变化图。 _ v 嘲 壤 坤 67891 01 11 21 31 41 51 61 71 81 92 0 2 l 时间( 小时) 图2 1 公交线路日客流变化规律 2 、周内全日客流的不均衡 由于人们的工作和休息是以周为周期循环进行的，这种活动规律必 然要反映在一周内各日客流的变化上来，一般周一到周二客流量大，周 三到周五客流量较小，周六、周日客流量又会发生变化。在以上班、上 学客流为主的公交线路上，双休日的客流量会有所减少，而在连接商业 网点、旅游景点的公交线路上，双休日的客流量又往往会增加。同时周 一到周五与周末的早、晚高峰时间段会有明显的差别。图2 2 是某线路一 个月的客流变化规律。 1 4 0 0 0 1 3 0 0 0 1 2 0 0 0 餐1 1 0 0 0 一 、。1 0 0 0 0 期 嫱9 0 0 0 摊8 0 0 0 7 0 0 0 6 0 0 0 135791 11 31 51 71 92 12 32 52 72 9 时间( 天) 图2 2 公交线路月客流变化规律 8 0 0 0 o 0 o o 0 o o 0 的诣们弘衢塬砌5 3 、季节性和节假日客流的不均衡性 在一年内客流还存在季节性的变化，如在以学生流为客流主体的公 交线路上，在寒、暑假时段客流量明显减小。在国家法定节日时，流动 人口的增加又会带来公交客流量的增加。所以季节性和节假日客流的变 化规律也是制定合理发车时刻表应该考虑的因素。 4 、区域间的不均衡性 某些区域出行过分集中，如公交线路上有商场、学校等的客流量大，起 伏变化幅度大，高峰时间显著；而某些区域出行相当较少，如郊区公交 线路客流上客流量小，乘车距离长，早晚方向性差异较大，一般规律为 早晨进城流量大，晚上出城流量大，节假日流量大，客流容易受天气变 化、季节变化的影响。图2 3 是郊区某线路上下行方向的客流变化规律实 线为进城客流量，虚线为出城客流量。 3 5 0 3 0 0 ，、2 5 0 懿 一 c l 三 ( 2 5 ) 了盐 急t 约束条件( 2 4 ) 说明了，第k 时段发车时间间隔的上下限要满足的相 部门的规定的上下限。一般情况下高峰期发车间隔不得超过5 m in ，低 期发车间隔不得超过l0 m in ；约束条件( 2 5 ) 说明公交公司一天的运营 处于盈利状态。因为公交公司要盈利，所以必需使公交公司的收益大 公交公司最低的消耗成本。 3 本章小结 本章对公交公司和乘客利益进行了分析，根据客流的变化规律在兼 顾公交公司与乘客双方利益的情况下，建立了以发车间隔时间为变量的 公交车优化调度模型并进行了详细的阐述。从模型可以看出发车间隔主 要受客流量和时间段的影响，因此有必要研究不同客流量分布和不同时 间段的划分对解决实际问题的影响。 1 2 第三章优化算法弗二早v l 儿异法 3 1 优化算法的综述 求解优化问题一般要进行两项工作：第一是将实际问题抽象地用数 学模型来描述，包括选择优化变量，确定目标函数，给出约束条件；第 二是对数学模型进行必要的简化，并用适当的最优化方法求解简化的数 学模型。最优化是人们在工业、农业、交通运输等诸多领域中经常遇到 的问题，它主要是寻找某些具有数学结构问题的最优解。最优化方法大 致可以分为两类，即经典的优化方法和现代智能优化方法。 3 1 1 经典的优化方法 基于经典优化算法的方法有：线性规划、非线性规划、整数规划、 动态规划等。 ( 1 ) 线性规划：线性规划( l i n e a rp r o g r a m m i n g ，简称l p ) ：线性规划 是研究在一组线性约束条件下，寻找线性目标函数的最大值或最小值的 问题。该模型计算迅速快、收敛性好，便于处理各种约束，但缺点是计 算精度低。 文献 3 6 基于智能交通运输系统的背景，研究提供公共交通信息的 条件下公交换乘时间最短的调度问题，提出线性规划模型，并用算例进 行了求解。文献 37 运用线性模型分配频率，使路网改变之后公交网络 上的换乘数据最大化。 ( 2 ) 非线性规划( n o n l i n e a rp r o g r a m m i n g ，简称n l p ) ：非线性规划是 具有非线性的约束条件和或目标函数的数学规划，是运筹学的一个重要 分支。非线性规划研究一个n 元实函数在一组等式或不等式的约束条件下 的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数 ，。非线性规划模型又可分为一阶梯度法和二阶梯度法。一阶梯度法主 要有简化梯度法、微分注入法等；二阶梯度法包括牛顿法、内点法、外 点法等。非线性规划模型的特点是精度比较高，但计算量相对较大，对 于大规模问题收敛特性不是很稳定。 非线性规划问题分为有约束非线性规划和无约束非线性规划。它一 般是利用罚函数将有约束的优化问题转化为无约束问题求解，或者基于 可行方向法直接求解有约束的优化问题：也有将非线性规划问题转化成 线性规划问题，然后求解。 1 3 文献 3 9 根据线路的延迟到达时间和换乘客流量等因素建立了公交 纽内多线路车辆的实时调度优化问题模型，并运用随机扰动梯度近似 法对问题进行求解。文献 4 0 研究了公交换乘枢纽选址与布局的优化 问题，用迭代法解决了换乘枢纽选址模型。 ( 3 ) 整数规划( i n t e g e rp r o g r a m m i n g ，简称i p ) ：整数规划是指优化的 目标函数中的决策变量只能取整数值的非线性或线性规划问题。在整数 规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部 分变量限制为整数，则称为混合整数规划。求解整数规划的方法有穷举 法、割平面法、分支定界法、分解法等。 文献 41 首先提出使用整数线性规划解决排班问题的理论与方法； 文献 4 2 依据公交公司车辆时刻表的制定提出了有3 个目标函数和2 4 个 约束条件的多目标非线形整数规划模型，并给出了求解模型的计算方法。 文献 4 3 用整数规划中的运输问题建模思想，建立了多条线路在客流峰 值变化的互补下实现综合平衡与优化的模型，用于解决各个错峰线路之 间的车辆的配置问题。文献 4 4 研究了基于最大同步换乘的公交区域调 度优化问题，并将该多目标优化调度优化模型描述为混合整数规划问题。 文献 4 5 针对公交车调度问题进行了分析，根据上、下行的发车时刻表， 考虑到公交车的循环利用，引入0 1 变量，建立了公交公司一天中所需要 公交车总量的0 1 规划模型。在假设各站上、下车人数服从均匀分布的条 件下，对模型进行了求解。 ( 4 ) 动态规划( d y n a m i cp r o g r a m m i n g ，简称d p ) ：动态规划是针对多 阶段决策问题的特点提出的最优化原理，并成功解决了工程技术、生产 管理等方面的许多实际问题。动态规划法把复杂问题化为一系列相互联 系的转多阶段序列来处理，通过合理选择各个阶段决策的集合并找出各 阶段之间的关系，使整个过程的总效果达到最优。动态规划中每个阶段 都是一个优化的问题，它使每个阶段的约束集合也简单，更利于得到全 局最优解，并且可以利用经验提高求解的效率。但是它的不足之处是用 数值方法进行求解时存在维数灾的问题。 动态规划是一种重要的决策，可以用于解决最优路径选择和资源分 配等问题。在处理某些优化问题，比线性规划或非线性规划方法更有效。 文献 4 6 在动态规划一章的案例分析中详细讲解了动态规划在公交车调 度中的应用。文献 4 7 通过对公交车调度问题逐层深入分析，进而确定 影响系统的本质因素，运用动态规划的思想，合理抽取典型样本数据， 采用时间步长法对模型求解。 1 4 3 1 2 现代智能优化方法 近些年来，人工智能进化算法得到了飞速的发展，这类算法对目标 函数的性态无任何要求，可以方便地考虑各种约束条件。与经典的优化 算法原理截然不同，它们主要是模拟自然生态机制来求解复杂优化问题， 这些方法主要有人工神经网络、遗传算法、免疫算法、粒子群算法等， 它们在并行性、随机性、自适应性、鲁棒性、非线性复杂问题的搜索能 力等方面表现出了显著的特点。这些优化算法大大丰富了最优化技术， 为那些用传统的方法难以处理的优化问题提供了切实可行的解决方法。 下面分别介绍几种常用的智能优化算法。 ( 1 )人工神经网络 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，简称a n n ) 是模拟人脑思维 方式的数学模型。神经网络是在现代生物学研究人脑组织成果的基础上 提出的，它是模拟人脑神经系统功能，包括信息处理、学习、联想、记 忆等。目前神经网络模型的种类有4 0 多种，典型的有b p 网络、h o p f i e l d 神经网络等h 。1 。它们具有以下优点：可以充分逼近任意复杂的非线性关 系；所有定量或定性的信息都等势分布贮存于网络内的各神经元，故有 很强的鲁棒性和容错性；采用并行分布处理方法，使得快速进行大量运 算成为可能；可学习和自适应不知道或不确定的系统；能够同时处理定 量、定性知识。所以神经网络为解决复杂的非线性、不确定优化问题开 辟了新的途径。 神经网络在交通中的应用很多，如文献 4 9 研究了公交线路上各站 点的客流量统计和预测方法，将b p 神经网络与城市公交系统紧密结合， 确定了输入变量的构成、变量数据的获取，输人量和输出量的对应关系 及实现从输入到输出的对应关系。文献 5 0 将b p 网络应用于预测公交线 路的交通量的方法，给出b p 网络的结构和它的学习算法，分析了预测变 通量的b p 神经网络方法。最后将这种方法用于预测一条线路的公交线路 的交通量。神经网络法收敛特性好，但是如果缺乏十分有效的学习方法， 它在训练过程中很容易陷入局部极值。 ( 2 )遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是一种将达尔文进化论的自然 选择和自然遗传机理引入到数学理论中的全局优化概率搜索算法。该算 法作为一种概率搜索和自适应优化方法，在求解非线性问题时与其他算 法相比具有较好的鲁棒性、全局优化性和并行性。但是它仍然存在一些 缺点，主要是局部搜索能力差、收敛速度慢、容易早熟和迭代次数多等问 1 5 题。因此许多学者对遗传算法进行了相关的改进。 目前，遗传算法及其改进算法已被很多学者应用到公交调度上。文 献 51 研究了遗传算法在公交线路优化系统中的应用；文献 5 2 研究了 遗传算法在时刻表生成中的应用，并在交叉运算中插入了局部选择的策 略，结果表此种改进可以很大程度地加快遗传算法的收敛速度；文献 5 3 针对遗传算法中的早熟等问题，在遗传算法中引入适值模拟退火拉伸思 想，并研究了其在公交发车间隔优化中应用。 ( 3 )人工免疫算法 人工免疫算法( a r t i f i c i a li m m u n ea l g o r i t h m ，简称a i a ) 生物免疫系统 是一个高度进化的生物系统，它能够识别和排除抗原性异物，保护机体 免受损害及维持内机体的稳定。从计算的角度来看，生物免疫系统是一 个高度并行、分布、自适应和自组织的系统，具有很强的学习、识别、 记忆和特征提取能力。人类从免疫系统中不断获得新的启示并创造出越 来越多智能方法，去解决复杂的现实问题，a i a 就是其中的一种方法。在 人工免疫算法中，被求解的问题视为抗原，抗体则对应于问题的解，采 用复制、交叉、变异等算子进行操作，逐代逼近最优解。与遗传是算法 相比，它通过抗体之间的亲和力保证了可行解的多样性。 基于免疫系统原理开发的各种模型和算法广泛地应用在科学研究和 工程实践中，比如电力系统、数据挖掘、机器人学、故障诊断、车间调度 等领域都得到了应用。近年来，人工免疫算法也逐渐被应用到交通系统 中，例如文献 5 4 将免疫算法应用到车辆调度路线安排中，并根据车辆 调度问题的具体情况，提出了一种基于分组匹配的亲和力的免疫算法； 文献 55 建立了基于公交线路时段客流数据的公交车辆优化调度模型， 并提出采用基于信息熵的人工免疫算法对进行求解。 ( 4 )粒子群算法 粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，简称p s o 算法) 是一种进化 计算技术，19 9 5 由k e n n e d y 博士和e b e r h a r t 博士发明的。它的基本思想 来源于对鸟群觅食行为的研究。它将优化问题的解看作寻优空间中的一 只鸟，被抽象为没有质量和体积的微粒，在搜索空间中以一定的速度飞 行，通过对环境的学习与适应，根据个体与群体的飞行经验的综合分析 结果来动态调整飞行速度。 在整个寻优过程中，每个粒子都有一个被优化的函数决定的适应值 和飞行的速度，并且每个粒子都具有以下几类信息：粒子当前自己所处 的位置；到目前为止由自己发现的最好位置，此信息视为粒子自身的飞 行经验；到目前为止整个群体中所有粒子发现的最好位置，这可视为粒 1 6 子群同伴共享飞行经验。于是各粒子的运动速度受到自身和群体的历史 运动状态信息的影响，并以自身和群体的历史最好位置来对粒子当前的 运动方向和运动速度加以影响。粒子群算法是一种典型的群体智能实现 模式。模型中个体与个体、个体与其所处的环境的局部作用使整个群体 的宏观行为表现出全局性的智能涌现行为，这种特性为许多问题的解决 提供了新的方法。粒子群中的粒子个体是分布式的，不存在中心控制， 能够适应当前环境下的工作状态，并且具有较强的鲁棒性，另外分布式 计算的特征又避免了算法的早熟性收敛， 近几年，粒子群算法及其改进算法也在公交调度中得到了应用。文 献 5 6 将粒子群算法应用到发车间隔的公交调度模型中，并得到了理想 的结果；文献 5 7 提出将带收缩因子和线性递减惯性权重的粒子群优化 算法应用到公交智能排班中，算例结果表明，该算法具有比其它优化算 法更好的效率，是一种解决公交调度优化问题的有效方法。 3 1 3 经典算法和现代智能算法的比较 经典的优化算法和现代智能优化算法它们都有自己的优点和缺点， 本文对这两种方法的搜索方式及其优缺点进行比较和分析。 ( 1 ) 目标函数：前者对目标函数要求比较高，如连续、可微等，必 要时需要做简化和近似处理，这可能影响到解的真实性；后者不依赖于 目标函数的导数，工程上很多优化问题的目标函数是不可导的，若采取非 数值计算优化方法，则不需要知道函数的导数信