客运专线动车组运用计划优化研究
|
摘要
动车组运用计划是客运专线的基本运营计划之一,包括动车组的运用时间、担当列车、始发终到车站、运行径路、各级检修等内容。由于动车组购置费用和维修费用都较高,因此如何合理使用动车组,减少动车组的使用数量,提高动车组的使用效率,对于客运专线运营管理具有重要意义。目前我国客运专线运营管理和动车组运用尚处于探索阶段,同时在动车组运用模式、管理模式、检修规程等方面与欧洲、日本等高速铁路发达国家存在较大差异,因此不能完全照搬国外动车组运用计划编制方法,必须结合我国自身的特点对其进行研究。
本文首先对现有国内外关于编制动车组运用计划的研究成果进行了系统总结,对动车组运用计划的含义和种类进行了概括,结合我国客运专线的国情和路情分析了影响动车组运用计划编制的几个主要因素。将动车组使用数量最少这-主要优化目标转化为运用网络上的总接续费用最少,建立了动车组运用计划与维修计划的一体化优化模型。该模型通过设置动车组接续变量和检修周期相关变量将运用计划和检修计划进行整体优化,与其它优化方法相比更具合理性,更能反映实际使用情况。并将优化模型转化为等价的求解模型,通过惩罚函数的形式将一部分约束条件转化为目标函数的一部分,对模型进行了简化。根据问题的特殊性,选用模拟退火算法,设计了基于三交换邻域结构的模拟退火算法,针对某客运专线列车运行图,编制了动车组运用计划,结果较为满意。
本文研究的动车组运用计划优化模型以及求解算法对于实际的动车组运用计划编制具有一定的现实意义和理论价值。
The Motor Tran-sets Scheduling is an important part of the basic operation planning of the dedicated passenger traffic line, it is composed of the operation time of the train,the train number of every motor train-sets, the departure and the arrival station, the train route,the various classes of the inspection and repair for trains and so on.Because of the high buying cost and maintenance costs, the Motor Tran-sets Scheduling aims at using the train rationally to reduce the total number of the train and improve the train using efficiency, and also it is of great significance to the operation management of the dedicated passenger traffic line.Recently, the operation management of the dedicated passenger traffic line and the use of the motor train-sets of our country are still placed in the exploring stage, and the operating mode of the dedicated passenger traffic line, the management mode, the status of the railway network and the maintenance specification of the motor train-sets are different from the other developed countries',so we can not just simply use their modes for reference.So it is ought to combine with our own actual facts to do research.
With the comprehensive summarize of the domestic and foreign research results, the thesis generalizes the definition and the types of the Motor Tran-sets Scheduling, analyzes the key influencing factors based on our special national conditions and special railway conditions, and then does the further research on the basis of the operated network which constructed by the predecessors.The thesis translates the minimum using number of the motor train-sets into the minimum connecting costs in the motor train-sets operational network, and then the integrated optimal model which concerning the operation planning and inspection planning has been established. In the integrated optimal model,by setting the train connecting variable and the inspection and repair period correlative sequence variable, it unites the operation plan and the inspection and repair plan together, and with this characteristic, this optimal model can reflect the actual usage patterns better than other models.Then the optimal model has been translated into the equivalent solving model,by setting the penalty function and translating parts of the constraint conditions into the object function, the equivalent solving model simplifies the integrated model.Finally the thesis proposes the Simulated Annealing(SA) algorithm which is based on the 3-opt neighborhood structure for solving an actual problem, draws the motor train-sets scheduling for the train diagram, and the result is satisfactory.
The optimal model and solution algorithm in this thesis have certain realism significance and theory value for actual problem.
本文首先对现有国内外关于编制动车组运用计划的研究成果进行了系统总结,对动车组运用计划的含义和种类进行了概括,结合我国客运专线的国情和路情分析了影响动车组运用计划编制的几个主要因素。将动车组使用数量最少这-主要优化目标转化为运用网络上的总接续费用最少,建立了动车组运用计划与维修计划的一体化优化模型。该模型通过设置动车组接续变量和检修周期相关变量将运用计划和检修计划进行整体优化,与其它优化方法相比更具合理性,更能反映实际使用情况。并将优化模型转化为等价的求解模型,通过惩罚函数的形式将一部分约束条件转化为目标函数的一部分,对模型进行了简化。根据问题的特殊性,选用模拟退火算法,设计了基于三交换邻域结构的模拟退火算法,针对某客运专线列车运行图,编制了动车组运用计划,结果较为满意。
本文研究的动车组运用计划优化模型以及求解算法对于实际的动车组运用计划编制具有一定的现实意义和理论价值。
The Motor Tran-sets Scheduling is an important part of the basic operation planning of the dedicated passenger traffic line, it is composed of the operation time of the train,the train number of every motor train-sets, the departure and the arrival station, the train route,the various classes of the inspection and repair for trains and so on.Because of the high buying cost and maintenance costs, the Motor Tran-sets Scheduling aims at using the train rationally to reduce the total number of the train and improve the train using efficiency, and also it is of great significance to the operation management of the dedicated passenger traffic line.Recently, the operation management of the dedicated passenger traffic line and the use of the motor train-sets of our country are still placed in the exploring stage, and the operating mode of the dedicated passenger traffic line, the management mode, the status of the railway network and the maintenance specification of the motor train-sets are different from the other developed countries',so we can not just simply use their modes for reference.So it is ought to combine with our own actual facts to do research.
With the comprehensive summarize of the domestic and foreign research results, the thesis generalizes the definition and the types of the Motor Tran-sets Scheduling, analyzes the key influencing factors based on our special national conditions and special railway conditions, and then does the further research on the basis of the operated network which constructed by the predecessors.The thesis translates the minimum using number of the motor train-sets into the minimum connecting costs in the motor train-sets operational network, and then the integrated optimal model which concerning the operation planning and inspection planning has been established. In the integrated optimal model,by setting the train connecting variable and the inspection and repair period correlative sequence variable, it unites the operation plan and the inspection and repair plan together, and with this characteristic, this optimal model can reflect the actual usage patterns better than other models.Then the optimal model has been translated into the equivalent solving model,by setting the penalty function and translating parts of the constraint conditions into the object function, the equivalent solving model simplifies the integrated model.Finally the thesis proposes the Simulated Annealing(SA) algorithm which is based on the 3-opt neighborhood structure for solving an actual problem, draws the motor train-sets scheduling for the train diagram, and the result is satisfactory.
The optimal model and solution algorithm in this thesis have certain realism significance and theory value for actual problem.
引文
[1]铁道部.中长期铁路规划调整(2008年调整).2008.
[2]史峰.最优化理论与方法[M].
[3]符卓.优化车底使用数的客车运行方案图编制方法.铁道学报,1996,18(6)：69-74.
[4]铁道科学研究院.现代铁路大型客运站成套技术研究.北京：铁道科学研究院,2007.
[5]彭其渊,魏德勇,闰海峰.客运专线运输组织.北京：科学出版社,2006.
[6]何华武,等.德、法、西班牙三国铁路动车组运用维修设施考察报告.北京：铁道部,2000.
[7]铁道科学研究院井白林中央火车站列车作业时间及相关分析。北京：铁道科学研究院,2007.
[8]陈春阳等.中德合作项目铁路提速技术培训考察报告.北京：铁道部,2002.
[9]KIMKyun, in, HONGSoonheum. An Approach to the KTX Routing Problem. China-Korea-Jap Railway Research Technical Meeting. China Academy of Railway Sciences, Beijing, China,2006:143-148.
[10]Yu-Hern Chang, Chung-Hsing Yeh, Ching-Cheng Shen. A Multiobjective model for passenger train services planning:application to Taiwan's high-speed rail line. Transportation Research Part B,2000:91-106.
[11]史峰,胡安洲.机车周转图的线性配置算法.铁道学报,1996(4),18-24.
[12]闫海峰,崔焱.编制机车周转图的优化模型.中国铁道科学第27卷,第4期2006,(4)123-128.
[13]赵鹏,胡安洲,杨浩.高速铁路动车组的不固定区段使用问题[J].铁道学报,1997,19(2)：15-19.
[14]赵鹏,胡安洲,杨浩.高速铁路动车组不固定区段使用条件下周转优化问题的研究[J].北方交通大学学报,1997,21(6)：621-624.
[15]赵鹏.高速铁路动车组和乘务员运用的研究[D].北方交通大学博士学位论文,1998.
[16]聂磊,赵鹏,杨浩,胡安洲.高速铁路动车组运用的研究[J].铁道学报,2001,23(3)：1-7.
[17]赵鹏,富井规雄.动车组运用计划及其编制算法.铁道学报,2003,25(3)： 1-7.
[18]赵鹏,富井规雄.基于概率局域搜索的动车组平日运用计划算法.系统工程理论与实践,2004,24(2)：123-129.
[19l]赵鹏,富井规雄.基于路段交换的多基地动车组运用计划的编制算法.铁道学报,2004,26(1)：7-11.
[20]张杰,陈韬,施福根.客运专线动车组运用计划的计算机编制.西南交通大学报,2006,41(5)：635-639.
[21]耿敬春,肖荣国,倪少权,牛会想.客运专线动车组周期性运用计划编制的研究[J].铁道学报,2006,28(4)：17-21.
[22]陈华群,唐协.基于匈牙利算法的高速动车组周转模型及算法的研究[J].西南民族大学学报.自然科学版,2005,31(5)：779-782.
[23]杨军,杨浩,卢海波.遗传算法在动车组周转优化模型中的应用[J].铁道运输与经济,2004,26(7)：65-67.
[24]陈华群,唐协.应用神经网络优化高速铁路动车组周转的研究[J].中国安全生产科学技术,2006,2(2)：46-49.
[25]陈华群.动车组运用计划编制系统相关问题研究.西南交通大学硕士学位论文,2007.
[26]铁道科学研究院.京津城际客运专线列车运行仿真模拟.铁道科学研究院,2007.
[27]沈志军.客运专线动车组运用检修设施设置原则的探讨.铁道机车车辆,2006,26(2)：1-3.
[28]刘娜,孙晚华.铁路客运检修基地合理布局的研.铁路运输与经济,2006,28(9)：66-68.
[29]玄光男,程润伟.遗传算法与工程优化.北京：清华大学出版社,2004.
[30]D.J. Reid. Genetic algorithms in constrained optimization. Mathematical and Computer Modelling.1996,87-111.
[31]Lothar M.Schmitt*,Chrystopher L. Nehaniv, Robert H.Fujii.Linear analysis of genetic algorithms.Theoretical Computer Science,1998,(200)101-134.
[32]Michel Gendreau, Gilbert Laporte, Frederic Semet.A tabu search heuristic for the undirected selective travelling salesman problem. European Journal of Operational Research,1998,(106)539-545.
[33]刑文训,谢金星.现代优化计算方法.北京：清华大学出版社,2005.
[34]Klaus Meer.Simulated Annealing versus Metropolis for a TSP instance. Information Processing Letters,2007,(104) 216-219.
[35]吴艳群,董鹏.求解大规模不对称指派问题的通用模拟退火算法兰州交通 大学学报.2008,27(4)：39-45.
[36]Aybars Ugur, Dogan Aydin. An interactive simulation and analysis software for solving TSP using Ant Colony Optimization algorithms.Advances in Engineering Software,2009,(40)341-349.
[37]Jinhui Yang, Xiaohu Shi,Maurizio Marchese, Yanchun Liang. An ant colony optimization method for generalized TSP problem.Progress in Natural Science,2008, (18)1417-1422.
[38]段海滨.蚁群算法原理及其应用.北京：科学出版社,2005.
[39]Manli Li,Zhang Yi, Min Zhu. Solving TSP by using Lotka-Volterra neural networks.Neurocomputing,2009,(72) 3873-3880.
[40]Kate A.Smith,David Abramson, David Duke. Hopfield neural networks for timetabling:formulations, methods, and comparative results.Computers & Industrial Engineering, Volume 2003,44(2)283-305.
[41]韩力群.人工神经网络理论、设计及应用.北京：化学工业出版社,2007.
[42]冯伍.基本机车周转图算法及其原理[D].西南交通大学硕士论文,2006.
[43]刘领兵,吕红霞,陈广秀.多端点不成对机车周转图模型与算法[J].交通运输系统工程与信息.2006,4(3)：106-109.
[44]孙宏,杜文.航空公司飞机排班问题的分阶段指派算法[J].系统工程学报,2003,18(2)：168-172.
[45]朴爱华,胡安洲.我国高速铁路列车运行组织问题的研究[J].铁道学报,1997,18(3)：105-111.
[46]时颢.我国高速铁路列车运行图采用模式的分析[J].铁道学报,2000,22(1)：92-97.
[47]夏阳.客运专线运输组织相关问题研究[D].西南交通大学硕士论文,2003.
[48]汪波,杨浩,张志华.基于周期运行图的京津城际铁路列车开行方案研究[J].铁道学报,2007,29(2)：8-13
[49]梁栋,林柏梁.铁路空车调配的多阶段策略优化模型研究[J].铁道学报,2007,29(1)：1-6.
[50]王相平.客运专线动车组运用计划研究研[D].兰州交通大学硕士论文,2007.
[51]刘殿仁,李得伟,刘启钢.我国客运专线发展模式探讨[J].中国铁路,2005(1)：25-26.
[52]刘丽影,刘继刚,刘继.我国高速动车组检修制度[J].同济大学学报,2001,29(8)：1000-1003.
[53]Michael R. Bussieck, Peter Kreuzer, Uwe T. Zimmermann. Optimal lines for railway systems. European Journal of Operational Research.1996 (96):54-63.
[54]Keivan Ghoseiri,Ferenc Szidarovszky, Mohammad Jawad Asgharpour. A multi-objective train scheduling model and solution[J].Transportation Research Part B. 2004(38):927-952.
[55]Pieter-Jan Fioole, Leo Kroon, Gabor Maroti,Alexander Schrijver. A rolling stock circulation model for combining and splitting of passenger trains[J].European Journal of Operational Research.2006,(174):1281-1297.
[56]Marc Peeters, Leo Kroon. Circulation of railway rolling stock:a branch-and-price approach[J].Computers & Operations Research.2008,(35):538-556.
[57]Balachandran Vaidyanathan, Ravindra K. Ahuja, Jian Liu, Larry A.Shughart. Real-life locomotive planning:New formulationsand computational results. Transportation Research Part B.2008 (42):147-168.
[58]Mohamed Haouari, Najla Aissaoui,Farah Zeghal Mansour. Network flow-based approaches for integrated aircraft fleeting and routing.European Journal of Operational Research. (2007):1-9.
[59]Daeki Kim, Cynthia Barnhart. Flight schedule design for a charter airline. Computers & Operations Research.2007(34):1516-1531.
[60]肖龙文.最优机车周转图的自动化铺划.长沙铁道学院学报.1999,17(1)：52-57.
[6]]王甦男.旅客运输[M].中国铁道出版社.2003.
[2]史峰.最优化理论与方法[M].
[3]符卓.优化车底使用数的客车运行方案图编制方法.铁道学报,1996,18(6)：69-74.
[4]铁道科学研究院.现代铁路大型客运站成套技术研究.北京：铁道科学研究院,2007.
[5]彭其渊,魏德勇,闰海峰.客运专线运输组织.北京：科学出版社,2006.
[6]何华武,等.德、法、西班牙三国铁路动车组运用维修设施考察报告.北京：铁道部,2000.
[7]铁道科学研究院井白林中央火车站列车作业时间及相关分析。北京：铁道科学研究院,2007.
[8]陈春阳等.中德合作项目铁路提速技术培训考察报告.北京：铁道部,2002.
[9]KIMKyun, in, HONGSoonheum. An Approach to the KTX Routing Problem. China-Korea-Jap Railway Research Technical Meeting. China Academy of Railway Sciences, Beijing, China,2006:143-148.
[10]Yu-Hern Chang, Chung-Hsing Yeh, Ching-Cheng Shen. A Multiobjective model for passenger train services planning:application to Taiwan's high-speed rail line. Transportation Research Part B,2000:91-106.
[11]史峰,胡安洲.机车周转图的线性配置算法.铁道学报,1996(4),18-24.
[12]闫海峰,崔焱.编制机车周转图的优化模型.中国铁道科学第27卷,第4期2006,(4)123-128.
[13]赵鹏,胡安洲,杨浩.高速铁路动车组的不固定区段使用问题[J].铁道学报,1997,19(2)：15-19.
[14]赵鹏,胡安洲,杨浩.高速铁路动车组不固定区段使用条件下周转优化问题的研究[J].北方交通大学学报,1997,21(6)：621-624.
[15]赵鹏.高速铁路动车组和乘务员运用的研究[D].北方交通大学博士学位论文,1998.
[16]聂磊,赵鹏,杨浩,胡安洲.高速铁路动车组运用的研究[J].铁道学报,2001,23(3)：1-7.
[17]赵鹏,富井规雄.动车组运用计划及其编制算法.铁道学报,2003,25(3)： 1-7.
[18]赵鹏,富井规雄.基于概率局域搜索的动车组平日运用计划算法.系统工程理论与实践,2004,24(2)：123-129.
[19l]赵鹏,富井规雄.基于路段交换的多基地动车组运用计划的编制算法.铁道学报,2004,26(1)：7-11.
[20]张杰,陈韬,施福根.客运专线动车组运用计划的计算机编制.西南交通大学报,2006,41(5)：635-639.
[21]耿敬春,肖荣国,倪少权,牛会想.客运专线动车组周期性运用计划编制的研究[J].铁道学报,2006,28(4)：17-21.
[22]陈华群,唐协.基于匈牙利算法的高速动车组周转模型及算法的研究[J].西南民族大学学报.自然科学版,2005,31(5)：779-782.
[23]杨军,杨浩,卢海波.遗传算法在动车组周转优化模型中的应用[J].铁道运输与经济,2004,26(7)：65-67.
[24]陈华群,唐协.应用神经网络优化高速铁路动车组周转的研究[J].中国安全生产科学技术,2006,2(2)：46-49.
[25]陈华群.动车组运用计划编制系统相关问题研究.西南交通大学硕士学位论文,2007.
[26]铁道科学研究院.京津城际客运专线列车运行仿真模拟.铁道科学研究院,2007.
[27]沈志军.客运专线动车组运用检修设施设置原则的探讨.铁道机车车辆,2006,26(2)：1-3.
[28]刘娜,孙晚华.铁路客运检修基地合理布局的研.铁路运输与经济,2006,28(9)：66-68.
[29]玄光男,程润伟.遗传算法与工程优化.北京：清华大学出版社,2004.
[30]D.J. Reid. Genetic algorithms in constrained optimization. Mathematical and Computer Modelling.1996,87-111.
[31]Lothar M.Schmitt*,Chrystopher L. Nehaniv, Robert H.Fujii.Linear analysis of genetic algorithms.Theoretical Computer Science,1998,(200)101-134.
[32]Michel Gendreau, Gilbert Laporte, Frederic Semet.A tabu search heuristic for the undirected selective travelling salesman problem. European Journal of Operational Research,1998,(106)539-545.
[33]刑文训,谢金星.现代优化计算方法.北京：清华大学出版社,2005.
[34]Klaus Meer.Simulated Annealing versus Metropolis for a TSP instance. Information Processing Letters,2007,(104) 216-219.
[35]吴艳群,董鹏.求解大规模不对称指派问题的通用模拟退火算法兰州交通 大学学报.2008,27(4)：39-45.
[36]Aybars Ugur, Dogan Aydin. An interactive simulation and analysis software for solving TSP using Ant Colony Optimization algorithms.Advances in Engineering Software,2009,(40)341-349.
[37]Jinhui Yang, Xiaohu Shi,Maurizio Marchese, Yanchun Liang. An ant colony optimization method for generalized TSP problem.Progress in Natural Science,2008, (18)1417-1422.
[38]段海滨.蚁群算法原理及其应用.北京：科学出版社,2005.
[39]Manli Li,Zhang Yi, Min Zhu. Solving TSP by using Lotka-Volterra neural networks.Neurocomputing,2009,(72) 3873-3880.
[40]Kate A.Smith,David Abramson, David Duke. Hopfield neural networks for timetabling:formulations, methods, and comparative results.Computers & Industrial Engineering, Volume 2003,44(2)283-305.
[41]韩力群.人工神经网络理论、设计及应用.北京：化学工业出版社,2007.
[42]冯伍.基本机车周转图算法及其原理[D].西南交通大学硕士论文,2006.
[43]刘领兵,吕红霞,陈广秀.多端点不成对机车周转图模型与算法[J].交通运输系统工程与信息.2006,4(3)：106-109.
[44]孙宏,杜文.航空公司飞机排班问题的分阶段指派算法[J].系统工程学报,2003,18(2)：168-172.
[45]朴爱华,胡安洲.我国高速铁路列车运行组织问题的研究[J].铁道学报,1997,18(3)：105-111.
[46]时颢.我国高速铁路列车运行图采用模式的分析[J].铁道学报,2000,22(1)：92-97.
[47]夏阳.客运专线运输组织相关问题研究[D].西南交通大学硕士论文,2003.
[48]汪波,杨浩,张志华.基于周期运行图的京津城际铁路列车开行方案研究[J].铁道学报,2007,29(2)：8-13
[49]梁栋,林柏梁.铁路空车调配的多阶段策略优化模型研究[J].铁道学报,2007,29(1)：1-6.
[50]王相平.客运专线动车组运用计划研究研[D].兰州交通大学硕士论文,2007.
[51]刘殿仁,李得伟,刘启钢.我国客运专线发展模式探讨[J].中国铁路,2005(1)：25-26.
[52]刘丽影,刘继刚,刘继.我国高速动车组检修制度[J].同济大学学报,2001,29(8)：1000-1003.
[53]Michael R. Bussieck, Peter Kreuzer, Uwe T. Zimmermann. Optimal lines for railway systems. European Journal of Operational Research.1996 (96):54-63.
[54]Keivan Ghoseiri,Ferenc Szidarovszky, Mohammad Jawad Asgharpour. A multi-objective train scheduling model and solution[J].Transportation Research Part B. 2004(38):927-952.
[55]Pieter-Jan Fioole, Leo Kroon, Gabor Maroti,Alexander Schrijver. A rolling stock circulation model for combining and splitting of passenger trains[J].European Journal of Operational Research.2006,(174):1281-1297.
[56]Marc Peeters, Leo Kroon. Circulation of railway rolling stock:a branch-and-price approach[J].Computers & Operations Research.2008,(35):538-556.
[57]Balachandran Vaidyanathan, Ravindra K. Ahuja, Jian Liu, Larry A.Shughart. Real-life locomotive planning:New formulationsand computational results. Transportation Research Part B.2008 (42):147-168.
[58]Mohamed Haouari, Najla Aissaoui,Farah Zeghal Mansour. Network flow-based approaches for integrated aircraft fleeting and routing.European Journal of Operational Research. (2007):1-9.
[59]Daeki Kim, Cynthia Barnhart. Flight schedule design for a charter airline. Computers & Operations Research.2007(34):1516-1531.
[60]肖龙文.最优机车周转图的自动化铺划.长沙铁道学院学报.1999,17(1)：52-57.
[6]]王甦男.旅客运输[M].中国铁道出版社.2003.