（系统工程专业论文）基于GATS的公交驾驶员调度算法研究.pdf

中文摘要 摘要：随着世界各地城市现代化程度的提高，城市交通拥堵问题日益严重，发展 公共交通是解决这一问题的重要途径之一运营调度管理是公交企业的核心业务， 驾驶员调度作为公交调度管理中的重要组成部分。关系着整个调度计划的人员使 用效率和运营成本科学合理的调度方案可以减少运营成本，提高调度管理的效 率和水平 本文结合国内外驾驶员调度问题研究发展历史，综述了解决驾驶员调度问题 常用的研究方法，在对国内外驾驶员调度理论与模型进行分析的基础上，重点探 讨了遗传算法与禁忌搜索算法结合策略求解这一问题的数学模型与方法。禁忌搜 索与遗传算法结合策略( g a t s ) 综合了遗传算法具有多出发点和禁忌搜索的记忆 功能及爬山能力强的特点，主要用于初始解的改进的过程中最后根据北京公交 专线分公司线路时刻表的实际数据进行了实例分析实验结果证明国内现有的人 工编制的时刻表有很大的优化空间，本文采用的优化模型与算法对于提高人员效 率和车辆使用率有一定的帮助。 关键词：公共交通；驾驶员调度；启发式算法；g 期晤 a b s l l r a c i a b s t r a c t ：t r a f f i c p r o b l e m sa i d e t e r i o r a t i n gn k i ca n dm o r es e r i o u s l yb ( g ：a u s eo f t h eu r b a n i z a t i o ni nm a n yc i t i e so ft h ew o r l d o n eo ft h ei m p o r t a n tw a y st os o l v et h i s p r o b l e mi sd e v e l o p i n gp u b l i ct m 面c s c h e d u l i n gm a n a g e m e n ti st h ec o i cb u s i n e s so f t h eb u s c o m p a n i e s d r i v e rs c h e d u l i n gi sa l li m p o r t a n ts t e po fp u b l i ct r a f f i cs c h e d u l i n g , as c i e n t i f i cd r i v e rs c h e d u i m gs c h e m ec a l lr e d u c eo p e r a t i n gc o s t sa n di m p r o v et h e w h o l e e f f i c i e n c y o f p u b l i c t r a f f i c s c h e d u l i n 吕 t h et h e s i sf i r s te x p l a i n st h ed e f i n i t i o n so ft h ed r i v e rs c h e d u l i n gp r o b l e m t h e n t h ed e v e l o p m e n to ft h ed r i v e rs c h e d u l i n gp r o b l e mi si n t r o d u c e d f o l l o w i n gp a r to ft h e t h e s i sf o c u s e so ns o l v i n gt h ed r i v e rs c h e d u l i n gp r o b l e mu s i n gag a t sa p p r o a c h t h e g e n e t i ca l g o r i t h mc o m b i n e dw i t ht a b us e a r c hs t r a t e g y ( g a t s ) i n t e g r a t e dw i t h m u l t i p l eg e n e t i ca l g o r i t h ms t a r t i n gp o i n ta n dt a b us e a r c hm e m o r yf u n c t i o na n dt h e a b i l i t yt om o u n t a i n e e r i n gf e a t u r e s ，m a i n l yf o rt h ei m p r o v e m e n to ft h ei n i t i a ls o l u t i o n s i nt h ep r o c e s s a n da tl a s t , a ne x a m p l ei sg i v e nt op r o v et h ef e a s i b l eo ft h ea p p r o a c h t h er e s u l tc o n c l u d e st h a tt h ep r e s e n td r i v e rs c h e d u l eh a sm u c hs p a c et oi m p r o v e ，a n d ag o o ds c h e d u l ec a nd e c r e a s et h ed u t i e sn u m b e ra n dt h ec o s t k e y w o r d s ：p u b l i ct r a f f i c ；d r i v e rs c h e d u l i n g ；h e u r i s t i c a p p r o a c h ；g a t s 北塞銮通太翌亟茔位监塞图且丞 图目录 图3 - 1 标注换班地点的行车计划 图3 - 2 一辆车的行车计划 图3 - 3 驾驶员调度 图4 - 1 班次工作组成 图4 2 班次和行车计划之间的联系 图4 - 3 模型求解思路 图4 _ 4g 髑算法中的g a 和t s 的混合结构 图4 5 标准2 - o p t 交换链接图示 图 62 - o p t 交换链接图示( a ) 图4 72 - o p t 交换链接图示( b ) 图4 - 82 - o p t 交换链接图示( c ) 图4 - 9 交换链接 图4 1 0 将连续驾驶段转化为结束连续驾驶段 图4 - l l 交换连续驾驶段。 图4 - 1 2 重新划分行车计划 3 7 3 8 坫璩斟拍孔弭笱巧孙拍弘 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名；羔东讳 导师签名 签字日期：酌司年j l 月be l 主件 签字日期：仲，1 ，月7 e t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：孑薹舶书签字日期：2 护0 1 年72 - 月i 。日 致谢 本论文的工作是在我的导师关伟教授的悉心指导下完成的，关伟教授严谨的 治学态度和科学的工作方法给了我极大的帮助和影响，使我更加明白了如何发现 和解决问题，如何做人做事。在此衷心感谢多年来关伟老师对我的关心和指导 王喜富教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷 心的感谢。 马继辉老师一直都在科研项目和生活上给了我很多的指导和帮助，在此表示 衷心的感谢 纪寿文、毕军、朱广字老师悉心指导我完成了实验室的科研工作。在学习上 和生活上都给予了我很大的关心和帮助，在此向纪老师、毕老师、朱老师表示衷 心的谢意。 在实验室工作及撰写论文期间，付鹏威、陈石、何蜀燕j 刘惠玲、王均、马 江伟等同学对我论文中的研究工作给予了热情帮助，在此向他们表达我的感激之 情。 另外也感谢我的爸爸妈妈，他们的理解和支持使我能够在学校专心完成我的 学业。 引言 1 引言 1 1 研究背景 随着世界各地城市化程度的提高，城市交通拥堵问题目益严重，对资源、环 境的保护以及可持续发展都造成了很大的影响。多年的研究表明，建立先进的公 共交通系统，提高道路通行能力和公交车辆运营管理水平，是解决城市交通问题 的一个重要途径 而衡量公共交通系统管理水平的标准主要是其调度水平的高低国内目前的 公交企业大都采用手工方式编制调度计划，调度模式几乎全部采用单线路模式， 即以线路为运营组织单位，人员及车辆按线路固定配置，以线路为单位编制运营 调度计划，线路配车按线路最大断面确定，首末站驻车、管理，调度。这种以线 路为单位的单线路调度模式是一种小而散的调度模式，它不利于资源的有效利用， 造成各线路相互独立由于各线路均按最大断面配车，再加上车辆人员又是固定 配置，线路间人力、运力难以调剂互补，必然存在低峰闲置。此外，单线路调度 模式采用每条线路人员和车辆分散管理，导致管理人员、运营辅助人员偏多，占 用城市用地多，规划调整线路难度大，缺乏灵活性。驾驶人员人力资源不能够得 到充分利用，造成了人员和车辆的资源浪费。 公交调度计划编制一般分为四个主要的过程，分别是：路网线路设计，发车 频率设定和建立时刻表，车辆调度和驾驶员调度l 。驾驶员调度是公交调度计划编 制四步过程中重要的一步驾驶员调度利用行车计划信息，驾驶员的工作条例和 工作日的成本结构等作为输入的变量，通过一定优化方法，从而得到驾驶员的工 作安捧计划 公交驾驶员调度问题研究如何利用最少的驾驶员和最小的运营成本来完成公 交车辆的运营工作，这属于一个多目标规划问题，而且是一个n p 完全问题1 2 1 1 3 1 。 对公共交通驾驶员调度问题的研究可以大幅度提高驾驶员利用效率。进而给公共 交通企业带来巨大的经济效益，因此，已吸引了人们广泛的关注与兴趣 同时。驾驶员调度问题也是人员捧班问题，人员捧班问题一直是调度问题中 经常碰到的经典问题。国内外的许多文献已有不同程度的探讨与研究，它在学术 领域被定义是一个特定的数学规划问题在国内外许多学者的努力下，已有许多 不同的求解方法被应用于不同的人员排班问题，但综观所有的求解方法，基本上 北京交通大学硕士学位论文 仍然可以归为两大类： 第一类为最优化算法，在作法上通常将问题构建成集合涵盖( s e tc o v e r i n g ) 或集 合分割( s e tp a r t i t i o n i n g ) 模式求解，一般称这种方法为集合涵盖( 或集合分割) 法这 种方法并不能算为最优解法，因为在利用集合涵盖( 或分割) 问题求解时，除非能证 明所有的组合皆被考虑过，才有可能获得最优解由于捧班问题规模过于庞大， 要列出所有可能的组合需要很长时间。 第二类是启发式算法启发式算法是指寻求一种能产生可行解的启发式规则， 以找到一个最优解或近似解的方法。虽然此近似解并不一定为最优解，但却能大 大缩短求解时间，提高求解效率。故在处理大型的人员排班问题时，一般都采用 此类方法来进行求解关于应用于人员捧班方面的启发式算法有很多，如模拟退 火算法( s i m u l a t e da n 北a n n g ) 、遗传算法( c , e n e t i ca l g o r i t h m ) 、禁忌搜索算法f f a b u s e a r c h ) 等t * s 。 在国内关于公交调度的理论研究上，很多学者已经尝试使用各种启发式算法 进行求解，但是在利用计算机进行公共交通调度方法方面的研究与国外先进水平 还有较大差距同时，虽然国外已经成功地开发并应用了一些解决驾驶员调度问 题的软件，但是对于现有的模型方法并不能盲目的照搬到国内。国内外在管理模 式，调度方式等有着很大的不同，对于驾驶员调度问题的建模常常都是从实际调 度情况出发的。所以如何结合国内调度现状来分析驾驶员的调度问题是本文的目 的之一。 2 0 0 8 年奥运会即将在北京举行，届时面对世界各地的参赛者、游客等，要求 必须提供先进、合理、安全舒适的交通服务合理的调度方案从公交运营成本、 公交运营资源、人员工作效率以及乘客满意度都有十分重要的影响改进现有的 调度模式，提高公交运营效率，已经成为政府的迫切需求同时公交企业也希望 可以通过对调度问题的优化来完善管理，取得更好的经济效益 目前国内在驾驶员调度方面的研究都在探索阶段，许多成果都需要进一步的 研究本论文从驾驶员调度问题模型的建立到求解都进行了探索性的研究，希望 能在现有的研究成果上获得进一步的改进，对于国内公交行业的实际应用有所帮 助 1 2 论文结构和主要内容 根据研究内容，本文一共分为六章： 第一章是概述，主要介绍驾驶员调度问题的研究背景，文章的体系结构和主 2 引言 要内容； 第二章对驾驶员调度问题研究的发展进行综述，主要从驾驶员调度问题的研 究方法入手，介绍驾驶员调度的发展历程，以及现有的驾驶员调度系统等； 第三章将对驾驶员调度问题进行简述，主要描述驾驶员调度问题的基本概念， 驾驶员调度所要解决的问题，以及和行车计划，时刻表之间的联系，并且分析驾 驶员调度问题的复杂性； 第四章介绍启发式算法中遗传算法与禁忌搜索相结合的模型求解策略与方 法；然后根据驾驶员调度问题的主要因素和复杂性对驾驶员调度问题进行建模， 并且利用遗传算法与禁忌搜索相结合的方法来对驾驶员调度问题求解； 第五章为实例分析，利用北京市公交公司车辆线路数据检验模型与算法的适 用性； 第六章为得出的结论，将对全文进行总结，概括本文的主要工作，并对今后 研究驾驶员调度问题提出展望。 3 国内外研究的理论与方法综述 2 国内外研究的理论与方法综述 最早利用计算机进行驾驶员调度研究开始于上世纪年代，经过多年的发展， 形成了很多先进的成栗和应用软件，回顾整个发展过程，这些方法主要可以分为 两大类：启发式算法和数学规划方法这两种方法并不是互相排斥的，相反，数 学规划方法中经常用启发式方法来求解；在启发式方法中又需要者数学规划方法 来建模。 2 1国外研究状况 2 1 1早期的纯启发式算法 早期对公交驾驶员调度问题深入研究的主要有美国的e l i a s 6 n l 和英国利兹大 学的w e a v e s l 和w 渤【9 i 等人，当时的系统有相对成熟的t r a c s ( t c c h m q u ef o r r u n n i n g a u t o m a t i cc r e ws c h e d u l i n g ) ，和r u c u s ( r u nc u t t i n ga n ds c h e d u l n g ) ， 还有采用交互式的c o m p a c s ( c o m p u t e r a s s i s t e dq 哪s c h e d u l i n g ) 。解决方法采 用的是启发式方法，当时计算机的功能还不够强大，另外，数学规划设计者对驾 驶员调度问题的理解也不够成熟早期大多数基于启发式算法的驾驶员调度系统 生成时刻表的方法与当时人工捧班的方法很相似，对于调度计划的修改往往采取 人工和系统交互的方法，实际上对于调度计划的改进十分的有限 6 0 年代e l i a s 开始使用计算机来辅助人工编制驾驶员调度。当时e l i a s 的辅助 系统在美国使用很广泛，但是当时大多数的班次只取整班，司机一般连续工作8 小时，剩下的工作会组合成一项两个车辆的任务，在这些任务之间会有一个休息 的间隔，或者延长部分司机的任务，延长的任务当作加班时间来计算e l i a s 使用 启发式的方法，首先将车辆计划分成一个连续驾驶段的集合，然后在已经捌分的 连续驾驶段的基础上设计出所有可能的2 个连续驾驶段的班次，根据不同的开始 班次而建立不同的计划，输出花费最低的方案 这种方法是基于生成与选择的，包括产生一个可能班次的集合，然后在其中 选择一个可以成为解的子集在e l i a s 的方法中，班次产生的过程中只生成含有2 个连续驾驶段的班次班次选择的过程采用贪婪算法，并可以很快地得到解，但 是解的质量往往无法令人满足尽管e h a s 的调度系统只用于测试，但这种生成与 选择的思路对驾驶员调度问题的研究发展有很大的影响。 t r a c s 1 0 】系统是英国利兹大学在w e a v e r 和w r e n 的工作基础上研究出来的， 它包括一个初始程序和一系列优化程序，初始程序先生成一个好的初始解，优化 5 北京交通大学硕士学位论文 程序再对其进行改进改进的过程分为两条路线：一条是尝试减少班次或者是未 分配的连续驾驶段的数量，依次考虑每一个班次，确认其中的连续驾驶段可以在 其它班次中重新分配，含有较长连续工作时间的班次可以尽量延长；短的尽量缩 短，有可能的话最好完全被除去：降低未分配的连续驾驶段的长度。另外一条是 尝试减少整个时刻表的花费有许多的方法可以达到这个目标，其中一个是在用 餐时间把班次划分开，并且作为指派问题重新分配这些班次，另外一种方法就是 交换连续驾驶段来减少花费。t r a c s 系统应用的针对性比较强，所以对于一些特 定的要求，往往需要几个月研究来使启发式方法适用于新问题。 r u c u si l l 】是在7 0 年代早期在美国公交公司( t h eu s u r b a nm a s s t r a n s p o r t a t i o na d m i n i s t r a t i o n ) 资助下由m i t r e 公司设计的车辆和驾驶员调度系 统，从1 9 7 5 年起在美国和加拿大的许多公交公司开始使用这套系统 r u c u s 和t r a c s 有许多的相似之处，也是首先生成一个初始方案再利用启 发式方法来改进在生成初始解的过程中，r u c u s 首先生成只有一个连续驾驶段， 不含就餐时间的整班，然后形成对用餐时间有时问限制的含2 个连续驾驶段的早 班和晚班，以及对吃饭时间无限制的含2 个连续驾驶段的早班和晚班，最后将未 被分配的工作设计成简单的班次添加到时刻表中。 当形成初始解之后。许多改进算法开始应用于排除短小的班次，尽可能把它 们和2 个连续驾驶段的班次结合起来通过交换一对班次的连续驾驶段，或者调 整班次的换班机会( 换为前一个或者后一个) 来减少花费，这个算法被分别称为 交换和转换( s h i f t s & s w i t c h e s ) c o m p a c s l l 2 1 是一个商业公司在年代早期设计的交互式的系统。c o m p a c s 采用了一些1 1 氓c s 中的启发式算法来生成初始解，但是并未对其进行改进。 年代早期，它被合并进了b u s m a n 的调度系统包中c o m p a c s 作为一种交互式 系统，可以从多方面帮助调度者，允许调度人员在时刻表中一次添加一个或者更 多的班次；在不同的阶段，允许修改已经形戎的班次，c 0 m p a c s 也可以自动形 成一个时刻表，但是这个时刻表的因为缺少了改进的功能。所以质量一般都很差 i n l 启发式方法的系统在一些应用方面取得了成就，原因在于他们比较适用于独 立的公司，因此，它可以按照公司的需求进行设计尽管如此，这种系统还是需 要了解专业知识和公司的特殊焘求，系统的普适性较差，并且在面对新的环境和 用户时要进行相当大的修改直到年代，人们渐渐意识到单纯依靠启发式算法 无法很好的解决驾驶员调度问题的，所以纯启发式算法目前已经基本被淘汰了， 取而代之的是结合启发式算法的数学规划方法。 6 国内外研究的理论与方法综述 2 1 2中期的数学规划方法 在7 0 年代后期，数学规划方法开始流行起来现有的大多数的驾驶员调度系 统都建立在数学规划方法的基础上，其中驾驶员调度问题经常被建模成为一个集 覆盖或者集分割闯题在介绍集覆盖方法和其他整数规划方法的基础上主要介绍 三个系统：i m p a c s ( i n t e g e rm a t h e m a t i c a lp r o g r a m m i n gf o ra u t o m a t i cc r e w s c h e d u l i n g ) ，t r a c s h ( t e c h n i q u e sf o rr u n n i n ga u t o m a t i cc r e ws c h e d u l e s , m a r km 和h a s t u s 其中后两个是世界上比较成功的两个驾驶员调度系统，i m p a c s 系 统是t r a c si i 系统的前身。 2 1 2 1 数学规划方法 基于数学规划的公共交通驾驶员调度方法习惯被称为“生成与选择”模式， 但实际上并不是纯粹的整数规划方法这种模式主要包含两个阶段：“生成”和l “选择”其求解步骤如下：首先采用启发式方法依据劳动法规生成全部好”。 的驾驶班次，构成一个大的解元素集合；然后采用整数线性规划方法选择一个子 集，使该子集中的全部元素结合起来能够构成一个可行解( e p ，覆盖全部的车辆运氛 营工作1 ，同时j 要求这个解满足一定的目标函数，如；采用最少的驾驶班次，并 且，或者，具有最小的运营成本 生成一个有效班次集合是基于。生成与选择”模式的驾驶员调度方法的基础一 对一个实际问题，包含全部有效班次的集合通常太大以至于超出当前l p 的求解能 力因此，目前的做法是凭借经验仅仅生成。好”的班次，具体方法包括：增加 一系列的“软限制条件”与劳动法规共同制约班次的有效性，进面降低生成的有 效班次个数：利用启发式方法筛选掉部分换班时问点来缩小问题规模；利用启发 式方法进一步筛选掉己生成的但不太。好”的班次 在“选择”阶段最为关键的是建立一个合适的模型包含量段车辆工作( 两 个连续的换班时问点之问的工作称为。小驾驶段”) 和m 个有效班次的驾驶员调 度问题一般可以被模拟为如下一个集覆盖问题在优化的过程中需要考虑可行的 班次的集合及其成本集覆盖寻找一个覆盖所有车辆工作的班次集合，并且可行 解的成本最小集覆盖问题的数学描述如下i 堋： 7 北京交通大学硕士学位论文 眦荔6 满足约束条件。荟嘞1 - 1 ，册 善_ 酊 0 1 w 一1 ，厅 舯_ 警方案中班涨选中 1任务i 是班次j 的组成部分 0 否 q 与班次j 相关的成本 m所有驾驶任务的数量 n所有可行班次的数量 f班次数量的最大值 ( 2 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) 上述的目标方程( 2 1 ) 表示相关的班次的总成本的最小值，约束条件( 2 2 ) 保证了所有的工作可以被选择的班次所覆盖，约束条件( 2 3 ) 限制了班次的数量。 班次的可行性由任务的兼容情况和相关劳动条例规定。 假如约束条件( 2 2 ) 的不等式改成等式，那么这个问题就变成了集分割的问 题，表示所有的任务只能使用一次 2 1 二2 基于数学规划算法的系统 m m a c s 【1 5 l 系统是7 0 年代后期英国利兹大学研究的驾驶员调度系统。i m p a c s 的模型是基于集覆盖，由于变量和约束的数量很大的，i m p a c s 采用了启发式方 法，系统解决驾驶员调度问题增加一些软规贝l j ，例如：连续驾驶段的最短时间的 限制，最少工作容量的限制等；用启发式方法减少工作块的数量，使用优化的模 型e s t 和s 卫c t e s t 用于确定一个换班机会清单，s e i f _ l r 用于捧除可能不 会用到的换班机会，并且分析剩下的换班机会，从而减少工作块的数量；用启发 式方法依照劳动法规和软规则产生一个合法班次的集合，减少班次的数量，最后 用整数规魁方法来选择一个班次的子集。 t r a s h l l 6 1 从1 9 9 4 年开始被设计，主要是为了满足铁路调度的需求，同时依 然能够解决公共交通驾驶员调度的问题t r a s h 几乎和i m p a c s 的方法相同， 但是对组成部分进行大规模重新设计了以满足铁路调度的复杂性，并且也合并了 8 国内外研究的理论与方法综述 一些新的算法 t r a c s 包含三个阶段，第一个阶段为班次生成阶段，用于建立所有可能的 班次；第二个阶段主要对班次进行进一步的处理，将产生的班次进行排序，并且 筛选掉差的班次；第三阶段是主要累网算法对问题进行求解。 t r a c s 已经在许多公司成功的使用了，由于采用了集覆盖模型，调度方案 中会产生交叠的驾驶工作，可能会造成司机的非生产性的时问，这个问题通常在 调度计划施行之前人工的进行捧除 h a s t u s s t i 是一个商用软件包，可以用于解决与调度相关的问题：车辆调 度，驾驶员调度，轮班表的编制，它最早是由蒙特利尔大学在7 0 年代开发的，随 后与加拿大的g i r o 公司一同开发 h a s t u s 中的驾驶员调度问题使用c r e w - o p t 的方法，并且被广泛的应用， 包括一家铁路公司，这种方法采用集覆盖( 或者集分割) 方法并且结合了列生成 方法。 和t r a c s i i 耀同，这个系统采用基于整数线性规划的方法，也是从生成的 班次的集合里选择合适的子集，不同点是后者不生成所有的可能的班次，取而代 之的是一组。好的”班次的集合在得到每一个问题的l p 解之后，双重变量将会 用于产生新的班次，包含减少的花费，且会改进l p 闯题的解。h a s t u s 中的列生 成法用于生成新的班次列，而t r a c s 中则是用于在已经生成的集合里选择新的班 次列。 尽管使用了列生成法，劳动法规依然用于过滤变量来除去不合适的换班机会 和限制可行班次的集合的大小，这些变量在调度过程中会指导班次的生成列生 成的过程很有可能在新的约束条件下无法生成班次，因为这是基于松弛线性规划 的。这个方法解决了许多l p 问题，有些问题不可能找到可行的解来满足它的标准 整个计算过程是十分耗时的 结合启发式算法的数学规划方法不能保证获得最优解，方法的酱适性较纯启 发式算法好，但是有时候还是需要调整，而且这种调整的工作量有时相当的大； 约束条件经常被用于防止生成过大的班次集合，所以最优解有可能会受影响，约 束规则的参数化的操作可能会对不了解模型的调度员造成困难：如果采用比较松 弛的调度靓则交量，则产生所有可行的班次的过程将会非常耗时；对闯题规模的 缩减和方案产生过程的缩减是无法避免的；对于特定问题在特定的时间内无法得 到可行解。 9 北京交通大学硕士学位论文 2 1 3目前的元启发式算法( m e t a h e u r i s t i c ) 进入年代以来，为了克服数学规划方法的局限性，当数学方法继续发展的 同时，一系列新的研究方法应运面生，其中，元启发式方法( 主要包括：禁忌搜 索、模拟退火和遗传算法等) 和约束规划方法( 均被归属于人工智能方法) 较为 活跃，它们试图能够处理更大规模的实际问题。但时至今日，用于解决公交调度 计划问题的人工智能方法大部分仍然同数学规划方法一样将调度计划问题模型为 集合覆盖或集合切分问题也就是说，他们仍然延续着数学规划方法中的“生成 与选择”模式，即，首先生成一个大的解元素集合，然后，从中选择一个子集， 这个子集中全部元素结合起来要求能够构成一个可行解，同时，要求这个解要满 足一定的目标函数，如：具有最小的成本这些采用了“生成与选择”模式的新 型的人工智能方法虽然求解速度可能会快于p 方法，并且被期望可以处理更大 规模的问题。但是，他们仍然需要借助人为的“软限制参数”来限制问题的规模， 调度员难以掌握这些参数的选择的问题仍然未被解决 2 1 3 1 遗传算法 遗传算法( g e n e t i c a l g o r i t h m ) 是由美国m i c h i g a n 大学的j o h nh o l l a n d 教授等 人于1 9 7 5 年首先提出来的，遗传算法的基本架构来自达尔文的进化论，经由基因 的编码、复制、交叉，变异、取代来达到进化的目的l 培1 b e a s l e yj e 在使用遗传算法解决驾驶员调度问题时，首先将问题建立成一个集 覆盖的模型，集覆盖问题可以表示为一个m * h 的0 - 1 矩阵，以行来代表求解的单 位值，也就是为可行班次的集合而列表示每行所包含的属性，也就是所有的连 续驾驶段集合目标主要在求解能以最少的行数即包含所有的属性采用两种方 式来表示： 以行来表示染色体染色体长度即为可行班次的集合，采用0 - 1 编码方式，基 因o 表示班次没有包含在调度计划内，基因1 表示班次包含在调度方案中因此， 每一个染色体表示一个可行的驾驶员调度方案 以列来表示染色体采用自然数编码方式，基因位置有值表示这个连续驾驶 段出现在哪些班次上 如此随机性的编码会产生不合理的解，有两种改进方式，一为在目标式中加 入一惩罚值，或者用启发式算法来排除不合理的解。 交叉方法主要有两种，单点交叉法和制式交叉法，制式交叉法为一种常见的 机制，方法是先随即产生一个0 - 1 交叉模组，其长度与染色体相同，当该点的模组 国内外研究的理论与方法综述 值为0 则遗传父代染色体的基因值，若为l 则遗传母代的基因值，此做法一次只 能产生一个子代 变异方面，遗传算法在刚开始阶段为了让进化朝着好的方向走，所以变异率 不宜太高，但随着遗传算法演算逐渐达到收敛时。为了避免其落入局部解中，可 以给予其较高的变异率，使较差的个体中优良的基因有表现的机会，所以可以使 用变动的变异率，也就是随着进化代数的增加，其变异率也相对的提高，但是不 能超过一个上限值 在使用遗传算法求解驾驶员调度问题的时候，基本上还是套用数学规划方法 中的模型，只是在具体求解方法上有所不同 2 1 , 3 2 禁忌搜索算法 禁忌搜索( t a b us e a r c h 或t a b o os e a r c h ，简称t s ) 的思想最早在1 9 8 6 年由 g l o v e r 提出【删，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是 对人类智力过程的一种模拟。t s 算法通过引入一个灵活的存储结构和相应的禁忌 准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证 多样化的有效探索以最终实现全局优化相对于遗传算法；t s 是又一种搜索特点 不同的元启发式( m e t a - h e u r i s a c ) 算法。迄今为止，t s 算法在组合优化、生产调 度：机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数 全局优化方面得到较多的研究，并大有发展的趋势禁忌搜索基本工作原理是由 禁忌表中记录一些过去的搜寻轨迹( m o v e ) ，每次搜寻策略必须先与此禁忌表比较， 因此可避免循环解的产生此外由于每次搜寻到的解并不定比前解为佳，医 此必须另行记录个到目前为止的最优解，作为搜寻结束后的解答 禁忌搜索的演算程序里有两个重要的机制， ( 1 ) 禁忌表结构的设计，禁忌表所储存的资料是最近几次的解集，记录的信 息越完整则必须花费更多的时闯于评估上，但若仅记录部分信息将造成无法完全 掌握解答的相关资讯，而使评估结果产生误差； ( 2 ) 交换机制的应用，透过交换机制的控制，可以跳脱禁忌的限制，也就是 当解答为禁忌解时，将此解的目标值与至今最优解做一比较，若能改进，则豁免 此解的禁忌状态 在使用禁忌搜索算法求解驾驶员调度闯题的时候，由于算法的局限性无法较 好的获得全局最优解 1 1 北京交通大学硕士学位论文 2 2 国内研究状况 2 2 1驾驶员调度现状 驾驶员调度这项工作在国内更蠡地被称为编排劳动班次( 又叫劳动配班) 国 内公交线路上运行的车辆是连续周转的单车作业每个车组的运行时间，各个时 间配备的车辆数都不同，以司售人员组成的班组则要相应配备出不同时间、峰次 的劳动班型、配班数，指导每个司售人员在不同时间和班次去完成运营任务。整 体的运营组织依托行车时刻表和劳动配班进行运作。同时劳动配班以行车时刻表 为依托，行车时刻表又以它来实施，两者相互配合同时进行。 国内的公交企业大都采用手工方式编制调度计划，调度模式几乎全部采用单 线路模式，即以线路为运营组织单位，人员及车辆按线路固定配置，以线路为单 位编制运营调度计划，线路配车按线路最大断面确定，首末站驻车、管理、调度 这种以线路为单位的单线路调度模式不利于资源的有效利用，造成各线路相互独 立。和应用情况相对应，国内关于调度计划的研究模式基本都是：针对单一线路， 运用统计学方法，建立客流分析模型，求得发车时问间隔，以此确定调度计划。 基于单线路调度的调度计划研究，从公交企业的应用实践来看，调度计划计算机 编制与手工编织相比优化的效果非常有限，不能满足公交企业的实际需求。 2 2 2研究状况 早期的相关研究主要集中在调度模式的模型研究上，1 9 8 5 年，蒋光震、何 显慈在公共交通线路组合调度模型) 一文中，介绍了基于乘客分布的公交线路 静态区间调度模型例。1 9 8 8 年，张席渊瞄】在硕士论文公交调度系统分析、建模 与优化 中，针对公交调度优化闯题进行了探索性研究1 9 9 5 年，同济大学陈继 军结合上海市。8 5 攻关项目公交动态调度系统研究”，对调度理论和调度系统设计 进行了详细研究阎1 9 9 8 年，西安公路交通大学孙荚灵依据西安市部分公交客流 调查数据，探讨了几种确定发车间隔的方法闭 这个时期的研究都停留在智能交通系统整体框架和公交调度的理论认识阶 段，对驾驶员调度问题模型与算法的探讨还很少不过此时已经有了较多的调度 时刻表编制的探索研究的目标也是为了单线各时段的发车密度满足客流需求， 也就是对发车密度和间隔的优化 随着发车间隔模型和算法的不断成熟，对公交驾驶员调度模型和算法的研究 有了进一步的深入。 国内外研究的理论与方法综述 北京航空航天大学张飞舟州对公交车辆智能调度及相关技术进行了研究，提 出了运用遗传算法和混合遗传算法优化车辆调度的方法。对于遗传算法的应用与 国外相关研究的方法类似，也是将问题建立成一个集覆盖的模型。集覆盖问题可 以表示为一个m * n 的0 - i 矩阵，以行来代表求解的单位值，也就是为可行班次的集 合 沈吟东瞵】等近年来对公共交通驾驶员调度问题进行了描述，指出构成其复杂 性的影响因素，对驾驶员调度方法进行了简要评述对基于整数规划的方法进行 了分析，评价其求解模式、数学模型并指出其存在的局限性。最后还指出对于我 国研究者，应结合国内实际情况，从融合多种人工智能方法、“构造式”的超启发 式方法两个方向，来对驾驶员调度问题进行深入研究。2 0 0 5 年又对基于整数规划 的t r a c si i 系统的整数规划模型和求解方法进行分析，并指出其局限性以及进一 步研究公交驾驶员调度问题的方向 2 0 0 6 年，张斐型矧结合我国实际对驾驶员调度问题进行了详细分析，并进行 了模型设计，尝试使用禁忌搜索算法求解。采用邻域搜索技术主要用在对初始 解的改进过程中最后进行实例分析，利用北京市公交公司车辆线路( 3 2 7 路与 3 8 5 路) 的数据对所设计的模型与算法进行了检验 2 3 本章小结 在对驾驶员调度问题的回顾中发现，早期的启发式方法解决驾驶员调度问题 常常通过模拟人工调度的方法而不是建立通用模型；现有比较成功的驾驶员调度 系统是基于整数规划的在生成与选择的方法中，人工限制经常强加于不同的阶 段来控制问题的大小和搜索范围的大小因为，一个好的启发式方法能减少对专 业知识的依赖和不依靠人工限制，这使得建立模型成为了可能，这个模型更贴近 实际问题，因此有机会得到一个更好的解随着元启发式算法的不断发展，越来 越多的研究者尝试使用遗传算法、禁忌搜索算法来解决驾驶员调度问题，取得了 不错的效果。所以本论文希望可以结合国内公交调度的具体情况，在公交劳动配 班问题上做出进一步的理论性探索，利用禁忌搜索与遗传算法相结合的策略对驾 驶员调度问题进行模型与算法的探索 公交驾驶员调度目题分析 3 公交驾驶员调度问题分析 公交调度计划问题是公交企业运营的核心问题之一。公交企业的主体资源有 三大类：一是作为工具的运营车辆；二是作为工具使用者的驾驶员；三是作为营 运平台的线路和站场；调度计划就是在一定的限制条件下，合理配置各项不同特 性和数量的资源，来最大限度地满足特定的调度和管理目标。简单地说，就是安 排由哪一位驾驶员负责哪一台车辆在哪一条线路上如何行驶，每一个资源单位都 必须做好安捧和计划，然后交与相关调度执行人员和驾驶员执行，同时向公众公 布乘车时刻表 调度作业是整个公交公司运作的核心内容，调度作业可以分成两大部分：制 定作业计划以及实施作业计划；其中作业计划是整个公交公司资源运作的基本指 导作业计划的制订也就是调度计划编铡，主要分为：路网规划设计、时刻表的 生成、车辆调度和驾驶员调度其中，驾驶员调度是重要的组成部分，对于调度 过程中的人员优化有十分重要的作用。公交调度过程如下：首先设计路网，确定 公交线路的时刻表。然后进行车辆调度，最后进行驾驶员调度工作驾驶员调度 就是安捧一组驾驶员来完成一日内的全部车辆运营工作。调度计划是公交运营的 核心和先导，公交企业的资源的运作效率主要是在这一环节体现出来唧 3 1公交驾驶员调度的相关概念 驾驶员调度是一个极为复杂的组合优化问题，因为它需要同时满足如下条件： 司机一天的工作一般是由一辆车或者几辆车的几段工作构成的，同时运营车辆所 有的工作必须包含到司机的工作中，也就是说，所有司机的工作集合应该覆盖运 营车辆的任务嘲为了能够更清楚地表达公交驾驶员调度问题，需要了解一些基本 概念。 3 1 1行车计划与发车类型 行车计划是运营车辆有序的工作计划( 发车时刻表) 一个行车计划包含了一 条线路在一天内有次序地进行车辆调度的时刻表，参与运营的车辆从驶出车场开 始，到驶回同一个车场结束一个行车计划是多辆车辆发车情况的集合发车情 况一般分三种： 正常发车：车辆由线路首站或者耒站发车，载客运营，到达对端站，这种发 北京交通大学硕士学位论文 车类型称为正常发车； 空驶发车：车辆由车场驶出到达线路开始运营，以及结束运营工作后驶回车 场的过程中，一般不载客，称为。空驶”； 区间发车：车辆由首站或者末站发出后，载客运营，未到达对端站就返回， 称为区间发车； 表3 - 1 是一辆车的行车计划示例，其中停站时间表示运营车辆在到达停站点之 后，开始下一段工作之前，在停站点允许的停留时间，其中包含了三种发车类型 表3 - 1 行车计划表示例 b l o c kl ：行车计划1 ： 班次：1 从场站a 出发=0 5 ：3 1 地点到达时间 出发时问停站时间 a0 5 ：3 1 b0 6 ：0 30 6 ：0 7：4 a0 6 ：4 60 6 ：5 9：1 3 b 0 7 ：3 30 7 ：3 7 ：4 a0 8 ：2 30 8 2 6 ：3 c 0 8 ：5 4 鹏：5 5：1 a 0 9 3 30 9 ：4 2 ：9 c 1 0 ：1 01 0 ：1 1 ：1 a 1 0 ：4 6 1 0 ：5 6：1 0 b 1 1 ：3 2 l l ：3 7 5 a1 2 ：2 11 2 ：2 7：6 c1 2 ：5 51 2 ：5 6；1 a1 3 ：3 11 3 ：3 6 区间；5 a 1 4 ：0 01 4 ：0 5 ：5 a 1 5 ：0 1 1 5 ：1 2：1 1 c 1 5 ：4 0 1 5 ：4 1l1 a1 6 ：2 11 6 ：2 7：6 c 1 6 ：5 51 6 ；5 6i1 a1 7 ：3 61 7 ：3 6：o b 1 8 ：1 2 1 8 ：1 7；5 a 1 8 ：5 91 9 ：1 6 ：1 7 公交驾驶员调度问题分析 b 1 9 ：4 81 9 ：5 3；5 a2 0 ：3 2 2 0 3 5 ：3 c 2 0 5 42 0 5 5l1 a 2 1 ：2 02 1 ：3 5：1 5 c 2 1 ：5 4 2 1 ：5 5 ：1 a 2 2 ：2 0 2 2 ：3 5：1 5 c 2 2 ：s 4 2 2 ：5 5 ：1 a 2 3 ：2 02 3 ：2 0 空驶：4 d 2 3 ：2 42 3 ；2 5：1 e2 3 ：5 52 4 ：0 0：5 d2 4 ：3 22 4 ：3 2 空驶：4 a2 4 ：3 6 回到场站a2 4 ：3 6 3 1 2班次与班次类型 班次( s h i f i ) ，表示驾驶员完成一天的计划运营工作，从一个场站签到开始到 在同一个场站签退为止；一个驾驶员按照计划完成运营时间和运营公里称为一个 班次。 在班时间( s p r e m l o v e r ) ：从签到开始到签退结束的时间段，也就是一个班次 的工作时间 班次类型( s h i f t t y p e ) 实际运营中，公交车辆的班次有许多类型，在本文中， 主要考虑两个主要的类型：单班和整班( 日常班) ，单班一般比标准的工作时间要 长，1 2 小时或者以上，中间会有一个很长的休息时间整班又可以按照班次的时 间分为不同的类型具体可以分为早班，晚班，日班等表3 - 2 列出了各种班次类 型的定义： 表3 - 2 班次类型 单班单班：分多次上班( 一般两次) ，上班覆盖时间长，中间有休息时间； 班 早班( a ) ：覆盖早高峰； 晚班( b ) ：覆盖晚高峰； 次整班 日班( c ) ：周末早高峰后移，晚高峰前移，日班可以覆盖两个高峰； 小驾驶段：只包含一个小驾驶段的班次，一般为加班； 1 7 北京交通大学硕士学位论文 无用餐时间班次：包含两个以上小驾驶段，但是不包含就餐时间的班 次，一般为加班； 3 1 3驾驶员换班 换班( r e l i e f ) ：驾驶员完成自己的班次计划后，在下班时间与前来上班的驾 驶员进行工作的交接称为换班； 换班地点( r e l i e fs t a t i o n )