基于差分进化算法的动车组周转接续优化研究
|
摘要
为解决高速铁路动车组周转接续优化问题,提出一种置换策略差分进化算法。针对该算法,采用正整数排列建立车站终到列车-始发列车接续对,作为算法的初始个体;利用产生相邻交换次数最佳的随机冒泡排序算法,对差分变异算子进行设计;在算法进化过程中,基于二项式交叉策略,随机选择个体的交叉点,进行部分基因交换;同时引入一定选择概率的贪婪选择策略,提高算法求出动车组最优周转接续时间的有效性。结合武广客运专线长沙站实例的数值仿真实验结果表明,差分进化算法可以获得更好的收敛性能和求解质量,得到动车组周转优化方案。
To solve the problem of turnaround continuity optimization for high-speed railway EMUs, a permutation strategy differential evolution algorithm is proposed in this paper. In view of this algorithm, positive integer permutation is used to establish the terminal train-departure train connection pair as the initial individual of the algorithm. The differential mutation operator is designed with a randomized bubble sorting algorithm which produces the best number of adjacent exchanges. In the process of algorithm evolution, based on the binomial cross strategy,the crossover points of individuals are randomly selected for partial gene exchange. At the same time, a greedy selection strategy with a certain selection probability is introduced to improve the effectiveness of the algorithm in finding the optimal switching time of EMU. The numerical simulation results of Changsha Station on Wuhan-Guangzhou passenger dedicated line show that the differential evolution algorithm can obtain better convergence as well as the result quality, and get the optimal scheme of EMU turnaround.
To solve the problem of turnaround continuity optimization for high-speed railway EMUs, a permutation strategy differential evolution algorithm is proposed in this paper. In view of this algorithm, positive integer permutation is used to establish the terminal train-departure train connection pair as the initial individual of the algorithm. The differential mutation operator is designed with a randomized bubble sorting algorithm which produces the best number of adjacent exchanges. In the process of algorithm evolution, based on the binomial cross strategy,the crossover points of individuals are randomly selected for partial gene exchange. At the same time, a greedy selection strategy with a certain selection probability is introduced to improve the effectiveness of the algorithm in finding the optimal switching time of EMU. The numerical simulation results of Changsha Station on Wuhan-Guangzhou passenger dedicated line show that the differential evolution algorithm can obtain better convergence as well as the result quality, and get the optimal scheme of EMU turnaround.
引文
[1]余晓园,王莹,李元凯.高速铁路列车开行模式对动车组运用的影响研究[J].铁道运输与经济,2016,38(7):1-6.YU Xiaoyuan,WANG Ying,LI Yuankai.Study on Influence of High-Speed Railway Train Operation Mode on Utilization of EMU[J].Railway Transport and Economy,2016,38(7):1-6.
[2]彭其渊,闫海峰,文超.高速铁路运输组织基础[M].成都:西南交通大学出版社,2009.
[3]李世彪.提高侯马北站运输效率的思考[J].铁道货运,2016,36(2):18-22.LI Shibiao.Thoughts on Increasing Transport Efficiency of Houma North Station[J].Railway Freight Transport,2016,36(2):18-22.
[4]史峰,周文梁,郁宇卫,等.客运专线动车组运用计划优化模型与算法[J].铁道学报,2011,33(1):8-13.SHI Feng,ZHOU Wenliang,YU Yuwei,et al.Optimized Model and Algorithm of Motor Train-sets Scheduling for Dedicated Passenger Lines[J].Journal of the China Railway Society,2001,33(1):8-13.
[5]赵鹏,杨浩,胡安洲.高速铁路动车组的不固定区段使用问题[J].铁道学报,1997,19(2):15-19.ZHAO Peng,YANG Hao,HU Anzhou.Research on Usage of High-Speed Passenger Trains on Uncertain Railroad Region[J].Journal of the China Railway Society,1997,19(2):15-19.
[6]赵鹏,富井规雄.基于概率局域搜索的动车组平日运用计划编制算法[J].系统工程理论与实践,2004,24(2):123-129.ZHAO Peng,NORIO Tomii.An Algorithm for Trainset Scheduling on Weekday based on Probabilistic Local Search[J].System Engineering-Theory&Practice,2004,24(2):123-129.
[7]王莹,刘军,苗建瑞.基于运行线可调的动车组周转计划优化研究[J].中国铁道科学,2012,33(4):112-119.WANG Ying,LIU Jun,MIAO Jianrui.Optimization of the Circulation Plan for Multiple Units based on Adjustable Train Path[J].China Railway Science,2012,33(4):112-119.
[8]王文宪,柏伟.基于蚁群算法的动车组周转计划研究[J].交通运输工程与信息学报,2012,10(3):102-105.WANG Wenxian,BAI Wei.Research on Train Set Scheduling based on Ant Colony Algorithm[J].Journal of Transportation Engineering and Information,2012,10(3):102-105.
[9]陈然,周磊山,乐逸祥,等.基于专家系统的网络化动车组运用计划的编制[J].中国铁道科学,2016,37(1):108-116.CHEN Ran,ZHOU Leishan,YUE Yixiang,et al.Network EMU Scheduling based on Expert System[J].China Railway Science,2016,37(1):108-116.
[10]STORN R,PRICE K.Differential Evolution-A Simple and Efficient Heuristic for global Optimization over Continuous Spaces[J].Journal of Global Optimization,1997,11(4):341-359.
[11]PAN Q K,WANG L,QIAN B.A Novel Differential Evolution Algorithm for Bi-criteria No-wait Flow Shop Scheduling Problems[J].Computers&Operations Research,2009,36(36):2498-2511.
[12]ONWUBOLU G C,DAVENDRA D.Differential Evolution:A Handbook for Global Permutation-based Combinatorial Optimization[M].Berlin Heidelberg:Springer,2009.
[13]SANTUCCI V,BAIOLETTI M,MILANI A.A Differential Evolution Algorithm for the Permutation Flowshop Scheduling Problem with Total Flow Time Criterion[J].IEEE Transactions on Evolutionary Computation,2015,20(8):162-170.
[14]苏兆品,张国富,蒋建国,等.基于非支配排序差异演化的应急资源多目标分配算法[J].自动化学报,2016,43(2):195-214.SU Zhaopin,ZHANG Guofu,JIANG Jianguo,et al.Multiobjective Approach to Emergency Resource Allocation Using None-dominated Sorting Based Differential Evolution[J].Acta Automatica Sinica,2016,43(2):195-214.
[15]WU L,WANG Y,ZHOU S,et al.Self-adapting Control Parameters Modified Differential Evolution for Trajectory Planning of Manipulators[J].Control Theory and Technology,2007,5(4):365-373.
[16]李华.铁路动车组运用计划编制理论与方法研究[D].北京:北京交通大学,2013.
[2]彭其渊,闫海峰,文超.高速铁路运输组织基础[M].成都:西南交通大学出版社,2009.
[3]李世彪.提高侯马北站运输效率的思考[J].铁道货运,2016,36(2):18-22.LI Shibiao.Thoughts on Increasing Transport Efficiency of Houma North Station[J].Railway Freight Transport,2016,36(2):18-22.
[4]史峰,周文梁,郁宇卫,等.客运专线动车组运用计划优化模型与算法[J].铁道学报,2011,33(1):8-13.SHI Feng,ZHOU Wenliang,YU Yuwei,et al.Optimized Model and Algorithm of Motor Train-sets Scheduling for Dedicated Passenger Lines[J].Journal of the China Railway Society,2001,33(1):8-13.
[5]赵鹏,杨浩,胡安洲.高速铁路动车组的不固定区段使用问题[J].铁道学报,1997,19(2):15-19.ZHAO Peng,YANG Hao,HU Anzhou.Research on Usage of High-Speed Passenger Trains on Uncertain Railroad Region[J].Journal of the China Railway Society,1997,19(2):15-19.
[6]赵鹏,富井规雄.基于概率局域搜索的动车组平日运用计划编制算法[J].系统工程理论与实践,2004,24(2):123-129.ZHAO Peng,NORIO Tomii.An Algorithm for Trainset Scheduling on Weekday based on Probabilistic Local Search[J].System Engineering-Theory&Practice,2004,24(2):123-129.
[7]王莹,刘军,苗建瑞.基于运行线可调的动车组周转计划优化研究[J].中国铁道科学,2012,33(4):112-119.WANG Ying,LIU Jun,MIAO Jianrui.Optimization of the Circulation Plan for Multiple Units based on Adjustable Train Path[J].China Railway Science,2012,33(4):112-119.
[8]王文宪,柏伟.基于蚁群算法的动车组周转计划研究[J].交通运输工程与信息学报,2012,10(3):102-105.WANG Wenxian,BAI Wei.Research on Train Set Scheduling based on Ant Colony Algorithm[J].Journal of Transportation Engineering and Information,2012,10(3):102-105.
[9]陈然,周磊山,乐逸祥,等.基于专家系统的网络化动车组运用计划的编制[J].中国铁道科学,2016,37(1):108-116.CHEN Ran,ZHOU Leishan,YUE Yixiang,et al.Network EMU Scheduling based on Expert System[J].China Railway Science,2016,37(1):108-116.
[10]STORN R,PRICE K.Differential Evolution-A Simple and Efficient Heuristic for global Optimization over Continuous Spaces[J].Journal of Global Optimization,1997,11(4):341-359.
[11]PAN Q K,WANG L,QIAN B.A Novel Differential Evolution Algorithm for Bi-criteria No-wait Flow Shop Scheduling Problems[J].Computers&Operations Research,2009,36(36):2498-2511.
[12]ONWUBOLU G C,DAVENDRA D.Differential Evolution:A Handbook for Global Permutation-based Combinatorial Optimization[M].Berlin Heidelberg:Springer,2009.
[13]SANTUCCI V,BAIOLETTI M,MILANI A.A Differential Evolution Algorithm for the Permutation Flowshop Scheduling Problem with Total Flow Time Criterion[J].IEEE Transactions on Evolutionary Computation,2015,20(8):162-170.
[14]苏兆品,张国富,蒋建国,等.基于非支配排序差异演化的应急资源多目标分配算法[J].自动化学报,2016,43(2):195-214.SU Zhaopin,ZHANG Guofu,JIANG Jianguo,et al.Multiobjective Approach to Emergency Resource Allocation Using None-dominated Sorting Based Differential Evolution[J].Acta Automatica Sinica,2016,43(2):195-214.
[15]WU L,WANG Y,ZHOU S,et al.Self-adapting Control Parameters Modified Differential Evolution for Trajectory Planning of Manipulators[J].Control Theory and Technology,2007,5(4):365-373.
[16]李华.铁路动车组运用计划编制理论与方法研究[D].北京:北京交通大学,2013.