智能交通系统中的公交运营优化调度研究

智能交通系统中的公交运营优化调度研究赵厚宝1苏勇（江苏科技大学计算机科学与工程学院江苏镇江212003）摘要：城市公交系统是一个巨系统，其相关的模型和方法都非常复杂，为此，本文引入了高性能计算来提高智能算法的优化质量和收敛速度。有机结合遗传算法GA（GeneticAlgorithm）和禁忌搜索法TS（TabuSearch）两者优点，构成混合遗传算法HGA（HybridGeneticAlgorithm）。针对公交车辆调度现状及所处的运营环境，运用HGA的智能化特征，进行了公交车辆智能调度研究。研究表明，基于GA-TS的混合遗传算法优化公交车辆运营调度，能够有效地改善原有公交车辆运营调度的不足，提高动态运营决策效率和服务质量。关键词：遗传算法；禁忌搜索算法；混合遗传算法；城市公共交通中图分类号：TP311文献标识码：BOptimizingDispatchingofPublicTrafficVehiclesinIntelligentTransportSystemsZhaoHou-baoSuYong(SchoolofComputerScienceandEngineering,JiangsuUniversityofScienceandTechnology,ZhenjiangJiangsu212003)Abstract:Urbanpublictransportsystemisagiantsystemanditsrelatedmodelsandmethodsareverycomplicated,thispaper,theintroductionofhigh-performancecomputingtoimprovetheintelligentalgorithmtooptimizethequalityandtheconvergencerate.ThebasicprinciplesofGeneticAlgorithm(GA)andTabuSearch(TS)areexpatiatedon.BothofoptimizingalgorithmsareavailablyintegratedintoHybridGeneticAlgorithm(HGA).WithregardtoactualstatusandoperationenvironmentofPublicTrafficVehicles(PTV),intelligentdispatchingofPTVisstudiedwithHGA.ThesimulationresultsaredemonstratedthatintelligentdispatchingofPTVcouldberealizedtodecision-makingandtheshortcomingcabbeeffectivelyovercomebasedonGA-TSHybridGeneticAlgorithm.Inthewayoperationefficiency,travelingsafetyandservicelevelofPTVareenhanced,thereasonableandviablemeansareprovidedforintelligentdispatchingofurbanPTV.Keywords:GeneticAlgorithm;TabuSearch;HybridGeneticAlgorithm;UrbanPublictransportation;1.引言随着城市社会经济的快速发展,城市交通需求增长迅猛,现有城市交通基础设施已不能适应机动化增长需求,城市交通问题成为城市社会经济发展的重要制约因素。。因此公交车辆的合理运营调度就显得尤为重要。将人工智能方法引入公交车辆运营调度管理中，利用智能算法、调度经验以及专家知识来缩小搜索空间，可以尽快找到满意解，形成合理、可行的调度方案。本文采将混合遗传算法HGA（HybridGeneticAlgorithm）用于公交车辆优化调度研究，以合理解决公交车辆供需矛盾。2.公交车辆运营调度的GA-TS混合遗传算法设计遗传算法是一类借鉴生物界的进化规律－适者生存、优胜劣汰遗传机制演化而来的随机搜索算法[1]。公交运营优化问题多参数，多变量，无法通过解析过程求出最优解，我们可以从众多的解中选出最优的解。这也恰好模拟了生物进化的适者生存规律，使得最具有生存能力的染色体最大可能地生存下来，这个最具有生存能力的染色体就对应于公交运营优化问题_______________________作者简介：赵厚宝(1978-),男，汉，安徽六安人，计算机应用技术硕士研究生。苏勇(1961-),男，汉，江苏镇江,副教授，硕导，主要研究方向，数据挖掘，数据库等。Email:[e-mail]的一个最优解。禁忌搜索算法是一种局部搜索修正算法，模拟人类具有记忆功能的寻优特征。禁忌搜索算法通过局部邻域搜索机制和相应的禁忌准则，来避免重复迂回搜索，并通过期望标准来释放一些被禁忌的优良个体，进而保证多样化的有效搜索，以此来最终实现全局优化[2]。研究发现，GA是一个渐近的收敛过程，可以极快地达到最优解的90％，但要真正达到最优解却要花很长时间[3]。解决这一问题的一种方法是对简单GA进行适当的改进，如简单GA中增加交叉约束算子，使交叉操作限制在基因型（编码串）相似的染色体之间，就能在一定程度上改善GA的局部搜索能力；另一种方法是将GA与传统的、基于问题知识的启发式搜索技术相结合构成HGA框架，从而改善简单GA的局部搜索能力，提高优化质量和搜索效率，以弥补单一优化方法的不足。GA-TS混合遗传算法程序流程框图如图1所示[4]图1.1GA-TS流程Fig1.1TheFlowchartHybridGeneticAlgorithm3.模型求解公交车辆调度既要考虑公交公司的利益也要充分考虑乘客的利益，因此设定公交车辆调度问题的目标函数时从以下两个方面考虑：a)从公交公司的角度出发，使公交公司的发车次数最少来保证公司的利益，也即公交公司的运营成本最低。b)从乘客的角度出发，使得全天所有乘客的等车时间最小来保证乘客的利益，也即乘客等车所损失的费用最低[5]。公交公司的运营成本V是一天的发车次数1(/)kikkTt=∑V与此线路的里程L以及每辆车每公里消耗的单位成本1C的乘积：1/1kKkKvCLtt==∑V(3-1)乘客等车所损失的费用P是所有乘客的等车时间2kj111(/2)kmKJkkijt===ρ∑∑∑V与每一个乘客每等待一个单位时间所相当的损失费用2C的乘积：22kj111(/2)kmKJkkijPCt====ρ∑∑∑V(3-2)但这两类目标是相互冲突的，两个目标函数就存在一个权值的问题，这体现在目标函数种两项的加权系数的大小。如果希望乘客等车时间比较短，这个时候乘客等车时间的加权系数要大些；反之亦然。于是目标函数为21/2kj1111min()(/2)kmkKJKkkKkijfCLttCt=====α+βρ∑∑∑∑VV(3-3)模型的约束条件主要考虑两个方面：a)发车的最小间隔和最大的时间间隔要满足有关部门的规定;b)公交公司要盈利，必须使公交公司所收得的票钱总和要大于公交公司最低的消耗成本，也就是要满足下式：111/(/)JKkikkjKnuTtCLκΚ=1==×∑∑∑V(3-4)3.1符号说明k为时段集，{1,...,,...,}kkK=，k表示第k个时段；J为车站集，{1,...,,...,}JjJ=，j表示第j个车站；kT表示第k时段的时间长度；m表示一天中总的发车车次；kju表示第k时段第j站上车乘客数；kjρ表示第k站的乘客到达率；kijΦ表示在第j站上乘坐上第k时段发的第i次车的乘客的总等车时间；1C为每公里每辆公交车消耗的费用；2C为每个乘客每等待一个单位时间相当的损失费用；α表示公交公司消耗费用的加权系数；β表示乘客等待时间所损失费用的加权系数，加权系数的关系为α+β=1；n为全程公交票价；L为线路的总公里数；/kkkmTt=V表示第k时段的总发车车次于该时段的时段长度与发车间隔的比值；Kkk=1mm=∑总表示一天中总发车车次为各时段的发车车次之和；kjkjku/Tρ=表示第k时段第j站的上车乘客数与该时段的时段长度的比值；2kj2ktρ×⁄V。其中kjkTρ×V为第k时段从第j站上了同一车次的乘客数，因为乘客到站服从均匀分布，则kt2⁄V为第k时段乘客的平均等待时间。4.仿真研究根据3建立的目标函数。运用智能算法GA-TS进行公交车辆运营调度方案(公交车辆不同的发车间隔及类型反映着不同的调度方案)的研究.为了使仿真研究尽可能接近实际情况,这里通过性能指标函数式中的惩罚项的不同取值,来反映公交车辆在不同时段的实际运行环境.GA-TS群体规模取为60,单点交叉概率为Pc=0.75,变异概率为Pm=0.005,这里采用自然编码方式,全程车为0,快车为1,区间车为2[6-7].经仿真实验研究,结果如图4.1。图4.1混合遗传算法Fig4.1HybridGeneticAlgorithm以镇江市公交公司某车队4路运营线路为研究对象,其运营参数设定为：运营车辆发车间隔为8min,每站停靠时间为0.25min，每站间行驶时间为2.9min，为了便于运营调度的研究，本文在平峰时段进行仿真实验研究，这里仅取全程车、快车、区间车等3种类型构成36车次运营车辆，其中36车次中全程车占2/3、快车占1/6、区间车占1/6[8]。经仿真实验研究。最终得到36车次运营车辆编排结果(即调度方案)为000010021001002002001000020000100122。以上仿真结果可以看出，在采用8min发车间隔时，只需要13辆运营车辆就能够满足一次周转，计算出其周转时间为366.2998min。若投入18辆车，投入该运营调度方案编排，发车间隔只须5.5min即可满足要求。与原来通过经验采用的调度方案(使用18辆车，发车间隔8min，周转时间为385.4min)相比，现在采用的GA-TS中，周转时间节省了19.1min，减少了6辆车。结合3.3.2公式，求的总费用为3697.62元。因此，采用HGA优化算法能够合理分配公交车辆资源，有效调整供需平衡，极大地提高了运输效率[9]。5.结论采用最小费用作为目标函数,考虑了车辆配置、时间、运营效率及资源利用等方面因素,通过选择、交叉及变异等遗传操作,得到了最优的调度排序方案,仿真结果表明,利用GA-TS解决车辆调度问题具有可行性、先进性和快速性。本文创新点：本文将HGA引入到公交车辆运营调度管理中，利用HGA的智能化特征缩小搜索空间，尽快找到满意解，形成合理有效的调度方案。参考文献[1]LucB.andStefanS.GeneticAlgorithms：theoryandapplication[J].JournalA，1997，38（2）：13-23.[2]Barbarrosoglu，Gulay，Ozgur.TabuSearchAlgorithmfortheVehicleRoutingProblem.Computers&OperationsResearch，1999，26（3）：255-270.[3]ZhangDefu,DengAnsheng,Aneffectivehybridalgorithmfortheproblemofpackingcirclesintoalargercontainingcircle,ComputerandOperationsRearch,2005,32(8):1974-1951.[4]蔡延光，钱积新，孙优贤.智能运输调度系统的设计与实现[J].决策与决策系统支持，1996，6（4）：108-114.[5]石爱菊，周林．公交车优化调度中的几个问题的研究数学的实践与认识2002.3.[6]蔡延光，钱积新，孙优贤.智能运输调度系统的设计与实现[J].决策与决策系统支持，1996，6（4）：108-114.[7]GloverF