基于改进遗传—模拟退火算法的公交排班优化研究.pdf

第29卷第7期计算机应用研究Vo1．29No．7
2012年7月ApplicationResearchofComputersJu1．2012

基于改进遗传一模拟退火算法的公交排班优化研究

王庆荣，袁占亭，张秋余
(1．兰州交通大学电子与信息工程学院，兰州730070；2．兰州理工大学电气工程与信息工程学院，兰州730050)

摘要：结合公交车辆调度自身的特点，兼顾公交公司与乘客双方的利益，建立了公交排班优化模型，以发车时
刻为基因变量进行编码，对两个相邻的发车间隔之差、最大最小发车时间间隔、乘客的满载率等条件进行约束限
制，提出了基于改进的遗传一模拟退火算法；对该模型进行优化求解，克服了传统优化算法的缺陷，提高了优化
设计过程的求解效率。通过仿真实验得到了利用改进的遗传一模拟退火算法进行求解的不均匀发车时刻表。
结果表明，改进的遗传一模拟退火算法能够在公交智能排班优化问题的巨大搜索空间中可靠地找到近似最优
解，大大提高了计算效率。
关键词：公共交通；公交调度；行车时刻表；遗传一模拟退火算法；适应度函数
中图分类号：TP301．6文献标志码：A文章编号：1001-3695(2012)07-2461-03
doi：10．3969／j．issn．1001-3695．2012．07．016

Studyontransitschedulingoptimizationbasedonimproved
genetic—simulatedannealingalgorithm

WANGQing—rong’，YUANZhan—ting2，ZHANGQiu-yu
(1．SchoolofElectronic＆InformationEngineering，LanzhouJiaotongUniversity，Lanzhou730070，China；2．SchoolofElectrical＆坳0一
tionEngi~enng，LanzhouUniversityofTechnology，Lanzhou~730050，China)

Abstract：Incombinationofthecharacteristicofpublictrafficvehicles’scheduling，establishedtheoptimizationmodelof
publictransportationvehicles’scheduling，givingattentiontothebenefitsofpassengersandcompanies．Adoptingthecoding
methodusingdepartingtimeasgenevariable，thispaperproposedtheimprovedgenetic-simulatedannealingalgorithmbyim—
posingtheconstraintsonthetimedifferencebetweenthetwobusheadways，themaximumandtheminimumofthebushead-
way，andpassengerloadrate．Itadoptedthealgorithmtofindsolutionofthemodelwhichovercametheadvantagesoftradi—
tionaloptimizationalgorithms，improvedthesolvingeficiency．Finally，itobtainedthesimulationresultsbyusingtheim—
provedgenetic-simulatedannealingalgorithmforsolvingthenon-uniformgridscheduling．Resultsshowthattheimprovedge—
netic—simulatedannealingalgorithmcanfindtheapproximatebestresultinthehugesearchspaceofoptimization，whilegreatly
increasesthecomputationalefficiency．
Keywords：publictraffic；publictrafficvehicles’scheduling；departingscheduling；genetic—simulatedannealingalgorithm；
6tnesslnction

公交排班问题是城市公交调度的核心内容，是公交调度人发车时刻表。行车时刻表的编制应是在满足客流需求的前提
员、司乘人员进行工作以及公交车辆正常运行的基本依据，也下，尽量减少不必要的投入。
是公交企业对社会