基于网格的遗传算法及其在公交运行计划编制中的应用研究陈琛洪流陈学广郝语嘉（华中科技大学系统工程研究所武汉430074）摘要：本文利用基于网格的遗传算法解决城市公共交通运营中的运行计划编制问题。首先应用有序样本聚类算法对城市公交历史客流量样本数据进行数据挖掘，然后在综合考虑乘客待车成本和公交公司运营亏损等因素的前提下构造遗传算法的适应度函数、编码方式和约束条件，最后在网格平台上初始化算法种群，并分配不同的子种群到网格的各个集群、节点上并行的进行选择、交叉、变异及计算染色体的适应度等进化操作，同时以一定的规律在集群和集群、节点和节点之间交换优秀染色体，从而能快速得出满意的运行计划时刻表；通过仿真试验，证明了该方法的有效性和实时性。关键词：公共交通；有序样本聚类；遗传算法；网格；运行计划：TPResearchongrid-basedgeneticalgorithmanditsapplicationinpublictransportoperationplanschedulingChenChenLiuHongXueGuangChenYu激aHao（InstituteofSystemEngineering,HuazhongUniversityofScienceandTechnology,Wuhan,430074,P.R.China）Abstract:Tosolvetheproblemofpublictransportoperationplanscheduling,thispaperproposesagrid-basedgeneticalgorithm.Firstly,wedodatamininginthehistoricalpassengerflowsamplesofurbantransportationbyusingsequentialclusteralgorithm.Secondly,weconstructthefitnessfunction,codingmethodandconstraintconditionofgeneticalgorithmunderconsideringthecostofpassenger-waitingandoperatinglossofpublictransportcompany.Finally,weinitializethepopulationsontheGridplatform,andthendistributethesubpopulationstodifferentGridclustersandnodesforselection,crossover,andmutation,calculatethefitnessofchromosomeindiversedirectionssimultaneouslyandexchangetheexcellentchromosomebetweenclustersornodesinordertogetthesatisfactoryoperationplanquickly.Experimentsonrealdatademonstratethebenefitsofthemethod.Keywords:publictransport；sequentialcluster；geneticalgorithm；grid；operationplan１引言遗传算法是一类借鉴生物界的进化规律(适者生存，优胜劣汰的遗传机制)演化而来的随机化搜索方法。实践证明，运行计划编制优化模型是一个复杂的多目标规划问题，它必须兼顾乘客和公交公司双方的利益，在客流量规律、线路运行条件、公交公司运输能力和社会经济效益等约束条件下，优化公---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---收稿日期：最终修改稿收到日期：本课题得到国家自然科学基金（60773188）和武汉市科技计划（200710321090-2）资助．陈琛，男，1984年生，湖南人，博士生。主要研究方向：决策支持系统、信息系统工程、网格计算。E-mail：datocc37@126．洪流，男，1979年生，湖北人，博士,讲师。主要研究方向：决策支持系统、信息系统工程、网格计算等。E-mail：newtorrent@126．陈学广,男，1947年生，湖北人，教授，博士生导师。主要研究方向：决策支持系统、信息系统工程、网格计算等。E-mail：xgchen9@mail.hust.edu．郝语嘉，男，1985年生，湖北人，硕士研究生。主要研究方向：决策支持系统、网格计算。E-mail：yjhao2007@126．交车辆在各个时段的发车时刻，才能使得整个城市公交线路有规律有节奏的运行，但是随着公交网络规模的扩大，优化问题的搜索空间急剧扩张，利用常规方法寻找精确解已经是一件很难或者不可能完成的任务。因此，通常人们把精力放在寻求运行计划满意解的上面，而遗传算法则是寻求这种满意解的最佳工具。目前国内外许多学者都致力于这方面的研究。ChalesJ.Malmborg等[1]将遗传算法引入车辆调度系统中；ZhangFeizhou等[2]提出基于混合遗传算法的公交智能排班方法；J.Herrera等[3]提出了面向网格的遗传算法；2007年，D.Lim等[4]又提出了基于网格计算的多层并行遗传算法。在国内，时敬梁[5]，贾以霞等[6]对公交调度的遗传算法做了改进。孙传姣等[7]用遗传算法研究解决快速公交中的调度优化问题。上述工...