（计算机应用技术专业论文）基于遗传算法的公交智能排班方法研究.pdf

硕+ 学何论文 ! 曼! 曼曼曼! 曼曼! ! 量曼曼曼! ! 曼曼曼皇曼皇i ! ： ii_ 摘要 智能公交系统是智能交通系统( i t s ) 研究的一个主要方向，对公交车辆具有 定位跟踪、辅助导航、调度指挥、动态发布信息以及为出行者查询最佳路径等功 能。它的建立将最大程度地提高车、路资源的利用率，提高公交服务质量，从而 创造巨大的社会经济效益，因此智能公交系统技术的研究具有深远的意义。 而公交车发车时刻表的制定是智能公交系统的核心内容，是公交调度日常指 挥车辆正常运行的重要依据，也是公交调度人员和司乘人员进行工作的基本依据。 制定公交发车时刻表需要建立优化模型，并选择、设计有效的算法进行求解。目 前大部分的文献都是以一个统计时间段( 如l d , 时) 为基本对象建立模型，把整个 调度同期( 如一天) 划分成多个统计时间段，得出的都是该时间段内的均匀发车 间隔，而这忽略了整个调度同期内的数据变化。本文根据公交车辆排班和遗传算 法的特点，兼顾到乘客和公共交通公司的利益，建立了一种基于改进的遗传算法的 公交智能排班问题模型，以求解行车时刻表。该模型以乘客等车时间成本最小和 公共交通公司的收益最大为目标，考虑了将发车间隔和两个相邻的发车间隔之差 进行限制，对乘客的满载率等进行约束，利用综合改进的遗传算法进行求解，并 进行了仿真实验，求得整个调度时期内的不均匀发车时刻表。结果表明，改进的 遗传算法能够在公交智能排班优化问题的巨大搜索空间中可靠地找到近似最优 解，大大提高了计算效率。最后运用该发车时刻表进行了排班，不会出现“串车” 和“大间隔 现象，减少了乘客的等车时间和提高了车辆运营效率，达到了公交 系统智能化的要求。 关键词：公交智能排班；遗传算法：免疫遗传算法；适应度函数；行车 时刻表 摹1 二遗传算法的公交智能排班方法研究 a b s t r a c t i n t e l l i g e n tp u b l i ct r a n s p o r ts y s t e mi sam a i nd i r e c t i o nw h i c hi n t e l l i g e n t t r a n s p o r l a t i o n s y s t e m s( i t s ) s t u d i e s ，h a s s o m ef u n c t i o n sw h i c h l o c a l i z a t i o nt r a c k i n g ，a u x i l i a r yn a v i g a t i o n ，d i s p a t c hc o n t r o l ，d y n a m i ci s s u e o fi n f o r m a t i o no fp u b l i ct r a n s p o r ta n di n q u i r yo p t i m a lp a t hf o rj o u r n e y i t w a sc r e a t e dt om a x i m i z et h eu t i l i z a t i o no fv e h i c l e sa n dr o a d ，t oi m p r o v e s e r v i c eq u a l i t yo fb u s ，t h e r e b yc r e a t i n gah u g es o c i a la n de c o n o m i cb e n e f i t s ， s ot h es t u d yo fi n t e l l i g e n tp u b i ct r a n s p o r t a t i o ns y s t e m sh a sf a r r e a c h i n g s i g n i f i c a n c e h o w e v e r ，s t a r ts c h e d u l eo ft h eb u si st h ec o r eo fu r b a np u b l i ct r a n s p o r t s c h e d u l i n g a n dt h ef u n d a m e n t a lb a s i sw h i c hd i s p a t c h e r ，d r i v e ra n d c o n d u c t o ro fap u b l i cv e h i c l et ow o r ka n db u s e st or u nn o r m a l l y l a y i n g d o w ns t a r ts c h e d u l en e e dt oe s t a b l i s hac o r r e s p o n d i n go p t i m i z a t i o nm o d e l a n dt os e l e c ta n dd e s i g ne f f e c t i v ea l g o r i t h m st os o l v e a tp r e s e n t ，m o s to f t h er e s e a r c hl i t e r a t u r e sa r eb a s e do nas t a t i s t i c a lt i m ep e r i o d ( e g 1h o u r ) a s t h eb a s i co b j e c to fam o d e l ，o b t a i n e di nt h et i m ep e r i o do ft h eu n i f o r mg r i d s p a c i n g o b v i o u s l y ，t h i si g n o r e st h ee n t i r ep e r i o do ft i m et h ed a t ac h a n g e s o nt h eb a s i so ft h ec h a r a c t e r i s t i c so f p u b l i c t r a n s p o f t a t i o n v e h i c l e s s c h e d u l i n g a n dg e n e t i ca l g o r i t h m ，e s t a b l i s h e dam o d e lw h i c ht a k e si n t o a c c o u n tt h ei n t e r e s t so fp a s s e n g e r sa n db u sc o m p a n i e so fp u b l i ct r a n s p o r t s m a r ts c h e d u l i n gp r o b l e mb a s e do ni m p r o v e dg e n e t i ca l g o r i t h mi no r d e rt o s o l v et h et r a f f i cs c h e d u l e t h em o d e la i m sa tt h em i n i m u mo fp a s s e n g e r s w a i t i n gt i m ea n dt h em a x i m u mo fb u sc o m p a n y i n c o m e ，a n ds u b j e c t st ot h e m a x i m u ma n dm i n i m u md i s p a t c h i n gi n t e r v a l ，t h ed i f f e r e n c ev a l u eo f a d j a c e n t i n t e r v a la n dt h ef u l l l o a dr a t e t h e nt h e i m p r o v e dg e n e t i c a l g o r i t h mi sd e v e l o p e dt os o l v et h ep r o b l e m ，a n dt h r o u g h o u tt h es c h e d u l i n g p e r i o do fn ou n i f o r mt i m e t a b l ei so b t a i n e db yp r o g r a m m i n g w i t hs i m u l a t i o n r e s u l t ss h o wt h a tt h ei m p r o v e dg e n e t i ca l g o r i t h mc a nf i n dt h ea p p r o x i m a t e b e s tr e s u l ti nt h eh u g es e a r c hs p a c eo fo p t i m i z a t i o n ，w h i l eg r e a t l yi n c r e a s e d t h e c o m p u t a t i o n a le f f i c i e n c y f i n a l l yt h es c h e d u l i n g t i m e t a b l eh a sb e e n a r r a n g e dt ot h el i n e ，w h i c hw i l ln o ta p p e a rt h ep h e n o m e n o no f “t h es m a l l e s tg a p o r “t h e b i g g e s tg a p ”，r e d u c e dt i m ew h i c hp a s s e n g e rw a i t i n gf o r at r a i n ，a n d i m p r o v e d s e r v i c el e v e l so ft h ev e h i c l e i ta c h i e v e si n t e l l e c t u a l i z a t i o n l l 硕十学何论文 r e q u i r e m e n t so ft h ep u b l i ct r a n s p o r t a t i o ns y s t e m k e yw o r d s ：i n t e l l i g e n ts c h e d u l e ；g e n e t i ca l g o r i t h m ；i m m u n eg e n e t i c a l g o r i t h m ；f i t n e s sf u n c t i o n ；s t a r ts c h e d u l e i i i 基于遗传算法的公交智能排班方法研究 插图索引 图3 1 数学建模的过程2 0 图4 1 遗传算法的基本流程图2 5 图4 2 各站乘客到达率2 9 图4 3 群体目标平均值和最优个体目标值随进化代数的变化图3 2 图5 1 免疫遗传算法流程图3 6 图5 2 两种方法群体平均目标函数值随进化代数变化规律对比3 8 i v 项十学位论文 曼曼曼曼曼曼曼曼! 曼曼蔓曼i i i 一一一i l l ；i = i 一；一 i 一i l 一： ii 皇曼! 皇 附表索引 v 3 0 0 1 3 1 j c j 1 j 2 j 程程 一 一 过过 一匕匕 一 一 变变 率率 概概 一叉异 交变 程随随 过数数 一 究函函 表研标标表刻表目目置时问体体设车时个个数发车优优参路发最最各如 1 1 2 3 4 1 4 4 4 4表表表表表 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签 协 日期：少t 戽月莎日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同 时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据 库，并通过网络向社会公众提供信息服务。 储躲别柳 导师签名 日期莎阳年 月日 日期：少，年石月莎日 硕十学位论文 第1 章绪论 公交的调度问题主要围绕两大主题展开：一个是客流，另一个是行车的发车 间隔。客流数据是公交公司开辟线路、安排司售人员和车辆的主要依据，公交部 门根据客流制订出大的营运计划，然后进行车辆和人员的安排，将车辆和人员下 放到路队，站一级的调度员根据上级指定的大的营运计划指挥现场调度。发车间 隔是上述流程中的另一个重要的数据，它是由客流数据确定的，体现在大的营运 计划当中，直接指导现场调度如何调度车辆，并且发车间隔确定的合理性还影响 着公交营运的社会效益和经济效益。如果发车间隔过大发车较少，乘客的出行就 要受到很大的影响，如果发车间隔小发车数量较多，乘客的利益得到了很大的保 证，由于发车车辆多，能很好的满足乘车出行的需要，但是从另一方面来说公交 公司的车辆利用率会大大的降低，经济效益会受到影响。所以如何根据现有的客 流数据确定出合理优化的发车间隔是非常关键的问题，这也正是在整个调度系统 中引入优化算法的主要目的解决调度问题中的这个关键问题，这个问题解决 的也是整个智能调度系统智能化程度的一个重要体现和评价的一个关键点。公共 交通智能排班问题是城市公共交通智能调度的核心内容，是调度人员和司机等进 行工作的基本依据，也是公共交通车辆正常运行的基本保障。行车时刻表是按照 线路的当前客流量情况，确定发车频率，提供线路车辆的首、末车时间。它是公 交企业对社会的承诺，决定着为乘客服务的水平，发车间隔越小，服务水平越高， 但是公交企业投入的成本越高。行车时刻表的编制应是在满足客流需求的前提 下，尽量减少不必要的投入，这是个多目标优化问题。目前，遗传算法是解决公 交排班问题的有效方法之一。但在引入遗传算法的时候，普遍存在几个问题：( 1 ) 遗传算法太简单，分析问题不够透彻，导致最后得出的结果不准确，而且计算的 效率比较低【1 】；( 2 ) 设计的数学模型太过于复杂，用算法求解非常不方便；( 3 ) 很多的研究都是以调度周期内的一个统计时间段( 如1 小时) 为模型的基本对象， 而且最终得出的都是该统计时间段内的均匀发车间隔【2 1 ，但这往往忽略了整个时 间段内( 得出的结果更符合实际客流的变化) 的数据变化；( 4 ) 用遗传算法进 行设计时，采用的编码方法和遗传算子的选择方式不合适，最终导致计算效率不 高。鉴于以上的考虑，本文提出将综合改进的遗传算法应用于公交智能排班问题 中，设计的数学模型既考虑了乘客的利益，也考虑了公共交通公司的经济效益， 采用将发车的间隔( 最长发车间隔和最短发车间隔) 进行限制、两个相邻的发车 间隔之差( 以免出现“串车”和“大间隔 现象) 和乘客的满载率等进行约束， 利用综合改进的遗传算法进行设计，最终得出非均匀时间的发车时刻表。 基于遗传算法的公交智能排班方法研究 1 1 研究背景和意义 城市交通是城市居民从事各项生产、生活的纽带，它与广大市民的联系十分 密切，对城市的经济发展起着十分重要的作用。改革开放以来，我国各大城市在 经济建设与城市建设上都取得了长足的发展，在经济与城市建设快速发展的同 时，城市的规模不断扩大，城市人口迅速增长，对城市交通的需求日益增加。由 于城市交通设施建设滞后于交通需求的增长速度，使城市交通状况日趋恶化，在 主要交通道口和某些流量集中的道路上，不同程度地出现交通阻塞现象，城市交 通问题已成为制约城市发展的一个瓶颈。 与其它各种交通方式相比，城市公共交通具有其它交通方式无法比拟的优 势，城市公共汽车与小汽车和出租车等相比具有很多优点：投资少、运输客运量 大、占有的社会资源少、效率高、比较环保、人均占用道路少等，很多地方在采 取措施限制小汽车的使用，鼓励使用公共交通系统，研制开发低能耗、低污染的 新型交通工具等。由于城市公共交通具有很多优点，各级各地的政府部门和交通 管理部门已经逐渐意识到了公共交通带来的好处，纷纷提出了“公交优先 、“优 先发展公共交通是解决城市交通问题的基本前提之一”、“通过公共交通来引导城 市的发展等原则。 随着小汽车数量的增多，产生了许多社会问题，例如交通阻塞、交通事故、 能源短缺和环境污染等，有时统称为交通公害，人们也深刻的感受到了这些问题 对生产和人们生活造成的不便。那么，如何解决这些棘手的问题呢? 当时，美国、 日本、英国、德国、澳大利亚等发达国家开始研究高新技术在道路交通上的应用， 于是就出现了以信息技术和通信技术为代表的高新技术及其系统集成应用于交 通运输领域的实践，构成了智能交通系统【3 】- 【6 】( i t s ，i n t e l l i g e n tt r a n s p o r ts y s t e m s ) 雏形。智能交通系统是以完善的交通设施为基础，将先进的计算机处理技术、数 据通讯传输技术、电子控制技术、电子传感技术以及信息技术等综合技术，结合 运筹学、人工智能等有效地集成应用于整个交通运输管理体系。它加强人、道路、 车三者之间的密切联系，配合提高交通运输效率，从而形成一种定时、准时、高 效的综合运输系统，使交通基础设施发挥出最大的效能。提高路网通过能力，缓 解交通压力，减少交通事故，节约能源和保护环境等，使全社会获得巨大的社会 经济效益。 因此，在对公共交通的研究过程中，我们还必须从企业的利益角度来考虑。 在遵循城市整体发展的基础上，能够使公共交通全面的服务于人民且公交企业也 达到了良好的效益，这就是车辆智能调度存在的意义。由于人口的增加、环境法 规的健全和服务水平的提高，如何有效利用现有资源和资金，最佳调度车辆，以 2 硕十学何论文 最少的车辆数服务最多的乘客，是公交部门目前需要重点解决的问题，这对公交 系统规划具有深远的意义。有效的公交调度系统是先进的公交系统中不可缺少的 一部分，而公交车辆智能调度问题中最关键的问题就是车辆的排班问题，它是衡 量一个公交调度系统好坏的关键，因此公交车辆智能排班问题的研究对提高道 路公交车辆运营管理水平起着重要的作用，所以如何得到最优的公交智能排班计 划对于公交公司具有重大现实意义和经济价值。 1 2 国内外研究现状 1 2 1 国外研究现状 发达国家对于公交排班问题的研究很重视，而且开始研究的时间也较早，已 经有了大量的研究成果和应用实例。在经济上，欧、美、日等发达国家特别关注 如何降低公共交通成本和提高公共交通运输效率1 7 h 1 0 l 。美国对先进的公共运输 系统研究主要集中在如何使公共交通运输和合乘更有效和可靠的问题上【1 1j i 1 4 j 。 1 9 9 5 年3 月美国交通部门正式出版了“国家智能交通系统项目规划 ( n a t i o n a l i t sp r o g r a mp l a n ) ，明确规定了智能交通系统有七大领域和3 0 个用户服务功能， 其七大领域包括：出行需求管理系统、出行和交通管理系统、公共交通运营系统、 商用车辆运营系统、应急管理系统、电子收费系统、先进车辆控制和安全系统。 十几年过去了，美国的智能交通系统体系框架已经日渐完善，先后推出了五个版 本，引起了包括日本、澳大利亚、欧洲等其它国家的广泛关注，他们相继对本地 区、本国的智能交通系统体系框架进行了研究，描绘出了智能交通系统在各国的 发展蓝图，使智能交通系统的发展目标更明确和发展更稳定。 后来欧洲一些学者探讨了车辆的非准点到站分布，考虑了不同时间发车间隔 下的乘客到达情况，研究了时刻表的制定问题【l 引。 在国外，对公交发车时间表的研究主要经历了三个阶段，如表1 1 所示。 表1 1 发车时间表研究过程 第一阶段第二阶段第三阶段 每辆车每小时最大负 每辆车最大负荷和公 考虑因素每小时乘客最大负荷交线路不同方向的负 荷 荷 不均匀发车间隔 不均匀发车间隔 优化结果均匀发车间隔每小时最大负荷点平 最大负荷点平均负荷 均负荷 3 基于遗传算法的公交钾能排班方法研究 第一阶段研究时间表得到的是均匀的发车间隔，只考虑了每小时乘客的最大 负荷，这样得到的发车频率用最小发车频率来计算，满足了这个时间段的服务水 平：第二阶段考虑了公交线路中每辆车小时最大负荷因素，这时得到的发车间隔 为不均匀的；第三阶段考虑了每辆车最大负荷点和公交线路不同方向的负荷来计 算发车间隔，这样可以在满足一定的服务水平的前提下优化了车辆数。 国外在时间表的研究中，得到的多数是不均匀的发车时间表，以满足乘客需 求，增加车辆运营效率。近年，国外加大了对发车时刻表的研究。a c e d e r l l 6 】通 过交通需求得到了一种发车间隔不均匀的发车时间表；0 m e k k a o u i ，a d p a l m a ， r l i n d s e y f l 7 j 在假定乘客知道时间表的情况下建立了一种时间表优化模型；2 0 0 1 年，a c e d e r 等人1 1 8 j 在公交车时刻表的制定问题上进行了深入研究，考虑了给定 网络公交车同步性最大化问题以及乘客的满意度和方便性，为了使换乘的乘客在 最短的等车时间内，在换乘站点从一条线路到另一条线路上，如何使到达换乘点 的公交车的数量最大，该研究成果已经应用于以色列的公交调度系统中，取得一 定的效果。 1 2 2 国内研究现状 从2 0 世纪7 0 年代末至今，我国交通事业快速发展。各级交通部门通过技术引 进和自主创新，一些先进技术逐渐在中国部分大城市交通部门得到应用。上个世 纪九十年代就已经引入了i t s 的概念，i t s 在许多地方已初具规模，北京、天津、 上海、深圳等地率先实行了智能调度。“十五期间，科技部将“智能交通系统 关键技术开发和示范 作为重大项目列入国家科技攻关计划，我国i t s 发展取得 明显成效。我国智能交通系统的研究应用虽然起步较晚，但发展处于蓬勃上升趋 势。我国城市智能交通系统总体水平与发达国家城市相比还存在有相当差距，在 建设智能交通的各子系统中，由于各部门管理上各自为政，信息资源不能共享， 使建设成的子系统效率低，信息化、智能化水平低，没有真正的实现智能功能。 虽然我国在智能交通系统的基础研究方面做了不少工作，但仍然存在不少问 题。只有解决好了这些问题，智能交通必将对交通运输行业的形态和管理模式产 生深远的影响，对提高交通基础设施建设水平和城市的发展具有重要意义。我国 政府己将i t s 作为中国未来交通运输领域发展的重要方向，努力推广智能交通系 统的应用，发展智能交通系统技术，开发交通信息的综合利用，推行交通控制技 术，建立智能化交通调度系统【l 引。智能公共交通系统( a p t s ) 可使交通供给满 足动态的交通需求，克服原有静态方法的局限性，实现调度与运营的高效化，提 供快速、便捷、经济的换乘服务，使运营车辆间隔均匀，乘客流动有序，提高公 共交通的社会服务水平。 4 硕十学佛论文 曼曼! 曼曼蔓曼! 曼曼曼! ! 蔓曼曼皇! ! 蔓曼曼曼曼曼! 曼i i i 曼皇曼鼍 我国在交通运输车辆排班f 2 0 l - f 2 2 】领域的理论研究起步较晚，研究方法也大体 相似，而且多采用传统公交排班方法，例如用到了数学中的解析法【2 3 】- 【2 引，模拟 仿真方法【2 6 l ；随着运筹学的发展，运用了运筹学中的一些方法去研究公交排班 问题，例如割平面法、分枝定界法、动态规划 2 7 1 等运筹学方法；后来也用到了 概率方法【2 8 】和经验模型【2 9 】等方法去研究排班问题，但这些方法一般计算复杂，往 往得不到精确的解。传统公交智能排班的基本思想是在不考虑公交企业自身利益 的情况下最大限度地满足乘客的出行需求为目标，认为乘车的乘客越多，则企业 的收入就越多，于是企业的经济效益就会越好。这样的排班方法使得公交车辆的 行车速度下降、各车的问隔不均匀，会出现“串车”和“大间隔现象，导致乘 客的候车时l 、日j 过长和出现前车车厢内乘客拥挤不墩而后车车厢内空空荡荡的不 平衡状况，这样严重影响了公交车辆的服务质量。 随着智能交通系统的快速发展和公交优先战略的确定，智能公交车辆排班问 题的研究也越来越多。特别是近几年，借鉴了国外对公交排班问题的经验和技巧， 我国利用遗传算法t 3 0 l - 【3 2 l 对公交排班问题的研究取得了一定的进步。北方交通大 学的张庆国【3 3j 和上海交通大学的郭振宇【3 4 1 都在公交排班问题中引入了遗传算 法，但是他们采用的基本遗传算法中，目标函数只考虑了车辆的运行时间而没有 考虑乘客的等车时间，计算的结果不能有效地服务于乘客；四川大学的曹更新1 3 别 在研究公交智能排班问题时，将免疫遗传算法引入其中，但目标函数只考虑了所 有乘客的等待时间最短，而没有考虑到公交公司的利益；哈尔滨工业大学的刘翠 1 36 】对排班模型进行的研究中，目标函数既考虑了乘客的等车时间成本，又考虑了 公交公司的可变运营费用，但是设计的模型过于复杂，不利于求解；青岛科技大 学的童刚【3 7 】和山东大学的石峻1 3 8 l 建立了公交调度模型并求出均匀的发车间隔。 但利用一些约束条件和满足多方效益而建立起来的数学模型，通过遗传算法求解 得出非均匀发车时刻表的研究还不多。 综上所述，国外对公交排班问题的研究很多，并且一些方法也得到了实际的 应用。但国内在这方面的研究还处于初步阶段，一些方法还不够完善，研究的深 度和广度都很有限，与国外发达国家研究的差距还较大。虽然国外已经有许多公 交排班问题的研究成果可借鉴，但要研究出符合我国自身特点的公交排班系统还 有很多工作要做。我国在引入遗传算法解决公交智能排班问题时，要么引用的遗 传算法过于简单，导致结果不准确，计算效率低，要么设计的目标函数只考虑了 乘客的等车时间和公交公司的利益一个方面，要么模型太复杂不利于求解。用改 进的遗传算法设计的模型既考虑乘客的等车时间又考虑公交公司的利益，同时对 发车的间隔( 最大和最小) 、两个相邻的发车间隔之差以及乘客的满载率等都进 行约束，以发车时刻为变量进行编码，最终得出非均匀的发车时刻表，这样的研 究在国内外几乎没有。 5 基于遗传算法的公交钾能排班方法研究 1 3 研究目标及主要内容 1 3 1 研究目标 随着各国国民经济的可持续性发展，城市交通问题日益突出。城市交通系统 是由城市道路网、运载工具和管理系统组成的开放的复杂系统。解决交通问题就 需要从交通系统工程的根本出发，如何把人、车辆和道路综合起来考虑。运用各 种高新技术系统地解决城市道路交通问题，己成为世界各国广泛研究的内容。在 这种情况下，智能交通系统( i t s ) 便成为解决这个问题的重要途径之一。运营 车辆智能排班问题是公交车辆智能调度需要解决的典型问题之一，在i t s 的背景 下，公交车发车时刻表的制定是城市公交调度的核心内容，是公交调度日常指挥 车辆正常运行的重要依据，也是公交调度人员和司乘人员进行工作的基本依据。 合理的公交发车时刻表可以帮助公交企业提高车辆利用效率、降低运营成本和减 少乘客的等车时间以提高服务质量等。 本文结合现状，根据遗传算法和免疫遗传算法的特点，确保公交公司的效益 和社会效益都能得到最大限度满足条件下，对公交智能排班问题进行了研究。 1 3 2 主要研究内容 本文通过对遗传算法和免疫遗传的基本原理与技术的研究，主要解决公交排 班中的如下问题： ( 1 ) 建立适合于利用遗传算法和免疫遗传算法求解的问题模型，该模型以 发车时刻作为变量，同时考虑发车间隔最大最小、两相邻发车间隔之差有限值和 车辆满载率等的约束。 ( 2 ) 设计出适合于智能公交排班问题的遗传算法和免疫遗传算法，对其进 行优化改进。算法以客流信息作为研究的依据，得出非均匀的发车时刻表，同时 达到使乘客的等车时间最少和公交公司的运营收益最大。 1 4 主要创新点 在论文的写作过程中，作者查阅了大量相关文献，亲自在厦门公交总公司思 明分公司的调度中心实践了两个月，参考了该公司的公交调度系统，对公交问题 中的排班问题进行了详细的了解，最后引用改进的遗传算法和免疫遗传算法来对 公交排班问题进行研究。对全文的工作总结，作者的创新思想主要体现在以下几 个方面： 6 硕十学何论文 曼皇舅舅m m ln mm m。ii! i i 曼曼! 曼曼皇! 毫曼苎鼍曼鼍曼! 曼量曼! ! 曼! 曼曼曼曼曼曼鼍曼曼曼曼曼曼 ( 1 ) 目前在公交智能排班问题的研究中，大部分的文献都是以一个统计时 间段( 如1 小时) 为基本对象建立模型，把整个调度同期( 如一天) 划分成多个 统计时间段，得出的都是该时间段内的均匀发车间隔，而这忽略了整个调度同期 内的数据变化。本文以整个调度周期内的发车时刻作为变量建立模型，并根据客 流信息得出非均匀的发车时刻表，该时刻表能满足于不同客流量的发车间隔。 ( 2 ) 数学模型是在两个目标函数的基础上建立起来的，同时考虑了公交公 司和乘客的利益。 ( 3 ) 本文设计了最大和最小的发车间隔、两相邻发车间隔之差以及车辆满 载率多重约束条件，使其能够得到最佳优化解。 ( 4 ) 在构造适应度函数时采用罚函数法对多重约束条件进行了转换，将其 变成序列化的无约束问题进行求解，简化了计算量。对遗传算法进行了一些改进， 使其计算更方便，效率更高，最终得到最优解。 1 5 本文的内容安排 本论文的具体组织结构如下： 第1 章、绪论。本章主要介绍了基于遗传算法的智能公交排班问题的研究目 的和意义，智能调度系统和智能公交排班问题的国内外研究现状，阐述了本文的 主要研究内容和主要创新点。 第2 章、遗传算法简介。概述遗传算法的基本概念、发展与现状以及其主要 思想等；介绍了遗传算法的特点、应用和一些构成要素。 第3 章、公交智能排班问题模型设计。对公交智能排班问题进行研究分析， 建立适合于遗传算法的数学模型。 第4 章、求解公交排班问题的遗传算法。根据公交智能排班问题的特点，设 计出最优的遗传算法，最后用遗传算法对公交智能排班问题数学模型进行仿真实 验。 第5 章、混合遗传算法在公交排班问题中的应用探索。介绍了免疫系统和免 疫遗传算法，用免疫遗传算法对公交智能排班问题进行了设计和求解，最后进行 了仿真实验，比较了用遗传算法和免疫遗传算法对公交智能排班问题进行求解的 不同效果。 最后，全文的总结以及对未来研究工作的展望。 7 基- 丁遗传算法的公交智能排班方法研究 2 1 遗传算法概述 第2 章遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m s 简称g a ) 是人工智能的重要新分支。它是 模拟达尔文的遗传选择和自然淘汰、适者生存的生物进化过程的计算模型，是搜 索最优解的一种随机化的方法，也是根据适者生存，优胜劣汰等自然进化规则来 进行搜索计算和问题求解。遗传算法的概念最早是由j d b a g l e y 在1 9 6 7 年提出的， 由美国m i c h i g a n 大学的j h h o l l a n d 教授于1 9 7 5 年所实行，因此j h h o l l a n d 教授被 视作遗传算法的创始人，当时，其主要目的是说明自然和人工系统的自适应过程。 在一系列研究工作的基础上，8 0 年代经过美国亚拉巴马大学的d e g o l d b e r g 归纳 和总结，最终形成了遗传算法的基本框架。 遗传算法，在本质上是一种直接搜索方法，不依赖于具体问题和求解问题的 领域，同时也是一种高效的对求解问题进行并行全局搜索的方法，它在搜索过程 中探索解空间上的全局性最优解和利用己获得的解空间信息逼近当前局部最优 解。通过群体和遗传算子包括选择算子、交叉算子、变异算子可以实现扬弃性的 探索来克服局部极值陷阱和模式欺骗，并且实现整个解空间范围内的搜索，提高 全局寻优能力。通过维持群体的可进化性和继承性的开发，同时克服早熟问题， 实现邻域搜索，提高逼近搜索能力。在人工智能研究中，人们已经把遗传算法列 入了“对未来十年的计算技术及信息技术有重大影响的关键技术”中。 2 2 遗传算法的发展与现状 1 9 6 2 年，美国m i c h i g a n 大学的j h h o l l a n d 教授在研究适应系统时，意识到自 然进化现象、生物的遗传等，好像同人工智能的自适应系统有相似关系，经过仔 细研究，提出在研究系统本身同外部环境的相互作用与协调等人工自适应系统 时，能够借鉴生物的遗传机制，以群体的方式进行自适应搜索，这时就涉及到了 进化算法的思想。此后j h h o l a n d 指导学生完成了多篇博士论文，1 9 6 7 年，他的 学生j d b a g l e y 在博士论文中首次提出“遗传算法 一词，至l j 7 0 年代初，j h h o l l a n d 提出了“模式定理( s c h e m at h e o r e m ) ，从而奠定了遗传算法研究的理论基础。 1 9 7 5 年是遗传算法在研究发展历史上最重要的一年。j d h o l l a n d l 3 9j 教授出 版了他的著名专著自然系统和人工系统的适应性，该书比较全面地介绍了遗 传算法的思想，发展了一套模拟生物自适应的理论，这时遗传算法得到了正式的 承认。同年，d ej o n g 4 0 j 完成了博士论文 a na n a l y s i so ft h eb e h a v i o ro fac l a s so f 8 硕十学位沦文 g e n e t i ca d a p t i v es y s t e m ( 遗传自适应系统的行为分析) ，对遗传算法研究具 有指导意义。他深入领会了模式定理并把j h h o l l a n d 的模式理论与计算实验结合 起来，该论文结合模式定理进行了大量的严格的计算实验( 主要是纯数值优化实 验) ，进一步完善和系统化了选择、交叉和变异操作，给出了明确的结论：同时 又提出了新的遗传操作技术诸如代沟( g e n e r a t i o ng a p ) 等，在这个基础上进一步 发展，著名的d ej o n g 五函数测试平台就此建立了，定义了性能评价标准，并以 函数优化为例，详细的实验分析了遗传算法六种方案的性能及理论机理，他的工 作成为后继者的范例并为遗传算法以后的广泛应用奠定了坚定的基础。b e t h e k c 的博士论文提出了用w a s h 函数来研究g a 的方法；a l b e r t 大学的a b r i n d l e 4 1j 在博 士论文中对选择策略进行了研究。这一时期的研究成果主要是回答了g a 到底有 何意义，有何价值，由于他们的研究工作，很多人的注意力逐渐转向了g a 。 2 0 世纪8 0 年代中期以来是遗传算法的蓬勃发展时期。各种复杂系统的自适应 控制以及复杂的优化问题中都应用到了遗传算法。各学科学者对遗传算法应用有 了广泛的兴趣，遗传算法的理论研究更为深入，研究成果更为丰富。1 9 8 5 年在美 国卡耐基梅隆大学召开了第一届关于遗传算法及其应用的国际会议i c g a ( i n t e r n a t i o n a lc o n f e r e n c eg e n e t i ca l g o r i t h m s ) ，并且成立了国际遗传算法学会； 1 9 8 9 年，美国亚拉巴马大学的d e g o l d b e r g 4 z j 出版了g e n e t i ca l g o r i t h m si n s e a r c ho p t i m i z a t i o na n dm a c h i n el e a r n i n g ( 遗传算法在搜索、优化和机器学习中 的研究) ，系统地对遗传算法研究的主要成果进行了总结，对遗传算法及其应 用作了全面而系统的论述，奠定了现代遗传算法的科学基础；1 9 9 1 年， l d d a v i s 4 3 j 编辑出版了h a n d b o o ko fg e n e t i ca l g o r i t h m s ( 遗传算法手册) ， 该书全面论述了遗传算法的原理与应用，用一些实例说明了遗传算法在工程技术 领域、科学计算方面和社会经济生活中的应用，对遗传算法的应用进行推广和普 及起到了重要的指导作用；1 9 9 2 年，j r k o z a 4 4 j 在计算机程序的优化设计及自动 生成中，将遗传算法成功地应用其中，提出了遗传编程的概念，在人工智能、符 号处理、机器学习等方面都有其应用。 经过二十几年的努力，遗传算法不论是在应用研究上，算法设计上，还是在 基础理论上，均取得了长足的发展，而且在人工智能、信息科学、运筹学和应用 科学等诸多学科领域也成为了热点研究。 我国有关遗传算法方面的研究虽然起步比较晚，但一直处于不断上升的过 程。国内已经有许多学科及专业的学者对遗传算法进行了较深的研究，并发表了 多篇质量比较高、较有影响的综述性文章。1 9 9 5 年，武汉大学的刘勇及康立山等 人出版了非数值并行计算遗传算法文章，其单位武汉大学在并行演化计 算等方面进行了大量的深入研究【4 5 j ；中国科技大学的陈国良、王熙法，庄镇泉 等人【4 6 1 于1 9 9 6 年出版了遗传算法及其应用；肖勇、陈意云【4 7 1 提出了利用遗 9 基下遗传算法的公交钾能排班方法研究 曼曼曼蔓曼曼曼曼皇曼曼皇曼曼曼曼蔓皇曼曼曼曼_ mm_i 一。二 - - 曼 皇孽曼曼曼曼曼! 皇曼蔓曼曼寡 传算法构造决策树的方法；西北工业大学的周明、孙树栋【4 8 1 于1 9 9 9 年出版了遗 传算法原理及其应用；天津大学研究了如何评价遗传算法的性能和怎么使用遗 传算法求解约束优化问题；北京系统工程研究所、大庆石油学院的何新贵等人提 出一种改进适应度函数的遗传算法，在适应度函数中加入了函数在搜索点的变化 率的信息，使得染色体( 按概率进行选择的) 具有较大、较小的函数值( 对极小 化问题而言) 变化率，从而提高收敛速度。所有这些研究对国内学者进一步研究 及如何应用遗传算法起到了积极作用。特别是近几年，无论是理论研究还是应用 研究，都取得了许多成果，使我国在遗传算法研究上与国际处于同一水平线上。 2 3 遗传算法的基本思想 遗传算法是一种迭代算法，实质上是一种搜索寻优技术，它是从某一随机产 生的或者选定的、代表问题可能潜在解集的一个种群开始，按照一定的操作规则 借助于自然遗传学的选择、复制、交叉、变异等，逐代演化产生出越来越好 的近似解。在每一代，根据问题域中个体的适应度的大小，按照优胜劣汰和适者 生存的原理，引导搜索过程向最优解逼近，最终产生出代表新的解集的群体，可 以作为问题的近似最优解或满意解。 2 4 遗传算法的一些基本概念和术语 遗传算法与数学规划优化方法以及其它方法在原理、实现手段等方面有着明 显的区别，它是基于生物遗传进化思想和计算机科学相互结合渗透而成的一种新 的优化方法，所以在遗传算法中经常用到有关自然遗传进化中的一些基础用语， 下面给出遗传算法中常用的一些名词和基本概念，如下： ( 1 ) 演化代( g e n e r a t i o n ) 算法的迭代步称为演化代或代。 ( 2 ) 个体( i n d i v i d u a l ) 组成种群的每一个解称为一个个体，是遗传算法中用来模拟生物染色体的一 定数目的二进制位串，常记为噩，似，等。 ( 3 ) 种群( p o p u l a t i o n ) 是由一定数量的个体组成的集合，也是所求解问题的多个解的集合，常记 为尸俐，t 表示其代数，最初的种群即尸m j 。 ( 4 ) 种群规模( p o p u l a t i o ns i z e ) 指种群中包含的个体的数量，常记为。一般来说，群体规模在整个演化过 程中是不变的。 ( 5 ) 染色体( c h r o m o s o m e ) 1 0 硕十学位论文 经过编码后得到的代表问题的解的串。每个个体实际上是染色体带有特征的 实体。 ( 6 ) 位串( b i ts t r i n g ) 个体的表现形式，一般为二进制串。 ( 7 ) 基因( g e n e ) 染色体的每一位称为基因。 ( 8 ) 基因型( g e n o t y p e ) 染色体性状的内部表现，也即基因组合的模型，或者称为遗传子型。 ( 9 ) 表现型( p h e n o t y p e ) 染色体性状的外部表现。染色体作为遗传物质的主要载体，其基因型决定了 个体的表现型。 ( 1 0 ) 基因模式( g e n e r i cm o d e l ) 指在二进制位串中，某一或某些位置上的具有相似性的个体组成的集合。 ( 11 ) 适应度( f i t n e s s ) 个体适应环境的程度( 与最优解接近的程度) 。 ( 1 2 ) 平均适应度( m e a nf i t n e s s ) 指若干个个体的适应度值的算术平均值。 ( 1 3 ) 父代( p a r e n t ) 根据某种规则来产生其下一代个体的个体称为其下一代个体的父代。 ( 1 4 ) 子代( o f f s p r i n g ) 根据某种规则来产生的下代个体称为子代。 ( 1 5 ) 选择( s e l e c t i o n ) 以一定概率从种群中选出若干个体的操作。 ( 1 6 ) 复制( r e p r o d u c t i o n ) 在上一代种群中按照某些指标挑选出若干数量的个体直接插入到新一代种 群中去的操作。 ( 1 7 ) 交叉( c r o s s o v e r ) 指对优选后的父代个体进