基于自适应遗传算法的城际列车运行图编制方法
|
摘要
对城际列车运行图编制问题进行研究,确定列车在各区间运行的最优顺序,并建立以列车总运行时间最小为目标的列车运行图优化模型。在此基础上,采用自适应选择机制的变异算子和交叉算子,设计一种自适应遗传算法进行求解。该算法采用"列车-区间运行顺序"的染色体二维编码形式,首先对列车在各区间运行的顺序进行编码;求解过程中,结合广度优先循环布线的原则进行解码,通过"到发时刻-发现冲突-解决冲突"逐区段进行铺画,得到列车在各车站实际的到发时刻;同时,利用自适应遗传算法进行全局优化,得到问题最优解。实验表明,自适应机制能够提高算法性能并较快得到列车最优运行顺序,铺画出更高效准确的列车运行图。
By studing the intercity train diagram generation problem, a model is built to describe its solution space, determine optimal traveling order of trains and minimum total train running time. New mutation operator and crossover operator are adopted, and a modified adaptive genetic algorithm is proposed. The algorithm adopts the two-dimensional coding form of "train-interval traveling order" which can firstly determine the traveling order of trains in each interval.The algorithm is combined with the principle of breadth-priority cyclic, which can schedule train through the step of "time determine, discovery conflict, solve it", determine the arrival and departure time of the train at each station. And then, the adaptive genetic algorithm is used for global optimization to obtain the best solution. Experiments show that the adaptive mechanism can improve the performance of the algorithm, get the best traveling order of the trains faster,and obtain a train diagram effectively.
By studing the intercity train diagram generation problem, a model is built to describe its solution space, determine optimal traveling order of trains and minimum total train running time. New mutation operator and crossover operator are adopted, and a modified adaptive genetic algorithm is proposed. The algorithm adopts the two-dimensional coding form of "train-interval traveling order" which can firstly determine the traveling order of trains in each interval.The algorithm is combined with the principle of breadth-priority cyclic, which can schedule train through the step of "time determine, discovery conflict, solve it", determine the arrival and departure time of the train at each station. And then, the adaptive genetic algorithm is used for global optimization to obtain the best solution. Experiments show that the adaptive mechanism can improve the performance of the algorithm, get the best traveling order of the trains faster,and obtain a train diagram effectively.
引文
[1] 胡思继. 列车运行图编制理论与方法[M]. 北京:中国铁道出版社, 2013.
[2] BARRENA E, CANCA D, COELHO L C, et al. Exact formulations and algorithm for the train timetabling problem with dynamic demand[J]. Computers & Operations Research, 2014,44(3):66-74.
[3] D’ARIANO A, PACCIARELLI D, PRANZO M. A branch and bound algorithm for scheduling trains in a railway network[J]. European Journal of Operational Research, 2007,183(2):643-657.
[4] 李得伟,丁世顺,张琦,等. 基于客流需求的城际列车时刻表模型改进研究[J]. 交通运输系统工程与信息, 2017,17(3):157-164.
[5] 廖正文,苗建瑞,孟令云,等. 基于拉格朗日松弛的双线铁路列车运行图优化算法[J]. 铁道学报, 2016,38(9):1-8.
[6] LEE Y, LU L S, WU M L , et al. Balance of efficiency and robustness in passenger railway timetables[J]. Transportation Research Part B: Methodological, 2017, 97:142-156.
[7] YAN F, GOVERDE R M P. Railway timetable optimization considering robustness and overtakings[C]// IEEE International Conference on Models & Technologies for Intelligent Transportation Systems. 2017:291-296.
[8] 许红,马建军,龙建成. 客运专线列车运行图编制模型及计算方法的研究[J]. 铁道学报, 2007,29(2):1-7.
[9] 白紫熙,邵静静,周磊山,等. 相同径路的高速列车运行图编制方法[J]. 中国铁道科学, 2015,36(6):135-140.
[10] 黄鉴,彭其渊. 基于分时客运需求的客运专线列车运行图优化[J]. 铁道科学与工程学报, 2012,9(6):66-71.
[11] 赵宏涛,苗义烽,王涛,等. 基于改进粒子群优化算法的鲁棒性列车运行图编制方法[J]. 中国铁道科学, 2013,34(3):116-121.
[12] 张其亮,陈永生. 列车调度问题模型与基于混合粒子群优化的求解算法[J]. 中国机械工程, 2013,24(14):1916-1922.
[13] JAMILI A, SHAFIA M A, SADJADI S J, et al. Solving a periodic single-track train timetabling problem by an efficient hybrid algorithm[J]. Engineering Applications of Artificial Intelligence, 2012,25(4):793-800.
[14] 李得伟,丁世顺. 基于改进的PESP模型编制高速铁路周期性列车运行图的研究[J]. 中国铁道科学, 2017(1):132-137.
[15] 李峰. 网络环境下单线列车运行图编制的优化算法研究[D]. 北京:北京交通大学, 2010.
[16] 周文梁,屈林影,史峰,等. 基于定序优化的高速铁路网络列车运行图优化[J]. 铁道科学与工程学报, 2018(3):551-558.
[17] 张小炳,倪少权,潘金山. 高速铁路列车运行图结构优化研究[J].西南交通大学学报, 2016,51(5):938-943.
[18] 陈钉均,王文宪. 铁路旅客列车运行图始发方案优化设计[J]. 计算机仿真, 2016,33(5):175-178.
[19] 文艺,潘大志. 用于求解TSP问题的改进遗传算法[J]. 计算机科学, 2016,43(S1):90-92.
[20] 王勇臻,陈燕,于莹莹.求解多旅行商问题的改进分组遗传算法[J]. 电子与信息学报, 2017,39(1):198-205.
[21] 杨从锐,钱谦,王锋,等. 改进的自适应遗传算法在函数优化中的应用[J]. 计算机应用研究, 2018(4):1042-1045.
[22] 李耀华,王磊. 基于改进遗传算法的飞机排班优化方法研究[J]. 系统仿真学报, 2016,28(3):620-626.
[2] BARRENA E, CANCA D, COELHO L C, et al. Exact formulations and algorithm for the train timetabling problem with dynamic demand[J]. Computers & Operations Research, 2014,44(3):66-74.
[3] D’ARIANO A, PACCIARELLI D, PRANZO M. A branch and bound algorithm for scheduling trains in a railway network[J]. European Journal of Operational Research, 2007,183(2):643-657.
[4] 李得伟,丁世顺,张琦,等. 基于客流需求的城际列车时刻表模型改进研究[J]. 交通运输系统工程与信息, 2017,17(3):157-164.
[5] 廖正文,苗建瑞,孟令云,等. 基于拉格朗日松弛的双线铁路列车运行图优化算法[J]. 铁道学报, 2016,38(9):1-8.
[6] LEE Y, LU L S, WU M L , et al. Balance of efficiency and robustness in passenger railway timetables[J]. Transportation Research Part B: Methodological, 2017, 97:142-156.
[7] YAN F, GOVERDE R M P. Railway timetable optimization considering robustness and overtakings[C]// IEEE International Conference on Models & Technologies for Intelligent Transportation Systems. 2017:291-296.
[8] 许红,马建军,龙建成. 客运专线列车运行图编制模型及计算方法的研究[J]. 铁道学报, 2007,29(2):1-7.
[9] 白紫熙,邵静静,周磊山,等. 相同径路的高速列车运行图编制方法[J]. 中国铁道科学, 2015,36(6):135-140.
[10] 黄鉴,彭其渊. 基于分时客运需求的客运专线列车运行图优化[J]. 铁道科学与工程学报, 2012,9(6):66-71.
[11] 赵宏涛,苗义烽,王涛,等. 基于改进粒子群优化算法的鲁棒性列车运行图编制方法[J]. 中国铁道科学, 2013,34(3):116-121.
[12] 张其亮,陈永生. 列车调度问题模型与基于混合粒子群优化的求解算法[J]. 中国机械工程, 2013,24(14):1916-1922.
[13] JAMILI A, SHAFIA M A, SADJADI S J, et al. Solving a periodic single-track train timetabling problem by an efficient hybrid algorithm[J]. Engineering Applications of Artificial Intelligence, 2012,25(4):793-800.
[14] 李得伟,丁世顺. 基于改进的PESP模型编制高速铁路周期性列车运行图的研究[J]. 中国铁道科学, 2017(1):132-137.
[15] 李峰. 网络环境下单线列车运行图编制的优化算法研究[D]. 北京:北京交通大学, 2010.
[16] 周文梁,屈林影,史峰,等. 基于定序优化的高速铁路网络列车运行图优化[J]. 铁道科学与工程学报, 2018(3):551-558.
[17] 张小炳,倪少权,潘金山. 高速铁路列车运行图结构优化研究[J].西南交通大学学报, 2016,51(5):938-943.
[18] 陈钉均,王文宪. 铁路旅客列车运行图始发方案优化设计[J]. 计算机仿真, 2016,33(5):175-178.
[19] 文艺,潘大志. 用于求解TSP问题的改进遗传算法[J]. 计算机科学, 2016,43(S1):90-92.
[20] 王勇臻,陈燕,于莹莹.求解多旅行商问题的改进分组遗传算法[J]. 电子与信息学报, 2017,39(1):198-205.
[21] 杨从锐,钱谦,王锋,等. 改进的自适应遗传算法在函数优化中的应用[J]. 计算机应用研究, 2018(4):1042-1045.
[22] 李耀华,王磊. 基于改进遗传算法的飞机排班优化方法研究[J]. 系统仿真学报, 2016,28(3):620-626.