浅谈公交优化调度问题.ppt

请您按击鼠标，编辑标题文的格式。,请您按击鼠标，编辑大纲正文格式。,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,*,请您按击鼠标，编辑标题文的格式。,*,请您按击鼠标，编辑大纲正文格式。,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,浅谈公交优化调度问题,1,公交优化调度问题简介,国内外研究情况综述,选读论文中的模型分析,对选读论文中所提方法的进一步思考,内容框架,2,一、公交优化调度问题简介,城市公交是每个城市非常重要的交通工具，是城市交通的主体，被称为城市肌体的“动脉”。做好公交车的调度对于完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。,公交运营工作是公交企业的核心基础工作，它是根据客流的变化和具体运营条件及其它条件，安排不同车型的车辆和行车的组织方案，这是个多目标的优化问题。公交运营设计是一个较复杂的决策过程，公交运营优化设计模型的构建必须平衡公交乘客和公交企业之间的利益。,3,公交调度分为调度计划的制定与调度的实施，其中调度计划的制定是公交企业运营的前提和基础。公交运营调度计划的制定主要包括三个方面内容：制定公共交通时刻表，即确定行车间隔；运力配置计划；劳动力配置计划。其中，行车时刻表的制定是整个计划的重中之重，是制定其它计划的前提。,行车时刻表是按照线路的当前客流量情况，确定发车频率，提供线路车辆的首、末车时间。行车时刻表是公交企业对社会的承诺，它决定着为乘客服务的水平，发车间隔越小，服务水平越高，但是公交企业投入的成本越高。行车时刻表的编制应是在满足客流需求的前提下，尽量减少不必要的投入。这是个多目标优化问题，对于公交公司来说，在一定的顾客满意度的前提下，公司派出的车辆次数越少，其积极效益越高；而对于顾客来说，等待的时间越少，满意度越高。,4,二、国内外研究情况综述,查阅国内外有关公交优化调度方面的文献，可以看出，已有众多学者对公交运营设计中的运行线路、时刻表、以及车辆路径等问题分别进行过有益的探索，给出了解决复杂运营设计、时刻表优化等问题的模型、算法等，而且基于不同目标函数、不同约束条件给出了问题的解决方案，这对于该领域的进一步研究工作提供了极为可贵的借鉴意义。,总结一下，已有研究大致从以下方面探讨了公交优化调度问题：,1,）基于不同目标、不同约束条件下的优化模型的建立,公交运营设计是个多目标的优化问题和较复杂的决策过程，因为涉及公交公司、乘客等多方利益。因此，公交运营优化设计模型的构建必须平衡公交乘客和公交企业之间的利益。如：,5,覃运梅在文章,公交调度优化模型,中，研究了公交车调度的优化问题。以总收益最大为目标,以满载率和最大发车间隔为约束建立了优化模型。,宋瑞,何世伟等在文章,公交时刻表设计与车辆运用综合优化模型,中，构造基于随机期望值规划的公交时刻表设计与车辆运用综合优化模型，该模型综合考虑了公交企业的经济效益和公交乘客所得到的公交服务水平的优化，并给出公交服务频次和车辆分配协调的启发式算法。,Chakroborty P.,Deb K.,and Subrahmanyam P.S.,在文章,Optimal Scheduling for Urban Transit Systems using Genetic Algorithms,中，基于使换乘乘客和候车乘客的等待时间最小化建立时刻表优化模型。,6,2,）,针对调度问题数据量巨大的特点，对模型计算方法的研究,公交车辆调度所要处理的数据量是巨大的，因此，如何有效地重组、利用已知数据建立模型，并提出运算效率较高的计算方法很值得研究。这方面，已提出好多算法，如：,覃运梅在文章,公交调度优化模型,中，提出用计算机枚举的方法求解她所建立的模型，从而给出线路的发车间隔、评价指标及发车时刻表。,任传祥，张海,范跃祖在文章,混合遗传,-,模拟退火算法在公交智能调度中的应用,中，兼顾企业与乘客的利益建立了公交车辆行车计划模型，将遗传算法与模拟退火算法相结合，组成混合遗传,模拟退火,(GA-SA),算法，对公交行车调度进行优化。,Ceder Avishai and Ofer Tal.,在文章,Timetable Synchronization for Buses,中，提出了一种启发式算法，基于同时到达换乘站点的车辆数最多求得最优解，研究了车辆同步性问题。,另外，还有学者用图表分析方法、数值分析方法、模糊控制方法、运筹学理论等对所建立的模型进行求解。,7,3,）公交系统内换乘最优化问题的研究,这方面也有大量学者进行过研究。如：,周雪梅,杨晓光在文章,基于,ITS,的公共交通换乘等待时间最短调度问题研究,中，研究了,ITS,实时提供公共交通信息的条件下,公共交通换乘等待时间最短调度问题。基于使公共交通的换乘时间最短，从而实现最佳衔接的目标下，应用运筹学理论，分别针对一个换乘点和多个换乘点的情况建立了线性规划模型，并给出了公共汽车发车时刻表的确定方法。,Bookbinder James H.and Alain Desilets,在文章,Transfer Optimization in a Transit Network,中，研究了公交网络的换乘最优化问题，指出我们应该重视公交车的实际运营问题。他们在研究过程中综合考虑了政策因素、车辆行程时间的随机性、仿真和最优化的组合问题，给出了基于车辆到达具有随机性，以及不同目标函数和换乘规则条件下的换乘最优化等问题。,8,4,）不同运输方式间换乘最优化问题的研究,国外学者对此进行过大量研究，如：,Kikuchi,S.and Parameswaran,J,在文章,Solving a schedule coordination problem using fuzzy control technique,中，使用一种模糊控制方法，研究了机场枢纽站和公交车站的协调性问题。他们使用了诸如高、低、小、更多等模糊规则实现时刻表调整，得到了比枚举方法更优的结果。,Shrivastava P.,and S.L.,在文章,Dhingra.Development of Coordinated Schedules using Genetic Algorithms,中，研究了火车和常规公交车辆间的协调性问题。通过建立火车与公交车辆间的换乘时间最短和公交系统运营成本最低的多目标函数使用,Schedule Optimization Model,（时刻表优化模型），实现了公交车的协调调度。,9,5,）公交运营设计中的运行线路、车辆路径等问题的研究,这方面的研究，如：,Shih,M.C.,Mahmassani,H.S.,and Baaj,M.H,在文章,A Planning and Design Model for Transit Route Networks with Coordinated Operations,中，指出：在研究公交车时刻表协调性问题时，应考虑三个主要因素：,1,）合理选择各个公交中心；,2,）公交网络的设计；,3,）协调和不协调状况下，发车时间间隔的确定。,10,6),运营成本及社会效益方面的研究,Han and Anthony F,在文章,Assessment of Transfer Penalty to Bus Riders in Taipei:Disaggregate Demand Modeling Approach,中，评估了台北、台湾公交乘客换乘时间对应的经济损失，指出目前算法可能低估了换乘损失。作者用分离的二项选择模式描述公交乘客的行为。研究表明，以相应时间内可创造的经济价值估算，步行时间可创造价值约为对应的乘车时间可创造价值的,6,倍，而等待时间内可创造价值则为乘车时间内对应价值的,3,倍。,何宝泉,吴斯浩等在论文,公交车调度优化模型,中，提出了制定一条公交线路车辆调度方案的优化数学模型。模型中计算了乘客在车站等候的时间内所可能创造的财富,社会效益，并将乘客因候车而丧失创造该财富的机会看成一种社会成本。综合考虑公交公司运营成本和相应的社会成本，对车辆调度方案进行评估。,11,三、选读论文中的模型分析,Title:Minimizing Transfer Times in a Public Transit Network with a Genetic Algorithm,Author:by Fabian Cevallos&Fang Zhao,这篇论文基于遗传算法，提出了解决公交系统内换乘时间最优化问题的系统性方法。主要是通过调整现有时刻表，找到最优解决方案。文中所提出的方法用到了现有时刻表和所有换乘站点的乘客资料，并考虑了车辆到达的随机性。基于,Broward County Transit,公交公司所提供的调度资料，计算了系统目前状况下的总换乘时间，以及用本文所介绍的方法对系统现有时刻表进行调整，所得推荐系统的总换乘时间，结果表明该算法可以在很大程度上节约公交系统的总换乘时间。,12,1,、建模过程,假设公交系统中有,N,条公交线路，我们来考察一位乘客从线路,i,上的 车,p,换乘到线路,j,上的车,q,所需的时间。设公交车,p,所在车站为,k,，而车,q,所在车站为,l,。记公交车,p,到达,k,站的到达时间为,a,ikp,，,ikp,为因车辆到达随机性所致的车,p,到达,k,站的实际时间与时刻表规定时间的偏离值，,S,i,为线路,i,的时刻表调整时间，,W,ijkl,为换乘旅客从车站,k,步行到车站,l,所需时间。因此，,(,a,ikp,+,ikp,+,S,i,+W,ijkl,),便是要从车,p,换乘车,q,的旅客到达车站,l,的时刻。,13,现在考察车,q,的离开时间。记,d,jlq,表示时刻表规定的车,q,应从车站,l,发出的时间，,jlq,和,S,j,与,ikp,和,S,i,具有相同的意思。因此，,(,d,jlq,+,jlq,+,S,j,),表示考虑了时刻表误差和对线路,j,的时刻表作适当调整后的公交车,q,的新的发车时间。因此，等候车,q,的乘客花去的换乘时间为,(,d,jlq,+,jlq,+S,j,)-(,a,ikp,+,ikp,+,S,i,+W,ijkl,),。对所有线路上全部车辆间可能换乘的所有乘客进行加和，便得到了整个系统中的总换乘时间。用公式表达为：,14,15,2,、模型求解步骤,2.,模型求解步骤,用遗传算法运算上面所建立的模型公式，数据流程见图,1,所示。,首先，从公交调度数据,库中获取时刻表，便得到各条线路上公交车辆安排好的到达和离开时间,其次，从,AVL,或,APC,系,统中获取车辆到达和离开,的实时数据，以及换乘旅,客信息,接着，数据经过格式化和,质量保证处理，同时生成,相关矩阵和乘客换乘矩阵,然后，利用遗,传算法进行优,化处理,最后，得到最终结果，,即时间调整量，保存并,用来生成新的时刻表,16,这里的遗传算法是使用代表时间调整量的整数进行编码（即采用整数编码方法）。因此，代表解的字符串中包含,N,个整数，这里,N,是线路条数。交换操作类似于标准遗传算法中的交换操作。突变操作是在突变频率的基础上，从所有可能的时间调整值中选取一个基因，替代当前基因值。,在遗传算法中，各条线路的时间调整量是通过遗传迭代进行计算的，从而找到最优解。当满足预先设定的条件时，算法结束。这些预先设定的条件可能是对处理事件的限制，或在很多代中找不到更优解时，算法结束最后，保存所得时间调整量，并用来生成新的时刻表。,17,3,、应用中应注意的问题有：,本文使用遗传算法解决了换乘时间最优化问题。基于发车间距保持不变，对线路固定的公交系统，通过检索车辆离开和到达的最优组合，实现了时刻表间的协调，以减少换乘时间。算法设计过程中，考虑了各种行程组合、车辆到达和离开的随机性、步行时间和换乘旅客数等因素。基于系统中一个或一组时刻表保持不变，考虑调整剩余时刻表，同时附加了诸如不同行程组合保持不变等约束条件。,本研究旨在：不对公交公司提供的服务产生重大影响的条件下，将该方法作为生成时刻表处理过程中的一部分，以实现换乘时间的最优化。在不需要额外增加投资、劳动力和影响政策条件下，将该方法并入调度处理过程中，为操作层面提供一种工具。图,2,描绘出换乘最优化是如何并入到调度过程中的。,18,考虑发车时间间隔变动的遗传算法在世纪中也有应用，但他们可能不太适合那些需要认真考虑设计、运营和地区差异性等因素的问题。另外，美国的公交公司一般不轻易调整发车间隔，因为这有可能触及劳动契约规则、资源再分配或政策管辖公正等问题。因此，这类算法可能不会被那些不需要变动发车间隔的公交公司所接受。,19,4,、案例分析,1,）应用该方法过程中需要以下数据：,时刻表,提供线路、换乘站点和到达时间；,线路图,提供各条线路和他们的站点信息；,公交系统图,显示所有线路和换乘站点信息；,乘客数据,提供各个站点的乘客信息；,AVL,或,APC,数据,获取实时车辆到达和各个站点上车乘客信息；,电子票务收费系统信息,获取换成旅客数据。,20,2,）车辆到达和离开时间的随机性研究：,公交车辆往往无法按照时刻表上安排好的时刻准点到达，而通常是或早或晚到达。尽管车辆到达和离开时间具有随机性，但其高度依赖于时刻表上安排好的时刻。因此，便可以使用一种概率分布来反映规划时间与车辆实时到达和离开时间之间的偏移量。车辆实时到达和离开信息可通过人工观察或,AVL,系统、,APCs,系统获得。,图,3,用直方图表明了美国一车站,(Broward Terminal),内公交车辆到达和离开时间与时刻表上规定时间的偏离量的概率分布，以及,4,种概率分布曲线。它们是：对数正态分布曲线、正态分布曲线、,Gamma,分布曲线、,Weibull,分布曲线。通过直接观察和统计分析，得到对数正态分布最适合反应时间偏离量的分布。,21,概率分布类型知道后，便可用反变换法（,Inverse Transformation Method,）估算时间偏离值。计算累积分布函数的反函数，得到估计值：,x=F,-1,(U),。,22,3,）结果,为检验遗传算法，我们建立了包含有,40,条公交线路（,80,条不同方向路径）、,255,个换乘站点和公交公司,BCT,提供的调度信息的数据库，此外，基于,BCT,所提供的数据，建立了乘客流数据库和时间偏离量数据库。通过电子票务收费系统的,swipe-card,数据获取每段旅程的上车乘客数、公交公司,BCT,系统的换乘率（,22%,）、日乘客数（,12,万）和每条线路的行程段数。因为本研究的目标之一是检验遗传算法的效率和有效性，所以在相同标准下，对比了系统当前换乘时间、用,brute force approach,计算结果合用遗传算法所的结果。,在规格为,processor 1.7Ghz,1GBRAM,，和,60GB(7200rpm)hard drive,的型号为,Dell Precision M60,计算机上运算若干次后可获得结果。群体规模为,60,，遗传迭代的最大代数为,20,，交换率和突变率也可以被检验出来，并得到不同,CPU,运算时间下的平均换乘时间。图,4,示出了迭代结果。,23,从图可看出，系统当前总换乘时间为每天,3150,小时，使用,brute force,随机检索方法，在较短的,CPU,处理时间下，迭代,2000,次后，便可得到较大的改善，总换乘时间每天节省,231.78,小时。应用遗传算法后，节省时间可进一步增大到,381.05,小时，这表明遗传算法不但有效，而且效率较高。,24,表,1,给出了基于遗传算法计算结果，得到的各条线路的时间调整值，据此调整现有时刻表，便可得到遗传算法中给出的预期结果：总换乘时间从每天的,3150.37,小时减少到,276932,消失，减少了,12.10%,。,25,遗传算法的效率依赖于其操作特性。图,5,给出了交换率与换乘时间之间的关系曲线。从图中可以看出，当交换率为,50%,、突变率为,10%,时，可得到最好的结果。,26,四、对选读论文中所提方法的进一步思考,公交系统的优化调度问题的大量研究，一直集中于终点换乘、或换乘量较大的指定站点或理论公式的研究层面。所选论文介绍了一种可实现同步换成的系统性方法。可用于拥有多条线路和多个换乘站点的公交系统。,通过具体案例分析，研究了一个拥有,40,条公交线路（,80,个不同方向路径）、,255,个换乘站点的公交系统。结果证明：作者提出的基于遗传算法的方法，能够解决那些经典优化算法很难解决的换乘同步性问题，并且可已在很大程度上节约总换乘时间。这种方法在计算方面也是可行的，而且容易实施。因为它简单易懂，并更被插入调度处理过程中去，因此能够被广大公交公司所接受。,27,从其用到的优化模型的类型角度看，该方法具有灵活性，能够很容易得到改进或修改。这一特点方便了新观点和新的计算方法的融合。,在原文作者研究的基础上，我们可进一步考虑对遗传算法的改进性研究，主要可从基因交换频率、突变频率、迭代次数、染色体和并入迁移交换操作等角度考虑进行。此外，可对计算方法做深入研究，进一步改善计算机的运算效率和有效性。同时，可考虑深入研究的计算方法有：并行计算、模拟退火算法或其他进化策略的创新算法等。,28,Thank you!,29,