（计算机软件与理论专业论文）智能公交之车辆人员排班算法的研究与应用.pdf

山东大学硕士学位论文 摘要 车辆人员排班( 公交静态调度) 的主要问题就是在给定时间点和车次数的情况 下，以最小代价覆盖所有的车次。同时还要根据相关的法律规定满足工作人员的 最大最小工作时间。 。 目前对于该问题的研究基本上都是针对单类型车辆的人员排班，且多以使用的 车辆数与驾驶员数最少为目标。而由于我们的应用所处地区、当地的法规以及长 期以来形成的管理模式要求我们必须提供对多类型的车辆人员排班的支持。本文 在对公交业务以及车辆人员排班进行了大量的研究后，主要完成了以下工作： 一、 根据实际的营运管理模式建立以每日车辆整体营运时间最短为目标函 数( 也就是代价最小) ，以工作人员的工作时间以及车辆的停战问隔均匀 为约束条件的数学模型。 二、 为了解决多类型车辆人员排班，我们提出了两阶段求解算法。首先通 过利用高效的a u c t i o n 算法获取代价最小的车次分组并根据分组情况分配 车辆的营运类型；然后。使用遗传算法进行随机化搜索以获得最优解。 a u c t i o n 算法在前期的应用中主要是用于单类型的车辆排班，将a u c t i o n 算法引入人员排班，大大提高了求解效率。 三、 虽然a u c t i o n 算法能够获取使用车辆数最少代价最小的车次分组，但 由于在我们的应用中存在间断性任务，因此a u c t i o n 算法此时生成的分组 已不能满足使用车辆数最少的要求。为此，我们对a u c t i o n 算法进行了改 进添加了对问断性任务的支持。 四、由于遗传算法已为人们提供了求解问题的基本框架，因此对于遗传算 法的研究主要是集中在对编码方式、适应度函数以及各类操作算子的具体 实现上。在我们的应用中，我们提出了一种全新的编码方式采样编码，以 及与该编码对应的动态双点交叉算子和对偶变异算子采样编码能够满足 评估编码策略常采用的3 个规范得要求，而且具有以下特点： ( 1 ) 编码简单且所需存储空间较小，一般可为完全编码的十几甚至是二十 几分之一； ( 2 ) 映射策略简单使得选择，交叉、变异等操作算子运算非常容易； 山东大学硕士学位论文 ( 3 ) 能够有效的分割整个问题的搜索空间，提高在各个空丑】中的求解效率； ( 4 ) 采样编码将一个多类型的排班问题转化为单类型排班问题，从而使得 我们可以利用改进后的a u c t i o n 算法结合回溯算法求解问题。 五、在借鉴了遗传算法中变异算子的思想后，我们提出了一种贪心变异方 法结合采样编码来抽取单班车的组合排列方式。该方法有效保证了遗传算 法搜索空间的完备性。 关键字：车辆人员排班；采样编码；集合分割：遗传算法；竞标算法 山东大学硕士学位论文 a b s tr a c t t h ev e h i c l ea n dc r e ws c h e d u l i n gp r o b l e m ( v c s p ) i st h ef o l l o w i n g ：百v 即as c to f s e r v i c er e q u i r e m e n t so rt r i p sw i t h i naf i x e dp l a n n i n gh o r i z o n ，f i n dam i n i m u mc o s t 。 s c h e d u l ef o rv e h i c l e sa n dt h ec r e w s s u c ht h a tb o t l lt h ev e h i c l ea n dt h ec r e ws c h e d u l e a r ef e a s i b l ea n dm u t u a l l yc o m p a t i b l e a tp r e s e n t ，a l lr e s e a r c ho nt h i sq u e s t i o na i m sa ts i n g l et y p ev e h i c l e sa n dc r e w s c h e d u l i n g ( s v c s p lw i t ht h el e a s tu s eo fv e h i c l e sa n dc r e w b u tw i mr e g a r dt ot h e l o c a ll a w sa n dr e g u l a t i o n s ，o u ra p p l i c a t i o nm u s ts u p p o r tm u l t i t y p ev e h i c l e sa n dc r e w v s c h e d u l i n g ( m v c s n i nt h i sp a p e r , w ew o r k e da sf o l l o w s ： f i r s t ，w ee s t a b l i s ht h em a t h e m a t i c a lm o d e lf o rm u l t i - t y p ev e h i c l e sa n dg r e w s c h e d u l i n gw i t ht h eo b j e c t i v eo f s h o r t e s tn m n i n gt i m e s e c o n d , w ep r o p o s ea 柳o - p h a s ea l g o r i t h mt os o l v et h ep r o b l e m w eu t i l i z et h e m o d i f i e da u c t i o na l g o r i t h mw h i c hw a su s u a l l yu s e df o rs o l v i n gs i n g l e - t y p ev e h i c l e s s c h e d u l i n gb e f o r et og e tt h em i n i m u mc o s ts e q u e n c eg r o u p sa n da r r a n g et h eb u s s c h e d u l i n gt y p e , a n dt h e nw eu s et h er a n d o m i z a t i o ns e a r c ho fg e n e t i ca l g o r i t h mt og e t t h eo p t i m i z e ds o l u t i o n t h i r d ，t h ea u c t i o na l g o r i t h mc a l lg e tt h em i n i m u mn u m b e ro fv e h i c l e sa n dc o s t s s e q u e n c eg r o u p s b u tb e c a u s eo f t h ed i s c o n t i n u o u sd u t yi no u ra p p l i c a t i o n , t h ea u c t i o n a l g o r i t h mc a nn o tp r o d u c e st h em i n i m u mn u m b e ro fv e h i c l e si n0 1 1 1 n e wc o n s t r a i n t s t h e r e f o r e , w em a d et h ei m p r o v e m e n to ft h ea u c t i o na l g o r i t h mt os u p p o r tt h e d i s c o n t i n u o u sd u t y f o u r t h , b e c a u s et h eg e n e t i ca l g o r i t h mh a sp r o v i d e dt h eu n i v m a lm o d e la n df r a m e ， t h e r e f o r er e s e a r c ho ng e n e t i ca l g o r i t h mi sm a i n l yc o n c e n t r a t e so ne n c o d i n gm e t h o d ， f i t n e s sf u n c t i o na sw e l la so t h e rk i n d so fo p e r a t i o no p e r a t o r i no u r sa p p l i c a t i o n , w e p r o p o s e dan o v e le n c o d i n gm e t h o d ：s a m p l ec o d e ，a sw e l la sd y n a m i ct w o p o i n t c r o s s o v e ro p e r a t o ra n dd u a ls i m p l em u t a t i o no p e r a t o r o u rs a m p l ec o d ec a l ls a t i s f y t h e3s t a n d a r d sf o rc o d es t r a t e g ya p p r a i s a l m o r e o v e ri th a st h ef o l l o w i n gc h a r a c t e r i s t i c ： ( 1 ) s a m p l ec o d en e e d ss m a l l e rs t o r a g es p a c e s ，u s u a l l y 10 一2 0 o ft h e c o m p l e t e l ye n c o d e dm e t h o d s ； ( 2 ) w i t hs i m p l em a ps t r a t e g y , s a m p l ec o d em a k e st h es e l e c t i o n ，c r o s s o v e ra n d m u t a t i o no p e r a t i o ne a s i e rt oc a r r yo u t ； 山东大学硕士学位论文 ( 3 ) s a m p l ec o d ec a ns p l i tt h ew h o l es e a r c hs p a c ee f f e c t i v e l ya n dt h e n 耐l a n c c s e a r c he f f i c i e n c y ； ( 4 ) s a m p l ec o d et r a n s f o r m st h em u l t i t y p ev e h i c l ea n dc r e ws c h e d u l i n gp r o b l e mt o s i n g l e - t y p ev e h i c l ea n d c r e o vs c h e d u f f n gp r o b l e m s ow ec a nu t i l i z et h ee x i s t e dm e t h o d t or e s o l v et h eq u e s t i o n f i f t h , a c c o r d i n gt o t h em u t a t i o no p e r a t i o no fg e n e t i ca l g o r i t h m ，w ep r o p o s e da n o v e lg r e e d ym u t a t i o nm e t h o dt oe x t r a c tt h es i n g l eb u ss c h e d u l i n g t h i sm e t h o dh a s e f f e c t i v e l yg u a r a n t e e dt h ec o m p l e t e n e s so f t h ea l g o r i t h m ss e a r c hs p a c e s k e y w o r d ：v o s p ：s a m p i ec o d e ：s e ts p ii t ：g e n e t i 0a i g o r i t h m ；a u c t i o n 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：至堑塑堡日期：鲨型：笪 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：乏盘盗鹜导师签名：日期：迦生：坠 山东大学硕士学位论文 1 1 研究背景 第1 章绪论 随着中国经济的迅速发展，城市规模不断扩大以及人们财富的增长，使得私家 车数量不断增多。然而随着中国汽车工业的不断成长，私家车数量的与日俱增， 这不但增加了对能源的消耗和对空气的污染，同时给公共交通带来了巨大的压力。 我们必须及时采取措施来避免其他国家所犯的错误，大力发展公共交通能够有效 缓解这一社会问题，而且这也是众多发达资本主义国家目前采取的主要措施。 以2 0 0 8 年奥运会为契机，以北京、上海、青岛、大连、中山、内蒙为代表的 几大城市先后进入智能交通系统1 的建设阶段，中国公共交通事业迅速发展。新 的管理方式将改交人们对交通工具的认识，也将改变人们的生活工作方式。在智 能公交系统建设前的所有繁琐复杂的手工操作将由计算机代替，同时也将为乘客 提供更高质量的服务与便利。 我们的研究以青岛、内蒙、中山智能公交系统的建设为背景，本文的研究将主 要解决公交系统的车辆人员排班闯题，也可以称为公交静态调度口0 1 问题。排班包 括两大部分：一是生成行车时刻表，二是针对已生成的行车时刻表进行车辆人员 排班。行车时刻表的生成也是一个非常复杂的问题，在我们的应用中该表由公交 公司相关人员提供。 车辆人员排班的最终目的是生成一份行车计划。行车计划是组织线路运营的具 体作业计划，它将指导各个车组运营生产的全过程。它也为提高公共交通的整体 服务水平提供了有力的依据。好的行车计划将大大提高对乘客的服务质量，使乘 客对公共交通感到方便而且便捷。从而吸引更多的人乘坐公共交通，这既会解决 大量的客流转移对城市交通造成的压力，减少全社会的能源消耗，同时也会增加 公交公司的营运收入。此外，由于车辆人员排班是项非常复杂的工作，如果通 过手工来排。一位非常有经验的管理人员也要花费三到五天的时间才能完成。而 且由于排班计划完全有人工方式完成所以很难印证其j 下确性和有效性。因此由人 工方式完成的车辆排班表也就成了一个摆饰，很难在调度人员的同常工作中起到 非常有意义的指导作用。通过我们的研究实现自动排班将大大缩短这一工作的时 山东大学硕士学位论文 间，简化工作人员的劳动复杂度，提高劳动效率并使得行车计划真正成为调度人 员每日工作的参考指南。此外传统的排班方式耗时长有效性低，很难适应突发事 件或者是那些需要快速或是临时修改计划的情形。而通过我们的自动排班可以快 速有效的解决这一问题，满足乘客需要。 1 2 文献综述 车辆人员排班作为城市运输领域一个经典的n p h a r d 问题受到国内外大量专 家学者的重视和研究。 从建模的角度来说，它已被抽象为多种模型。包括有运输模型，任务分配模型， 最小代价流模型、q u a s l 分配模型、配对模型等。其中最小代价流模型、q u a s l 分 配模型是比较有代表性而且应用也比较多的模型。 从算法的目标函数来说，则主要可以分为两大类： ( i ) 使用车辆数与驾驶员数最少，代价最小 ( 2 ) 加减车间隔均匀嘲 目标函数( 1 ) 主要从利润最大化的角度出发，生成具有最小代价的行车计划。 代价的计算主要分为固定成本( 例如车辆、驾驶员等) 、变动成本( 例如燃油等) 两 部分，因此其固定费用的计算与利润最大化目标的实现需要满足一定的约束条件。 目标函数( 2 ) 主要是从加减车均匀有序、驾驶员工作时间平等性出发，均匀原 则使得在高低峰之间调整发车间隔时使得驾驶员不必突然长时间等待( 等待时间 也将计算为工作时间) ，它采取了一种循序渐进的策略使得商低峰之间的过渡比较 平滑。但它对代价的考虑则少了些，只是使用了简单的算法来确定使用车辆的数 量。虽然如此，但在固定了某些前提条件的情况下。其所使用的车辆数与目标函 数一所产生的车辆数并无很大差距， 1 2 中使用了该方法。 从算法实现本身来说，其使用的技术则更是多种多样，包括分支定价、集合分 割、线性规划、遗传算法以及启发式算法等。下面则是一些成功案例中所使用的 算法与技术： 文献 1 系统描述了a u c t i o n 算法的基本原理以及一些可用的变体。并对 a u c t i o n 算法的s s c a l i n g 增量进行了全面的证明。 文献 2 】概述了使用a u c t i o n 算法求解线性运输问题的基本方法。其基本思想 2 山东大学硕士学位论文 就是首先将交通运输问题转换为分配问题，构建整数线性规划模型，然后通过对 a u c t i o n 算法进行适当变形来求解该模型。 文献 3 3 通过使用双向的a u c t i o n 算法提高了a u c t i o n 算法的求解效率与质量， 文献 4 则利用了a u c t i o n 算法的并行性进一步提高了算法的求解效率。文献 7 同样也利用了双向的a u c t i o n 算法，并通过在已有的q u a s i a s s i g n m e n t 模型的基 础上提出了一种新的网络模型缩减算法，以及解决q u a s i a s s i g n m e n t 模型的 a u c t i o n 算法，其研究主要是通过减小网络结构来加速算法的执行效率，虽然它也 是采用线性模型但效率有了很大的提高。但上述算法仅解决了车辆调度问题，没 ， ， 有考虑人员的分配。 a u c t i o n 算法是在求解公交调度问题早期研究比较多的方法，但随着对这一问 题的深入研究以及公交系统本身的发展完善，大量新的方法不断涌现。比如说针 对整数规划模型的列生成、分支定价法、集合分割、启发式算法、遗传算法等。 此外，求解方式也从开始的车辆人员的分离式方案转换为解决车辆人员排班的集 成式方案。文献 5 ，9 ，1 1 - 1 3 ，1 5 一1 8 ，2 1 都是针对集成式方案的研究与实践。 文献 5 ，6 ，9 研究了使用基于列生成的分支定价方式求解大整数规划问题的 方法，其主要思想是将问题看成一个m a s t e r - p r o b l e m ，然后利用列生成产生多个 s u b - p r o b l e m 并求解，最后通过合并s u b - p r o b l e m 获得m a s t e r - p r o b l e m 的解。虽然 该方法能够找到比较满意的解，但由于受到m a s t e r - p r o b l e m 规模的限制导致该方 法仅能应用于较小规模问题的求解。使用该方法求解的时日j 复杂度也比较高，很 难满足实际的需要。虽然在排班算法中线性规划、线性松弛有着广泛的应用， 但由于实际应用中产生的大量变量和约束条件使得算法发生退化侧。文献 1 0 提 出了一种新的列生成算法一动态约束聚集算法。它有效地减少了规划过程生成的 变量及约束，降低了m a s t e r - p r o b l e m 的分解规模，大大缩短了线性规划的时间， 提高了该方法的求解效率。 但是，由于集成求解致使问题规模扩大，导致大量的求解算法效率低下。因此 通过将问题进行合理分割，然后利用现有方式针对分割后的子问题进行求解也成 为一种比较可行的方式。文献 1 1 便是在这一思想的指引下进行了大量不同分割 方法的研究与试验，并最终通过大规模的试验证明了分割方法的有效性。 此外，遗传算法，启发式算法也在公交调度领域展示了应用的巨大前景。文献 山东大学硕士学位论文 1 3 1 7 都从各自的角度阐述了应用人工智能方式求解调度问题的新视角。 在文献 1 4 中作者提出了使用一种启发式自调整的方案来生成员工排班计划。 其最大的创新是使用遗传算法前的预处理过程，通过作者提出的优良系数以及五 个权值评判标准来避免迭代过程中的重复计算，从而提高了求解效率。不过，由 于遗传算法已为人们提供了求解问题的基本框架，因此对于遗传算法的研究主要 是集中在对编码方式适应度函数以及各类操作算子的具体实现上。 虽然针对车辆人员排班有着大量的研究文献，然而前面所述方法大都是以 车辆与驾驶员数最少代价最小为目标函数，其生成排班的整个过程缺少交互性， 且只能处理单类型的车辆人员排班问题。但由于地域管理模式以及法规的独立性， 使得我们的应用必须能够处理多类型的车辆人员排班，且公交业务也比较复杂， 除了正常的( 公交) 营运业务外还可能有很多其它业务( 例如包车、班车业务) ， 这些业务的处理又比较灵活且又不完全与正常营运脱离，但它们的引入又会破坏 现有的约束。这种交互性以及车辆的多类型性是我们在实际应用中不可避免的问 题。此外，行车计划在整个公交营运过程中起着重要的作用。从管理的角度讲， 行车计划为管理提供依据；从客户角度讲，行车计划为给乘客提供良好的乘车环 境创造了条件；从员工角度讲，行车计划提供了一系列的工作指标。因此不论以 什么样的方式来生成计划最终都得能够满足管理的需要。因此要么在提供计划的 同时，解决相关的管理问题；要么使生成的计划适应现有的管理模式。因此上述 大量算法虽然表面上比较合理，但在我们的应用中由于受到管理模式的限制使得 上述方法很难解决我们面临的问题。比如不同时刻的车次其载客量会有很大差别 ( 例如人员流动的高峰期与低峰就有着很大的差距) ，进而就会形成营运收入的差 距。如何为分配到不同时刻车次的驾驶员制定合理的工作指标、平衡人员收入， 这是我们必须面对的一个非常重要的问题。如果在计划中完全不考虑这些因素， 那么就我们现有的公交信息化程度以及管理模式而言，计划制作人员很难为随机 组合的计划制定合理的工作指标。我们最终采用了后者。为解决上述问题我们对 问题进行了重定义并提出了一种新的分段式算法束求解多类型车辆人员排班问 题，从而在生成计划的同时考虑了现有营运管理模式的需要。 4 山东大学硕士学位论文 1 3 文章结构 第二部分介绍相关算法的基本原理以及公交业务相关概念；第三部分描述构建 车辆排班的数学模型及求解的主要算法：第四部分算法的实现；第五部分试验结 果及有效性分析；第六部分算法优化与改进：第七部分总结与展望； 1 4 论文创新 首先，虽然在公交人员排班领域已经有大量的文献，但是他们解决的都是单类 型车辆的人员排班问题。而我们解决的则是多类型车辆的人员排班问题，更准确 地说我们的研究是支持正班车与加班车两种类型车辆的人员排班问题。这也是我 们应用的主要模式。 其次，为了解决多类型车辆人员排班的求解效率，我们将a u c t i o n 算法引入人 员排班，大大提高了求解效率。 ， 最后，在排班算法中引入遗传算法，并结合公交营运的特点，对遗传算法进行 了合理的改进。改变了传统的编码方式，使用了采样编码，有效解决了生成初始 解的难度，并通过采样编码对整个解空间进行了有效的分割，大大提高了求解效 率。 山东大学硕士学位论文 2 1 算法概述 第2 章知识介绍 本节主要是对我们文章中使用的两种算法的简要描述，包括算法的基本原理、 实现步骤以及算法的应用情况等。 2 1 1a u c t i o n 算法简介 2 1 1 1 a u c t i o n 算法概述 a u c t i o n “1 算法是解决传统的任务分配问题的非常有效的方法。它不论是在性 能上还是理论上都优于解决同类问题的其它形式的主要算法。此外，它比较适合 并行计算， 4 中利用了a u c t i o n 算法的这一特性来提高并行度，从而优化了求解 效率。a u c t i o n 算法非常类似于现实生活中的竞拍场景，所有没有获得自己想要商 品的人，都会同时竞争某件或某些商品，并在每轮竞标结束将该商品的价格提高。 当多个人同时都想获得某商品时，商品将归予竞价最高的竞标者。 鉴于a u c t i o n 算法良好的性能，它在任务分配领域有着广泛的应用。同样也在 交通运输行业领域有着一席之地。 2 阐述a u c t i o n 算法在交通领域应用的基本模 型与算法。 3 5 ，7 中则将a u c t i o n 算法真正用于交通领域。 2 1 1 2a u c t i o n 算法基本步骤 我们介绍一个简单的分配模型。考虑n 个人分配n 个商品的问题。每个人只能 获得一个商品且每个商品只能分给一个人。此外，每个商品都有一个价格p ，( 也 就是想要该商品的人要付出的代价) ，而每个人对每个商品都有一个期望值v 。( 也 就是该商品在这个人心中的价值) 。因此一个人i 获得商品j 所能获得的利益 p r o f i t , - - - - v - p 。我们晚如果一个人i 获得商品j t 后使得 p r o f i t “, = 一p = m a x v 一p ， ，川。 则说明i 获得了自己想要的商品。如果所有人都获得了自己想要的商品，则分配 山东大学硕士学位论文 结束。， 因此，一个合理的分配a 必然满足下面的情况。对于每一个人i 来说存在一个 可以分配给自己的商品的非空子集s ( i ) ；而a 应该是一系列人一商品的关系对 的集合。也就是 a ) j s ( i ) v ( f ，_ ，) a b ) 对于每个竟标者i 最多仅有一对( i j ) a c ) 对于每件商品j 最多仅有一对( i ，j ) a 为了获取上述性质的有效分配我们构建下面的模型。 m a x i m i z e p r o f i t v , y f j j k j s u b j e c tt o 昀= 1 v f n ( 2 1 a ) 蜘= 1 n ( 2 1 b ) ( ，) e j 儿 o ，1 v ( i ，) a ( 2 1 c ) p r o f i t u 表示利益。) 0 表示存在从i 到j 的合理分配 ( 2 1 a ) 、( 2 i ”保证任何一个结点只能有一个前驱和一个后继 简单的a u c t i o n 算法实现： 1 ) 获取没有获得想要商品的竞标者i ，获取商品j 一使得j 满足：z 。m a x ， v ，一p j ) 若所有竟标者都获得想要的商品，转到4 ； 2 ) 将j 。分配给i ，若j 。已经分配给其它竞标者则将其剥夺； 3 ) 将商品j t 的价格死设为r2 + k q ， 坼。川m a 川x ，一p j ， q 。一m ，a 。x v ，一p j ) ；若j 是i 唯一可以得到的商品则将口设为q 2 ，转 到1 ； 4 ) 结束； a u c t i o n 算法的流程图如图2 - - 1 所示。 然而上述方法在v ，一q = 0 时会产生无限循环。在 1 、 2 中阐述了使用 占一s c a r i n g 参数消除这种缺陷。只需使得v ( i ，) al ，。i n t e g e r 且 m a x v u - p ， 一占 ，而 p = p + 托一a f + 占= 唯一嘶+ 占 i l j a u c t i o n 算法的分配过程示意图如图2 2 所示。 8 山东大学硕士学位论文 2 1 2 遗传算法简介 2 1 2 1遗传算法概述 遗传算法3 是一类通过借鉴生物界的进化规律演变而来的随机化搜索方法。其 特点是直接对结构对象进行操作，不存在求导或函数连续性的限制；具有更好的 全局搜索能力；采用概率化的寻优方法，能自动获取和指导优化搜索空间，自适 应的调整搜索方向，且无需无须确定的规则。 对于一个求函数最大值的优化问题( 求函数最小值也类同) 。，一般可描述为下面 的数学模则： ， f m a x 二f 三( x 臻) ( 3 2 荔a ) u 图2 3 毛r ，u 关系图 工，r ，u 之间的关系入图2 3 所示。 对于一般的最优化问题，其目标函数和约束条件种类繁多，有的是线性的， 有的是非线性的；有的是连续的，有的是离散的。随着研究的深入，人们逐渐认 识到求解最优解往往会比较困难，而且有时也不现实。因此，在这种情况下，求 出其近似最优解或满意解便成为研究者的主要着眼点。总的来说，求最优解或近 似最优解的方法主要有三种：枚举法、启发式算法和搜索算法。其中，搜索算法 是在可行解集合的一个子集内进行搜索操作以找到问题的最优解或近似最优解， 该方法虽然保证不了一定能够得到问题的最优解，但若适当地利用一些启发知识， 就可以求出一个比较满意的解。而遗传算法则较好的平衡了近似解的质量与求解 效率的矛盾。为解决此类问题提供了一个有效的途径和通用框架，开创了一种新 的全局优化搜索算法。 2 1 2 2遗传算法基本步骤 第一步：确定决策变量及其各种约束条件，即确定出个体的表现型x 和问题的 山东大学硕士学位论文 解空间。 第二步：建立优化模型，即确定出目标函数的类型及其数学描述形式或量化 方法。 第三步：确定表示可行解的染色体编码方法，也即确定出个体的基因型x 及 遗传算法的搜索空间。 第四步：确定编码方法，即确定出由个体基因型x 到个体表现型x 的对应关 系或转换方法。 第五步；确定个体适应度的量化评价方法，即确定出由目标函数值f ( x ) 到个 体适应度f ( x ) 的转换规则。 第六步；设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算 子的具体操作方法。 第七步；确定遗传算法的有关运行参数。 遗传算法仅为求解问题提供了个有效的途径和通用框架，其中如何根据具体 的问题确定编码以及如何进行选择、交叉、变异等操作是决定算法求解效率、收 敛性以及求解质量的重要因素，在文献e 2 6 - 2 9 中分别对上述操作进行了单独的讨 论。 2 1 2 3遗传算法的特点 ( 1 ) 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用 决策变量的实际值来进行优化计算，但遗传算法不是直接以决策变量的值，而是 以决策变量的某种形式的编码为运算对象。 ( 2 ) 遗传算法直接以目标函数值作为搜索信息。传统的优化算法不仅需要利用 目标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索 方向。而遗传算法仅使用出目标函数值变换来的适应度函数值，就可确定进一步 的搜索方向和搜索范围，这对目标函数是无法或很难求导的函数，或导数不存在 的函数的优化问题，以及组合优化问题等，非常方便。 ( 3 ) 遗传算法同时使用多个搜索点的搜索信息。传统的优化算法往往只从解空 间中的一个初始点开始最优解的迭代搜索过程。单个搜索点所提供的搜索信息少， 所以搜索效率低有时甚至陷于局部最优解而停滞不前。遗传算法从由很多个体 山东大学硕士学位论文 所组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开始搜 索。对这个群体所进行的选择、交叉、变异等运算，又会产生出新一代的群体， 从而提供更多的群体信息。 ( 4 ) 遗传算法使用概率搜索技术。很多传统的优化算法往往使用的是确定性的 搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这 种确定性往往也有可能使得搜索永远达不到最优点。而遗传算法属于一种自适应 概率搜索技术，其选择、交叉、交异等运算都是以某种概率的方式来进行的，从 而增加了其搜索过程的灵活性。 由于遗传算法的上述特点，使其在许多领域都有着广泛的应用，而且其在公交调度领域 也有着重要的地位，文献 1 4 ，1 6 ，1 7 ，2 3 都使用或者结合使用遗传算法的思想来求解调度的最优 解或近似最优解 2 2 公交业务介绍 随着城市公共交通的发展，在2 0 世纪初，国内外学者便开始了对公交调度的 研究，且一度成为该领域的前沿研究课题。随着研究的不断深入，以及公共交通 事业的不断发展，公交调度在国内外也逐渐形成各自的运行模式。 公交调度是一类典型的组合优化问题或者说是任务分配问题，也就是说在满足 一定约束的情况下，利用有限资源求解某一最优调度的最优化问题。由于公交调 度问题本身属于n p - h a r d 问题，许多学者都致力于优化算法或近似算法的研究， 我们的研究也同样如此。在开始探讨具体的求解算法之前，我们首先对公交领域 相关知识进行简要的介绍。 ( 1 ) 问题定义 车辆人员排班就是在给定车次，任务以及相应约束的情况下，求解代价最小的 车辆人员的合理调度方案。每一个车次都有一个规定的离站时间和到站时问。合 理的车辆调度是指( 1 ) 每一个车次都会被分配到一辆车；( 2 ) 每一辆车要得到一 系列可连续运行的车次。可连续运行是指在车辆1 分配到的车次中，前后两个连 续的车次之间满足前一车次的到站时j b j 与后车次的离站时日j 的差值在规定的最 大最小停站闭隔之内。合理的人员调度是指( 1 ) 每一个任务都会被分配到一个人； ( 2 ) 每一个人都会得到一个仅且一个任务：( 3 ) 每个人的工作时日j 不能超过法律 山东大学硕士学位论文 或法规的约束范围；( 4 ) 每个任务必须满足工作里程的要求。每一个任务由一组 可连续运行的车次组成。 ( 2 ) 调度形式 公车调度形式有很多种，我们这里只介绍其中一种，也是我们现实应用中主要 使用的一种形式。该形式将车辆按车辆工作时间的长短分为正班车、加班车、夜 班车 ( a ) 正班车，主要是指车辆在日间营业时间内连续工作相当于两个工作班 的一种基本的调度形式，所以又称双班车或大班车 ( b ) 加班车，主要是指车辆仅在某种情况下，在某段营业时间内上班工作， 并且一日内累计工作时问相当于一个工作班的一种辅助调度形式，所 以也称单班车。 ( c ) 夜班车，指车辆仅在夜间上线工作的一种辅助调度形式。 在我们的算法中仅考虑前两种形式。上述三种车辆调度形式的基本分类关系表 如表2 一i 所示。 车辆调度形式分类关系表 表2 一l i调度形式工作时间长短工作时间类型 l 正班车双班日间；或以日间为主 f 加班车 单班 日间；或日夜兼容 l 夜班车单班夜间；或以夜间为主 ( 3 ) 车次 一个车次是指车辆从主站场出发经过所有设置的乘客站点回到主站场的一个 过程。每个车次都会有一个规定的离站时间和到站时间 ( 4 ) 行车时刻表 行车时刻表决定了某条线路一天发出的车次总数，给出了每个车次的到离站时 间，决定了主站场发车的时间日j 隔，因此也就决定了乘客的平均候车时1 1 日j ，对乘 客的服务质量有着很大的影响，同时也对公交公司的载客率以及收入有着重要影 响。 因此，生成一份合理的行车时刻表也是一项非常重要而且复杂的工作。但我们 的工作并不是生成行车时刻表。我们应用中的时刻表是由用户提供的。下表2 2 为一份真实行车时刻表的局部样例： 2 山东大学硕士学位论文 时段 发车间隔 5 ：4 吣：0 l 7 6 ：o l _ 0 6 ：1 3 6 0 6 ：j 3 1 0 6 ：2 3 5 0 6 ：2 3 由6 ：3 l 4 0 6 ：3 1 电6 ：3 73 行车时刻表表2 2 序号离站时间剑站时间 l 5 ：4 0 7 ：0 4 25 ：4 77 ：i i 35 ：5 哇7 ：1 8 4 6 ：0 1 7 ：2 5 5 6 ：0 77 ：3 1 6 6 ：1 37 ：3 7 7 5 ：1 8 7 ：4 2 86 ：2 37 ：4 7 96 ：2 77 ：5 1 1 06 ：3 l7 ：5 5 1 16 3 47 ：5 8 1 26 ：3 78 ：0 1 ( 5 ) 任务 任务是指分配给每个驾驶员的工作指标，它是由系列工作片组成，而每个工 作片是由多个可以在有效停站间隔内连接起来的车次组成。如图2 1 所示，任务l 由两个工作片构成。在我们的应用中一个任务最多只能包含两个工作片，而且两 个工作片之间的间隔应该大于某个规定的常数值，该值在不同地区或组织内可以 有所不同的。虽然加班车也是由两个工作片组成，但对于正班车来说，任务i 在 公交领域被称为两头车我们将其称为间断性任务。而对于加班车，工作片间的间 隔表示正常的交班。此外，任务还隐式包含每天要运行的里程、工作时间，以及 每天的营业额等其它信息 圈2 4 任务一上作片示意豳 ( 6 ) 行车计划 车辆人员排班的最终结果是生成一份行车计划。行车计划是线路始末站及重点 中途站所有的行车时刻表，它规定了在该路运营的各个班次车辆每个周转车次的 到达和离丌该站的时间、行车问隔、及换班等。如表2 3 所示。 山东大学硕士学位论文 行车计划表2 3 、殍适 l23 4 5 赫 开到开到开到开到 开到 l5 ：4 07 ：0 47 ：1 38 ：3 78 ：4 6 i o ：1 01 0 ：1 9l l ：4 3 交1 2 ：3 01 3 ：5 4 所 25 ：4 t 7 ：1 1 35 ：5 47 ：1 8 46 ：0 17 2 5 56 0 7 7 ：3 1 66 ：1 37 ：3 7 7 6 ：1 87 ：4 2 8 6 ：2 3 7 4 7 山东大学硕士学位论文 第3 章数学模型及求解算法 根据前两章的介绍可知，在我们的应用中各线路或路队的车辆与人员基本固 定，员工工资= 基本工资+ 提成，因此我们的算法必须满足下列需要： ( a ) 支持多类型车辆人员调度( 正班车调度、加班车调度) ( b ) 能够平衡驾驶员的收入和劳动强度 而现有的文献大都是求解使用车辆人员最少且代价最小的单类型车辆人员调度方 案，为了满足上述要求我们需要对问题进行重定义，调整算法的目标函数。 ( 1 ) 问题定义， 在给定车次、任务、车辆类型以及相应约束的情况下，求解整体营运时间最小 的多类型车辆人员的合理调度方案。约束包含对现有管理模式的支持，也即对员 工工作指标的潜在支持。 ( 2 ) 约束概述 a ) 车辆类型并不是指车辆本身型号或种类，而是指车辆的营运调度类型( 参 见2 2 ) 。由于人们出行具有一定的规律性，客流便会在日间产生波动性， 比如早晚的上下班时间客流量会较大( 如下表3 - 1 、3 - 2 为公交某线路的客 流数据) 。为了满足人们的乘车需要，一般在客流量较大时增加发车密度 而在客流量较小时减少发车密度。这样如果以客流高峰期所需车辆安排全 日所需车辆，就会造成资源浪费；而按平峰安排车辆就不能满足高峰的需 要。因此便出现了两种类型的车辆：一种是全天运营的车辆( 正班车) ；另 一种便是在高峰期运营的车辆( 加班车) 。 b ) 员工工作指标是指员工一天工作的定额，超过定额部分将作为员工提成。 由于在不同时段的客流量不同，因此载客量也就不同，最终将导致收入的 不同。由于现有公交车采用现金与i c 卡两种方式计费，因此难以统计出 各时段的详细收入情况。我们应用所在地区( 青岛、内蒙) 则是通过对车 辆营运类型的划分以达到合理制定工作指标的目的。首先通过车辆类型将 车辆分为高峰运营车次和非高峰运营车次，并对两种类型车辆的全天营运 收入进行统计以制定出相对合理的收入指标。然后对同种类型的车辆进行 周期轮换已达到公平的目标。前面提到的所有算法大都只考虑单一类型的 山东大学硕士学位论文 车辆，而且其车辆与车次是随机组合，这对人工制定收入计划带来巨大的 困难，因此难以满足目前我们的应用需要。 c ) 高峰上线车辆数( 客流高峰期在线运营的车辆数) 应等于全部车辆总数。 所有计划都应该满足高峰上线车辆数的要求，它能够保证资源的最大利用 率，也是判断生成计划是否合理的一个指标。 d ) 里程指每个驾驶员一天要跑的里程。里程= 车次数虬( c 表示每个车次的标 准里程，一般情况下为某个定值) e ) t 作时间是指驾驶员从上班到下班总的时间长度。工作时间必须满足国家 法律以及地方法规的相应规定。 某线路统计数据表3 2 停站点 a b c d e f g hi 停车站序号j i23 4 56 7 89 站点集散度 1 b 6 4 4 6 5 4 6 7 9 2 41 4 5 91 0 1 06 7 46 1 61 8 7 4 路段序号v2 v 3 4 56 78 路段客流量 1 8 6 42 2 3 12 2 6 22 6 4 92 4 5 0 2 3 8 61 7 4 6 1 8 7 4 路段满载率 0 6 l0 7 6o 7 80 8 70 8 10 80 4 8 0 6 2 因此为了解决上面的问题，我们提出了两阶段算法：第一阶段通过使用改进的 a u c t i o n 算法确定车辆调度类型，并保证目标函数最小；第二阶段根据第阶段分 配好的车辆类型使用遗传算法求解整个问题的近似最优解，并通过集合分割技术 来提高求解效率。 6 山东大学硕士学位论文 3 1 数学模型 在第一部分我们讲过从建模的角度来说，车辆人员排班已被抽象为多种模型。 包括有运输模型、任务分配模型、最小代价流模型、q u a s l 分配模型、配对模型等。 其中最小代价流模型、q u a s l 分配模型是比较有代表性而且应用也比较多的模型 在本章我们主要介绍我即将用到的q u a s l 分配模