（计算机应用技术专业论文）改进的遗传模拟退火算法在公交排班中的应用.pdf

t h e a p p l i c a t i o no f t h ei m p r o v e dg e n e t i c - s i m u l a t e d a n n e a l i n g b u ss c h e d u l i n g b y h u a n g h o n g y o n g b e ( r i a n j i nu n i v e r s i t 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 f e n g i n e e r i n g c o m p u t e ra p p l i c a t i o n st e c h n o l o g y i n t h e g r a d u a t es c h o o l o f l a n z h o u u n i v e r s i t yo ft 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 rz h u c h a n g s h e n g m a y , 2 0 1 1 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：芗亥印日期：；o l l m 月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同 时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据 库，并通过网络向社会公众提供信息服务。 作者签名 导师签名 日期：别年月日 日期舀b ，产月9 日 综合改进的遗传一模拟退火算法在公交排班中的应用 目录 摘要i a b s t r a c t i i 插图索引i i i 附表索引i v 第1 章 绪论1 1 1 研究背景和意义2 1 2 国内外研究现状3 1 2 1 国外研究现状3 1 2 2 国内研究现状4 1 3 研究目标及主要内容6 1 3 1 研究目标6 1 3 2 研究内容7 1 4 主要创新点7 1 5 本文的内容安排8 第2 章遗传算法和模拟退火算法9 2 1 遗传算法概述9 2 2 遗传算法基本思想9 2 3 遗传算法基本步骤9 2 4 遗传算法相关术语1 0 2 5 遗传算法的优缺点1 l 2 6 遗传算法的应用1 2 2 7 模拟退火算法概述1 2 2 8 模拟退火算法的基本思想1 3 2 9 模拟退火算法的特点1 3 2 1 0 模拟退火算法的基本步骤1 3 2 1 l 模拟退火算法的优缺点1 4 2 1 2 本章小结1 4 第3 章改进的遗传模拟退火算法1 5 3 1 遗传模拟退火算法的简述1 5 3 2 遗传模拟退火算法构成要素1 5 3 2 1 遗传模拟退火算法的应用步骤1 5 3 2 2 编码表示1 6 3 2 3 适应度函数1 6 u 硕十学位论文 3 2 4 遗传模拟退火算子1 9 3 2 5 模拟退火函数2 2 3 3 改进的遗传一模拟退火算法2 2 3 3 1 改进的遗传模拟退火算法参数设置2 2 3 3 2 改进的遗传模拟退火算法终止条件2 3 3 4 本章小结2 4 第4 章公交排班问题模型设计2 5 4 1 模型的假设2 6 4 2 问题的描述2 6 4 3 建立数学模型一2 7 4 3 1 建立目标函数2 7 4 3 2 模型的约束条件2 8 4 3 3 发车时刻模型2 9 4 4 本章小结2 9 第5 章应用改进的遗传模拟算法求解公交排班问题3 0 5 1 改进的遗传模拟退火算法结构3 0 5 2 改进的遗传模拟退火算法设计3 0 5 2 1 编码3 0 5 2 2 约束条件的处理3 l 5 2 3 适应度函数3 2 5 2 4 初始化种群3 2 5 2 5 改进的遗传模拟退火算子的设计3 3 5 3 应用改进的遗传一模拟退火算法解决公交排班的仿真实验3 4 5 3 1 参数设置3 4 5 3 2 仿真实验一3 7 5 4 本章小结3 9 总结与展望4 0 参考文献4 1 蜀e 谢4 4 附录a 攻读学位期间所发表的学术论文4 5 硕十学位论文 摘要 随着世界城市化进程的发展及人们生活水平的提高，各大城市中公交问题尤其显著， 而目前我国大部分城市采用的是传统的手工调度方式，无法满足乘客出行的需要， 因此建立先进、智能化的公交系统是解决该问题的关键。而公交车辆智能调度首先要解决 的问题则是运营车辆的智能排班。 本文重点对改进的遗传一模拟退火算法( g a - s a ) 及其在公交智能排班中的应用进行了 研究，介绍了遗传算法( g a ) 的基本思想、步骤及优缺点，模拟退火算法( s a ) 的思想、 步骤及特点，并对将两者结合之后的g a - s a 进行了阐述。本文在g a - s a 的基础上，针对 其在编码操作、选择操作和模拟退火的降温操作中存在的不足进行了几点改进：1 ) 引入真 实值编码；2 ) 将轮盘赌选择与最优解保存策略选择相结合；3 ) 采用改进的降温函数，形 成了改进的g a - s a 算法，从而缓减了g a - s a 存在的模型太复杂不利于求解、早熟、容易 陷入局部最优而提前收敛以及进化缓慢等问题。本文结合公交车辆调度自身的特点，兼顾 公交公司与乘客双方的利益建立公交车辆行车计划模型，以发车时刻( 真实值) 为基因变 量进行编码，对两个相邻的发车间隔之差、最大最小发车时间间隔、乘客的满载率等条件 进行约束限制。结合实例，应用改进的g a s a 对该模型进行优化求解。最后，能够可靠地 在公交排班优化问题的巨大搜索空间中找到最优方案或近似最优方案。通过实验结果对比 分析，验证了改进后算法的有效性和优异性。 关键词：遗传模拟退火算法；改进的遗传模拟退火算法；公交排班 综合改进的遗传一模拟退火算法在公交排班中的应用 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ew o r l d su r b a n i z a t r i o np r o c e s sa n dt h ei m p r o v e m e n t o fp e o p l e s l i v i n gs t a n d a r d s ，b u sp r o b l e m i s p a r t i c u l a r l ys i g n i f i c a n t i n m a j o r c i t i e s b u tn o wt h et r a d i t i o n a lm a n u a ls c h e d u l i n gm o d ei sa d o p t e di nm o s to fo u r s c i t i e s ，w h i c hi su n a b l et om e e tt h en e e d s o fp a s s e n g e rt r a v e ly e t t h e r e f o r e ，a n a d v a n c e di n t e l l i g e n tt r a n s p o r t a t i o ns y s t e mi st h ek e yt os o l v i n gt h ep r o b l e m a n dt h e p r o b l e m ，t ob es o l v e df r i s t l y , o ft h ep u b l i ct r a n s p o r tv e h i c l e si n t e l l i g e n ts c h e d u l i n gi s t h eo p e r a t i o no fi n t e l l i g e n tv e h i c l es c h e d u l i n g t h ew o r kh a sm a d ek e yr e s e a r c ho nt h ei m p r o v e dg e n e t i c - s i m u l a t e da n n e a l i n g a l g o r i t h m ( g a - s a ) a n di t sa p p l i c a t i o ni nb u si n t e l l i g e n ts c h e d u l i n g a n dt h eg e n e t i c a l g o r i t h m s w i t hi t sb a s i c i d e a ，s t e p sa d v a n t a g e s a n d d i s a d v a n t a g e s h a sb e e n i n t r o d u c e d ，a sw e l la ss i m u l a t e da n n e a l i n ga l g o r i t h m s t h e nm a d ea ne x p o s i t i o no ft h e g e n e t i c s i m u l a t e da n n e a l i n ga l g o r i t h ma f t e rb e i n ge o m b i n i n e d i nt h i sp a p e r ，o nt h e b a s i so ft h eg a - s a ，t oi t sd i f i c i e n e i e st h a te x i s ti n c o d i n go p e r a t i o n ，s e l e c t i n g o p e r a t i o na n dc o o l i n go p e r a t i o nw i t hs i m u l a t e da n n e a l i n g ，s e v e r a li m p r o v e m e n t s h a v em a d e ：1 ) i n t r o d u c e dc o d eo ft h et r u ev a l u e ；2 ) c o m b i n i n gr o u l e t t ew h e e ls e l e c t i o n a n dt h e o p t i m a l s o l u t i o n p r e s e r v a t i o ns t r a t e g y ；3 ) u s e d t h e i m p r o v e dc o o l i n g f u n c t i o n ，a n df i n a l l yf o r m i n gt h ei m p r o v e dg a s aa l g o r i t h m t h u s ，i tm i t i g a t e ss o m e p r o b l e m sp r o d u c e de x i s t i n g i n g a s a ，s u c h a s a g a i s t i n gs o l v i n go w i n gt o c o m p l i c a t e dm o d e l ，p r e m a t u r e ，e s a yt of a l li n t ol o c a lo p t i m u ma n dr e s u l ti na d v a n c e d c o n v e r g e n c e ，s l o we v o l u t i o n ，e t e i n t h e p a p e r , w i t h t h ec h a r a c t e r i s t i c so fp u b l i c t r a n s p o r tv e h i c l es c h e d u l i n gi t s e l f , a n dc o n s i d e r i n gt h ei n t e r e s to f b o t hp a s s e n g e r s a n dp u b l i ct r a n s p o r tc o m p a n y , t h ep u b l i ct r a n s p o r tv e h i c l e st r a v e lp l a n n i n gm o d e li s e s t a b l i s h e d i tm a k e sc o d i n gw i t ht h ed e p a r t u r et i m e ( t r u ev a l u e ) a sg e n ev a r i a b l e ，a n d h a sr e s t r i c t i o n so nd e p a r t u r ei n t e r v a la n dt h ed i f e r e n c eo ft w oa d ja c e n to n e s ，t h e l o a df a c t o ro fp a s s e n g e r s ，t h em a x i m u ma n dm i n i m u mo fd e p a r t u r ei n t e r v a l ，e t c b y i n s t a n c e s ，t h ei m p r o v e dg e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h mi sa p p l i e dt oo p t i m i z e t h em o d e f i n a l l yc a nb er e l i a b l yf o u n dt h es c h e m eo ra p p r o x i m a t eo p t i m a ls c h e m ei n t h e g r e a t s e a r c h s p a c e o ft h e o p t i m i z a t i o np r o b l e m so fp u b l i ct r a n s p o r t s c h e d u l i n g t h r o u g he o m p a r i s i o n a n d a n a l y s i s o f e x p e r i m e n t a lr e s u l t s ，t h e e f f e c t i v e n e s sa n ds u p e r i o r i t yo ft h ei m p r o v e da l g o r i t h mi sv e r i f i e d k e y w o r d s：g e n e t i c - s i m u l a t e d a n n e a l i n ga l g o r i t h m ；t h e i m p r o v e d g e n e t i c - - s i m u l a t e da n n e a l i n ga l g o r i t h m ( g a - s a ) ；b u ss c h e d u l i n g i i 硕+ 学位论文 插图索引 图4 1 数学建模的过程一2 5 图5 1 改进的遗传模拟退火算法的基本流程图3 0 图5 2 各站乘客到达率3 4 图5 3 传统g a 、g a s a 和改进的g a s a 算法下的全天发车频率分布图比较3 9 i l l 综合改进的遗传一模拟退火算法在公交排班中的应用 附表索引 表5 1 最优个体目标函数随交叉概率的变化过程3 5 表5 2 最优个体目标函数随变异概率得变化过程3 6 表5 3 参数设置表一3 6 表5 41 3 9 路发车时刻表3 7 i v 硕十学位论文 第1 章绪论 世界城市化是未来城市发展的一大趋势，这种趋势一方面加快了经济发展， 而同时不可避免地会带来一些忧患。其中较为突出的就是城市交通问题，一旦该 问题不能得到很好的解决，它将会从很大程度上对人们日常的生活和生产造成一 定的影响。那么如何解决交通问题已经成为目前及未来人们研究讨论的热点之 一。为了进一步提高交通道路的通行能力以及公交运营管理水平，建立智能化、 先进的公交系统( a d v a n c e dp u b l i ct r a f f i cs y s t e m ，a p t s ) 是解决城市交通隐患的 关键【1 1 。 在公交调度所需考虑的众多问题中，公交排班是核心。它一方面有助于调度 人员与司乘人员工作上的协作进行，同时还将以此为依据对公交车辆的运行情况 进行考核。公交排班的最终目的即制定一张合理的、有效的、最佳的行车时刻表， 它需要综合几方面的因素，如既定线路的车辆数目以及当前客流量和首末发车时 间等。它一方面体现了公司对社会的承诺，另一方面也体现了其服务水平的情况。 在运营成本给定的条件下，如果乘客等车时花的时间越少，说明公交公司的运营 服务水平也越高。当然，如果采用粗放经营方法，即单方面依靠“增加车辆、增 加人力 ，同样可以达满足乘客出行需求的目的，但它没有将公交公司的利益考 虑进去。在实际情况中，既要考虑在最大程度上满足乘客出行需求，同时还要考 虑让公司收益最大，故这是一个多个目标的优化问题。 在公交排班问题的众多解决方法中，遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 较为常见【2 1 。该算法有两大优点：1 ) 通过遗传因子的迭代在一个较小的区域启 发式地搜索全局最优解；2 ) 以较大概率趋向全局最优解。同时在实际应用中它 也存在自身的不足，如早熟、易陷入局部最优而提前收敛等。故实际应用中一般 将它与其他的优化算法组合，常见的有模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 。 二者的结合能够有效地解决复杂的n p 优化问题，这是常规的优化方法难以达到 的效果。但是在实际应用中，传统的g a 以及g a s a 3 普遍存在较多问题，如算 法太简单、进化缓慢、模型过复杂难于求解、易陷入局部最优从而导致提前收敛 等等。 基于以上考虑，本文在g a s a 的基础上，针对其在编码操作、选择操作和 模拟退火的降温操作中存在的不足进行了改进，形成了改进的g a s a 。从而缓 减了g a s a 存在的一系列问题，并结合实例，将改进后的算法应用于公交排班 的具体模型中。 综合改进的遗传一模拟退火算法在公交排班中的应用 1 1 研究背景和意义 随着城市的发展、经济的繁荣以及人口的增多，人们的经济条件日益改善， 社会生活日益丰富，从而使得其对交通的要求也越来越高。不论是在发达国家还 是在发展中国家，交通问题都日益严重与突出，已经深刻影响了各国城市的社会 生产和生活。如何解决交通问题已经成为现代人们生活中亟待解决的问题之一。 解决交通问题最直接办法就是提高路网的通行能力。最初，为了解决交通量日益 增长造成交通拥挤的问题，我们采用了加大道路修建的方法。然而我们的生活空 间毕竟有限，不可能无限制地加大道路修建，并且投资的资金也有一定局限。经 过一系列探索及经验总结，我们逐步认识到：解决好交通问题，必须一方面大力 发展城市公共交通，即实施公交优先战略【4 5 】；另一方面在技术上全面利用智能 交通系统来解决交通问题【6 】，因而智能交通系统( i t s ) 便成为解决这个问题的 重要途径之一【7 1 。由于公共交通运营管理与城市建设发展不相协调，结合世界发 达国家交通发展的趋势和城市公交建设的科学技术手段，我国政府也开始着手推 行智能化管理。发展公共交通的i t s 技术、开发交通信息、推行交通控制技术并 建立智能化交通调度系统【8 l 。对这些i t s 主要技术的研究，可以增强车辆、道路、 司乘人员以及管理人员之间的联系，使他们之间能够很好地相互协调，从而形成 一个高速的、安全的、便捷的交通运营环境p j 。 然而目前我国大多数城市的公交运营服务已经不能很好地满足乘客的出行 需求，这主要是因为一方面城市居民对公交服务有着高质量的要求，而另一方面 公交的运营方式和调度模式相对还比较落后，这无疑导致了两者间的矛盾。现代 城市的居民对出行参考信息的要求是准备、快捷，而如今的公交调度营运模式已 经不能满足出行居民这种较高服务质量的要求。当前公交调度在大部分城市仍然 采用的是传统的人工调度方式，在这种传统的公交车辆调度过程中，由于调度人 员对己发车辆在道路上的交通环境以及乘客流量等状况无法了解，只能按照预先 制定的静态行车时刻表进行调度，司机在路上遇到特殊情况也就无法接受合理的 调度指令以及正确的行驶指指引，这样往往就会造成许多不必要的资源浪费或出 现乘客长时间在车站滞留等情况，如何才使得调度中心能够实时地获知调度所需 的必要信息呢? 这就在很大程度上要求公交调度系统能够及时地、准确地采集到 以下信息：如车辆状态及位置、沿线道路的状况、沿线的客流量等等，为智能调 度提供全面的、有效的、及时的数据支持。如此才可以从路况、车流、客流等这 些实际情况出发，能够更好地进行最佳调度方案的选择，使得整个公交线路上出 现最佳的运行状态，并且现代通讯技术的高度发展以及信息管理技术的不断进步 将为公交公司在人力和物力上的节省做出很大贡献，从而使得公交公司一方面工 2 硕士学位论文 曼曼曼曼量曼曼皇皇m n n i nmm o 皇曼曼曼量曼皇曼曼曼鼍曼曼曼曼墨 作效率得到了提高，另一方面投资成本也得到了降低。因此，引入智能公交不仅 使社会效益得到提高，并且能够为公交公司经济效益得到进一步的提高【9 】。 对于传统的公交运营而言，线路排班【l o 】是核心，目测客流以及手签路单。 这种排班主要是基于排班员的经验以及传统的通信设备。排班员传达排班指令时 主要采用电话等通讯工具，当突发情况出现时，正常的行车秩序遭到破坏，现场 排班这时就会出现所谓“瞎子排班的现象，然而这种状况已经很难与现代化城 市快速的发展步伐同步。目前我国公共交通运输管理技术，在很多方面仍然处在 “构想 和“初步实验 的阶段【1 1 l2 1 。因此建立完善的城市公交车辆排班系统， 在评价公共交通车辆排班方案将各种经济性与非经济性指标进行综合，而在此基 础上进行的新的组织功能的重构就显得格外重要了。 由此可知，在对城市公共交通进行研究时，一方面既要考虑宏观层面上的交 通规划的研究，同时还要考虑到公共交通企业本身的利益，因此在遵循城市整体 发展的基础上，一个较好经济效益的公交管理系统的建立就有着极其重要的现实 意义【l3 1 4 j 。而公交车辆智能调度最关键的问题就是车辆排班问题，因而如何得 到最优的公交车辆智能排班计划对公交公司具有重大经济价值和现实意义。多年 来国内外实践经验一致表明：大力发展公交交通并建立起先进的、智能化的公交 管理系统是解决城市交通问题的关键，而在先进的公交系统中有效的公交调度是 不可或缺的重要部分，衡量一个公交调度系统因素很多，其中关键因素之一便是 车辆的智能排班，因此研究公交车辆智能排班对提高道路服务质量以及公交车辆 运营管理水平起着非常重要的作用。 1 2 国内外研究现状 1 2 1 国外研究现状 发达国家很重视对公交调度优化的研究，并且在很早以前就开始研究，实例 应用及研究成果存在很多，主要在公交车辆相关信息的调度，如自动采集、运输 和处理等方面得到体现。2 0 世纪9 0 年代初某学者针对车辆的非准点到站分布进 行了相关研究，同时还研究了当发车间隔不一样是乘客的到达分布情况以及在综 合考虑乘客对费用及出行时间等因素的情况下对时刻表制定问题的研究。本世纪 初有学者提出一种自动控制策略，它对车辆到站时刻的控制是通过路线上固定的 控制站完成的。该研究使得控制信息的延误问题得到了很好的解决。本世界八十 年代以后，许多公共交通部门为了提高公交服务水平将先进的信息与通信技术应 用于交通问题的研究中。在经济上，欧、美、日等发达国家尤其关注降低公交成 综合改进的遗传一模拟退火算法在公交排班中的应用 本以及提高公交运输效率问题【1 5 , 1 6 】。美国主要针对公交系统的有效性、可靠性 1 7 , 1 8 】进行了重点研究，包括传达精确可靠的出行参考信息给出行者，从而使得 更多的人可以利用这些信息来进行选择适合自己的出行方式。欧美等发达国家对 于智能公交调度的研究给予了高度的重视和巨大的投入，截止至今，已经有大量 科研成果和高新技术付诸于应用【1 9 】。 可见，发达国家无论在宏观的交通规划方面还是在具体的道路管理系统方面 均很重视公共交通。但是，公交车辆排班问题属于n p 难题【2 0 】范畴，一般不易求 得其精确解。因此对于公交车辆排班问题主要还是采用现代非线性数学方法来寻 求非精确最优或者近似最优解，即满意解。各国根据自客观条件和自身实际情况 采取具体的解决办法。 1 2 2 国内研究现状 我国属于发展中国家，道路建设发展也很快，目前算得上是发展速度最快的 国家之一。但是一方面城市居民对公交服务有着高质量的要求，而另一方面公交 的运营方式和调度模式相对还比较落后，这无疑导致了两者间的矛盾，并且这一 矛盾也日益严峻和显著。尤其在城市中，交通问题的解决迫在眉睫。为此，近十 年来我国也逐步对i t s 展开了一系列的研究，并针对现有的公路交通运输网，研 究了如何提高运输效率、运输安全保障以及环保的可能性。2 0 世纪9 0 年代以来， 政府有关部门对i t s 技术的研究给予了高度重视，并先后组织了多次i t s 国际性 的研讨会。对促进国内i t s 研究的发展起到了非常大的推动作用。在许多地方 i t s 已初具规模，其中北、上、广等地率先实行了智能调度。各个科研院所也相 继在不同层次上展开了对i t s 的研究，并且进行了相关的i t s 试验。尤其在2 0 世纪末，有关i t s 的试验、研究及国际交流活动等越来越多。各级交通部门在技 术引进和自主创新方面也做了大量工作，一些先进技术逐渐在国内部分大城市交 通部门得到应用。交通部也将i t s 列入2 0 1 1 年长期规划及“九五 科技发展的 计划当中。并自从1 9 9 5 年开始就不断委派代表团去参加i t s 世界会议【2 。国内 一些研究人员对智能公交的研究也加大了人力和物力的投资，其中比较具有代表 性的有：吉林大学的杨兆升对智能公交系统框架做了一定的研究；北方交大的张 庆国在公交调度优化问题中引入了g a ，但是采用的是传统的g a ，运算效率较 低；西安科技大学李书兵公交调度中采用了模拟退火算法；北京航空航天大学的 任传祥提出了混合传统遗传模拟退火算法，该研究对运算效率有所提高，但还 达不到理想状态。 由于我国关于智能公交的研究起步晚且理论基础较差，科研人员虽在不断进 行大量工作，但由于受到诸多实际情况的约束限制，使得相应技术不能得到很好 4 硕士学位论文 的推广。其中研究主要集中于对系统模式的探讨以及硬件设备的选择方面，而在 信息采集以及运输处理等方面缺乏系统的研究。目前主要集中在对货运车辆进行 排班这个领域，所用方法总体相似【2 2 】【2 4 1 。而对公交车辆智能排班领域的研究目 前相对较少。目前，我国城市公交车辆排班的研究比较落后，所能查到的文献多 为一些零散的、理论性的，大多仍处于探讨阶段，其中多数采用传统的人工方法 对排班方案进行编制。相关领域的其它研究也寥寥无几，偶见国内外一些报道也 多为应用某一单一的方法，只能解决公交排班问题的某个方面。 目前我国各大城市多采用传统的方法，它是在最大程度上来满足乘客的出行 需求并将其作为基本目标。它通常建立在这样一个假设的基础之上：乘客越多， 则公司收入也就越多，于是公司的效益也就越好。传统公交排班采取的具体做法 是：首先，根据线路吸引区范围的居民人口数量与居民出行系数相乘得出居民出 行需求或者还可以根据调查所掌握的资料得到居民的出行需求；然后，测算最大 断面客流的近似密度；最后，在满足最大断面客流的前提下来安排车辆。我国各 大城市普遍采用传统的公交排班理论及方法。但由于传统公共交存在的一些弊 端，使得企业对真正符合行车计划的内在规律不予以考虑，同样也不会对公交科 学排班问题进行研究。在当今市场经济高速发展的时代，传统的公共排班方案已 经满足不了实际需求了。 纵观国内外学者所涉及的运输排班问题的研究，如m a h m a s s a n i 2 5 1 ， t h o m a s 2 6 1 ，c h a r l e s 2 7 1 ，卢厚清【2 8 1 ，s o n g 2 9 1 ，v a n 3 0 1 ，李军【3 1 1 ，p e s e n t i 3 2 1 等。 多数将重点放在车辆安排的优化问题上，即基于路径或行程时间最优的条件下求 解运输排班问题。虽然已有国内学者在这方面做了大量的理论研究，但研究的问 题也只能针对一些特殊的情况，而与实际应用尚有一定的距离。 近1 0 年来，许多学者将研究的重点集中在排班问题的近似算法以及优化算法 等方面，比如如何有效地、合理地对车辆实际运营情况进行排班管理。车辆运输 排班问题本身属于n p 复杂问题，也是排班问题的重难点问题。虽然己有一些学 者通过采用随机搜索法【3 3 1 以及人工神经网络3 4 1 方法对车辆排班问题进行研究， 然而研究对象大多是货物车辆运输排班问题，而应用智能算法对公交车辆排班问 题进行的研究目前还不多见。 在公交企业的众多管理工作中，公交运营工作是核心也是基础。它是根据客 流的变化情况以及具体运营条件或者其它的条件，来安排合适的车辆及行车计划 方案。这属于一个多目标的优化问题。传统的理论方法大多集中于运筹学、管理 科学以及工业工程等领域。多采用割平面法、动态规划法、分枝定界法以及拉格 朗日乘子法等【35 】研究方法。但是伴随着公交调度问题的规模的扩大以及计算复 杂性的增大。尤其是当对实时性及动态性有要求时，传统方法就很难解决了。其 中大部分属于n p 复杂问题，而且得不到精确的解【3 6 , 3 7 】。人工智能a i ( a r t i f i c i a l 5 综合改进的遗传模拟退火算法在公交排班中的戍用 i n t e l l i g e n c e ) 的快速发展，给该问题的解决带来了新的生机。公交智能排班问题 中a i 方法由于自身的优势显得越来越重要，并已经取得了一些重要的相关科研 成果，如运用非数值并行搜索方法- - g a 3 8 4 2 】( g e n e t i ca l g o r i t h m ) ，模拟退火 s a t 4 3 。4 5 1 ( s i m u l a t e da n n e a l i n g ) 以及禁忌搜索t s 4 6 - 4 8 ( t a b us e a r c h ) 等对调度 问题进行优化。这些优化算法各有优劣，在一些研究领域已经得到了广泛应用， 其理论框架基本形成。如杨自厚，唐立新1 4 9 】等人对c i m s 下m r p i i 的多级生产批 量计划问题进行研究时采用了g a 算法，该算法对结果有了明显的改善，与启发 式算法相比具有明显的优越性。 总的来说，目前国内在智能交通方面的研究还处于起步阶段，尚未形成一定 的深度和广度，与国外还有一定的差距。虽然国外现存诸多可供借鉴的成果，然 而我国的公交运营问题本身受到自身国情因素的约束，在很大程度上有别于国外 的情形。故研究出符合我国国情的合理的公交调度优化系统还有许多工作要做。 1 3 研究目标及主要内容 1 3 1 研究目标 随着世界城市化进程的快速发展，城市人口逐渐增加以及人们生活水平的提 高，各城市交通问题尤其突出。智能交通系统( i t s ) 便成为解决这个问题的重 要途径之一。公交调度问题是公交车辆智能调度需要解决的典型问题之一，而行 车时刻表是公交调度日常指挥车辆运行的重要依据，因此制定一张合理的行车时 刻表便显得非常重要和必要。在i t s 的背景下，用改进的g a s a 解决公共交通排 班中存在的问题，可以帮助公交企业提高车辆利用效率、降低运营成本、提高服 务质量等。 本文在g a s a 的基础上，针对其在编码操作、选择操作和模拟退火的降温操 作中存在的不足进行了改进，形成了改进的g a s a 算法，从而缓减了g a s a 存在 的模型太复杂不利于求解、早熟、容易陷入局部最优而提前收敛以及进化缓慢等 问题。并结合公交车辆调度自身的特点，兼顾公交公司与乘客双发的利益建立公 交车辆行车计划模型，结合实例，应用改进的g a s a 对该模型进行优化求解。最 后能够可靠地在公交排班优化问题的巨大搜索空间中找到最优方案或近似最优 方案。从而验证了改进后的算法的可行性和优异性。 6 硕士学位论文 1 3 2 研究内容 本文在g a s a 的基础上，针对其在编码操作、选择操作和模拟退火的降温操 作中存在的不足进行了三点改进：1 ) 在编码操作中，为了避免繁琐的编码采取 了真实值编码，提高了该算法的计算效率；2 ) 针对g a s a 算法中的进化缓慢、 容易陷入局部最优而提前收敛等问题，在进行选择操作时将轮盘赌选择和最优解 保存策略选择结合起来，既保证了进化速度，又保证了算法的收敛性；3 ) 退火 过程中一般的降温过程过快而有可能得不到全局最优解，针对这一问题，采用了 改进的降温函数，使得降温过程较为缓慢，从而能够得到更多的性能更好的解， 尤其是在进化一定代数之后，算法逐步逼近最优解，这个时候需要降温越来越慢， 这样有利于搜索到全局最优解，这是一般的降温函数无法满足的。从而缓减了 g a s a 存在的模型太复杂不利于求解、早熟、容易陷入局部最优而提前收敛以及 进化缓慢等问题，形成了改进的g a s a 算法。本文结合公交车辆调度自身的特点， 兼顾公交公司与乘客双发的利益建立公交车辆行车计划模型，以发车时刻( 真实 值) 为基因变量的进行编码，对两个相邻的发车间隔之差、最大最小发车时间间 隔、乘客的满载率等条件进行约束限制，结合实例，应用改进的g a s a 对该模型 进行优化求解。最后能够可靠地在公交排班优化问题的巨大搜索空间中找到最优 方案或近似最优方案。通过实验结果对比分析，验证了改进后的算法的可行性和 优异性。 1 4 主要创新点 本人查阅了大量相关文献，参与了陕西宝鸡公共交通智能化调度指挥系统工 程项目，目睹了深圳蓝泰源电子科技有限公司公交智能调度软硬件的配合实施， 对公交调度问题有了一定的了解，包括i t s 在公交调度中的应用，公交调度存在 的问题及解决方法。最后引入g a s a 对如何优化排班调度的问题进行探讨。并对 其做了如下改进，创新思想主要体现在以下几个方面： ( 1 ) 在编码操作中，为了避免繁琐的编码采取了真实值编码，提高了该算 法的计算效率。 ( 2 ) 针对g a s a 算法进化缓慢、容易陷入局部最优而提前收敛等问题，在 进行选择操作是将轮盘赌选择和最优解保存策略选择结合起来，既保证了进化速 度，又保证了算法的收敛性。 ( 3 ) 退火过程中一般的降温过程过快而有可能得不到全局最优解，针对这 一问题，采用了改进的降温函数，使得降温过程较为缓慢，从而能够得到更多的 7 温越来越慢，这样有利于搜索到全局最优解，这是一般的降温函数无法满足的。 1 5 本文的内容安排 本论文的具体组织结构如下： 第1 章：绪论。本章主要介绍了基于改进的遗传模拟退火算法的智能公交排 班问题的研究目的及其意义，智能调度系统和公交排班问题的国内外研究现状， 阐述了本文的主要研究内容、目的以及主要创新点。 第2 章：遗传算法和模拟退火算法简介。概述遗传算法和模拟退火算法的基 本概念、发展与现状、主要思想以及其优缺点等；介绍了遗传算法和模拟退火算 法的特点、应用等。 第3 章：改进的遗传模拟退火算法简介。概述遗传模拟退火算法的基本概 念、构成要素等，并对其进行改进形成改进的遗传模拟退火算法。 第4 章：公交排班问题模型设计。对公交排班问题进行深入研究分析，建立 适合于改进的遗传一模拟退火算法的数学模型。 第5 章：应用改进的遗传模拟退火算法求解公交排班问题。根据公交智能排 班问题的特点，设计出最优的综合改进遗传模拟退火算法，最后运用改进的遗 传一模拟退火算法对公交智能排班问题的数学模型进行仿真实验来验证其可行 性。 最后，全文的总结以及对未来研究工作的展望。 8 硕十学位论文 第2 章遗传算法和模拟退火算法 2 1 遗传算法概述 遗传算法( g a ) 由美国某大学教授于2 0 世纪7 0 年代初年首先提出，它是一 种模拟自然进化过程来搜索最优或近似最优解的优化方法，它的一个重要特征 是：个体之间能够进行信息交互以及采用群体并行搜索的策略【5 们，它不存在求 导或者函数连续性的限制，且没有特定的遗传规则，而是采用概率变迁规则来指 导它的搜索方向，从而具备较高的鲁棒性，易于优化，因此应用范围也比较广泛。 g a 使得复杂问题的解决有了新的局面，尤其是在优化问题上。它是一种全局搜 索占优势的新型优化算法【5 1 1 。 2 2 遗传算法基本思想 g a 具有很广泛的通用性，不依赖于待求问题的领域和具体问题，它实质上 是一种搜索迭代寻优技术，它是从与待求问题相关的初始群体开始，依据遗传学 的选择、交叉、变异等操作规则，通过迭代进化，最终产生越来越优异的解。在 每一代进化过程中，根据适者生存和优胜劣汰的原则，更大概率接受优秀个体而 排斥劣势个体，使搜索过程向最优或近似最优解逼近，最终得到的