列车调度问题模型与基于混合粒子群优化的求解算法

摘要/Abstract

摘要：

针对复线列车调度问题，建立了描述问题解空间的阻塞限制混合流水车间模型，并提出一种混合粒子群优化算法进行求解。该算法以最小化最长完工时间为目标，设计了释放－回推算法来安排列车运行顺序并计算最小化最长完工时间，利用改进的粒子群优化算法解决轨道分配问题并进行全局优化。此外，通过基于迭代邻域的搜索算法来提高种群的局部搜索能力。实验结果表明，所提出的方法能够有效地求解复线列车调度问题。

关键词: 混合流水车间调度, 粒子群优化算法, 阻塞限制, 列车调度

Abstract:

A model of hybrid flow shop problem with blocking for describing the solution space was built for the train scheduling problem on double-track line, and a hybrid particle swarm optimization (HPSO) algorithm was proposed to solve it. With the objective of minimizing makespan, release-backstepping (RB) algorithm was put forward to sequence the running trains and calculate the minimizing makespan, while an improved particle swarm optimization algorithm was employed to solve track assignment problem and implement global optimization. Besides, an iterative neighborhood search algorithm was introduced to improve the local search ability of the particle swarm optimization algorithm.The experimental results show that the train scheduling problem on double-track lines can be solved effectively with the proposed method.

Key words: hybrid flow shop scheduling, particle swarm optimization algorithm, blocking, train scheduling

中图分类号:

张其亮1, 2, 陈永生1. 列车调度问题模型与基于混合粒子群优化的求解算法[J]. 中国机械工程, 2013, 24(14): 1916-1922.

ZHANG Ji-Liang-1, 2, CHEN Yong-Sheng-1. Train Scheduling Problem Model and Its Solution Based on Hybrid Particle Swarm Optimization Algorithm[J]. China Mechanical Engineering, 2013, 24(14): 1916-1922.

参考文献

[1]彭其渊,杨明伦.计算机编制复线实用货物列车运行图的整数规划模型及求解方法[J].中国铁道科学,1994,15(4):60-66.
[2]PengQiyuan,YangMinglun.TheIntegerProgrammingModelandItsSolutionforMakingDoubletrackTrainWorkingGraphwithComputer[J].ChinaRailwayScience,1994,15(4):60-66.
[3]ZhouXuesong,ZhongMing.BicriteriaTrainSchedulingforHigh-speedPassengerRailroadPlanningApplications[J].EuropeanJournalofOperationalResearch,2005,167(3):752-771.
[4]GuillermoCG,JoseM RL.HybridAlgorithmofTabuSearchandIntegerProgrammingfortheRailwayCrew SchedulingProblem[C]//Proceedingof2thAsia-PacificConferenceonComputationalIntelligence and Industrial Applications. Wuhan,2009:413-416.
[5]CapraraA,FischettiM,GuidaPL,etal.SolutionofReal- world Train TimetableProblems[C]//Proceedingsofthe34th HawaiiInternationalConferenceonSystemSciences.Maui,2001:1-10.
[6]ArianoA D,PacciarelliD,Pranzo M.A BranchandBound Algorithm forScheduling TrainsinaRailwayNetwork[J].EuropeanJournalofOperationalResearch,2007,183(2):643-657.
[7]BurdettRL,KozanE.ADisjunctiveGraphModelandFrameworkforConstructingNewTrainSchedules[J].EuropeanJournalofOperationalResearch,2010,200(1):85-98.
[8]LiuShiqiang,KozanE.SchedulingTrainsasaBlockingParallel-machineJobShopSchedulingProblem[J].Computersand Operations Research,2009,36(10):2840-2852.
[9]TormosP.AGeneticAlgorithmforRailwaySchedulingProblems[J].StudiesinComputationalIntelligence,2008,128(1):255-276.
[10]KhanMB,ZhangDianye,ShiJM,etal.AnIntelligentSearchTechniquetoTrainSchedulingProblemBasedonGeneticAlgorithm[C]//Proceedingof2ndInternationalConferenceonEmergingTechnologies.Peshawar,2006:593-598.
[11]NiShaoquan,Chen Dingjun,Lu Miaomiao.ResearchonOptimization ModelofInitialScheduleofPassengerTrainsBasedonImprovedGeneticAlgorithm[C]//ProceedingoftheSecondInternationalConferenceonIntelligent ComputationTechnologyand Automation.Washington D C,2009:273-276.
[12]Salim V,CaiXiaoqiang.A GeneticAlgorithmforRailwaySchedulingwithEnvironmentalConsiderations[J].EnvironmentalModelling & Software,1997,12(4):301-309.
[13]任苹[1],李楠[2],高立群[3].基于集成粒子群优化的复线旅客列车优化调度[J].系统仿真学报,2007,19(7):1449-1452.
[14]RenPing,LiNan,GaoLiqun.Bi-criteriaPassengerTrainsSchedulingOptimalPlanningBasedonIntegratedParticleSwarm Optimization[J].JournalofSystemSimulation,2007,19(7):1449-1452.
[15]王万良[1],姚明海[1],吴云高[1],吴启迪[2].基于遗传算法的混合Flow—shop调度方法[J].系统仿真学报,2002,14(7):863-865. 9
[16]WangWanliang,YaoMinghai,WuYungao.HybridFlow-shopSchedulingApproachBasedonGeneticAlgorithm[J].JournalofSystem Simulation,2002,14(7):863-869.
[17]OuWei,ZouFengxing,GaoZheng.FlexibleFlowshopSchedulingApproachBasedonHybridParticleSwarm Optimization[C]//Proceedingsof2008Controland Decision Conference.Yantai,2008:1013-1018.
[18]周辉仁[1],唐万生[1],魏颖辉[2].基于微粒群算法的柔性流水车间调度优化[J].中国机械工程,2010(9):1053-1057.
[19]Zhou Huiren,Tang Wansheng,Wei Yinghui.PSO-basedOptimizationofFlexibleFlow-shopScheduling[J].China Mechanical Engineering,2010,21(9):1053-1056.