摘要
动车组运用计划是高速铁路客运组织过程中的关键环节,直接关系到列车运行安全、服务质量和经济效益。随着我国高速铁路的发展,动车组运用计划编制问题的相关特征呈现出多样化、复杂化趋势,对动车组运用计划的编制提出了新的要求。论文以高速铁路实际生产环境为基础,对动车组运用计划编制理论与方法进行研究。论文的主要工作及成果包括：
1、对动车组运用计划编制基础进行了分析,总结出动车组运用计划编制问题具有时空跨度大、优化目标多、约束条件复杂等特点。
2、将动车组运用计划编制问题归结为特殊的旅行商问题,提出了考虑检修线占用的动车组运用计划编制模型,采用“传递”机制设计了检修累计参数表达方法。为降低问题复杂度和求解难度,提出了从时间、空间和编制过程三个方面对问题进行分解的策略。策略中,将动车组运用计划分为交路计划和检修计划两个阶段分别进行编制。
3、针对动车组交路计划,通过对不同场景条件下交路计划编制过程进行分解,总结出以“基本交路计划”为核心的编制过程。进而针对基本交路计划,提出了编制计划的整数规划模型,设计了求解模型的改进型粒子群算法；算法中,为提高粒子寻优能力,引进了动车组最优接续网络作为粒子飞行的参考；通过算例分析验证了方法的有效性。
4、针对动车组检修计划,同样通过对不同场景条件下计划编制过程进行分解,将编制过程分解为运用修计划编制和高级修计划编制两个部分。针对运用修计划,提出编制计划的整数规划模型,设计了求解模型的改进型蚁群算法；算法中,增加运用任务对应的动车组走行里程作为蚂蚁路径选择概率的计算参数之一,提高了算法面向最大化修程利用率目标的寻优特性；通过算例验证了方法的有效性。
Scheduling of Electric Multiple Units (EMU) is the keylink in the process of passenger transport organization of high-speed railway, and directly relates to the running safety of trains, the service quality, and the economic benefit. With the development of high-speed railway in our country, the characteristics of EMU scheduling problems present a trend of diversification and complication, so new requirements are put forward for the scheduling of EMU. Based on the actual production environment of the high-speed railway, this thesis carries out theory and method studies on the EMU scheduling problem. The main work and achievements can be summarized as follows:
1. The basis of EMU scheduling problem is analyzed, and the characteristics of the EMU scheduling problem are concluded, including the wide range of time-space, the multiple optimization objective, and the complex constraints.
2. The EMU scheduling problem comes down to one special class of travelling salesman problem. Learning from the modeling method of the typical travelling salesman problem, the EMU scheduling model considering the occupancy of maintenance linesis is put forward and the expression method of maintenance accumulative parameters is designed using the "delivering" mechanism. In order to reduce the complexity and the solving difficulty, the solution strategy is proposed, which decomposes the problem from the temporal, spatial and procedural aspects. In the strategy, the EMU scheduling problem is concretely decomposed into the circulation of EMU and the maintenance routing of EMU.
3. For the circulation problem of EMU, the planning process with the core of simple circulation is built by decomposing the circulation programs in different scenarios. Then, for the basic circulation process, an integer programming model is presented and a modified solving algorithm is designed using the idea of particle swarm optimization. In order to improve the particle optimization ability, the optimum connecting network of EMU is introduced to be the reference to the particle flying. The proposed circulation planning method is tested and verified by an example.
4. For the maintenance routing problem of EMU, the planning process is divided into two parts, the maintenance routing planning for the first and second levels and the maintenance routing planning for the high level, by decomposing the maintenance routing programs in different scenarios. For the maintenance routing planning of the first and second levels, an integer programming model is expressed and a modified ant colony optimization algorithm is designed to solve the model. The travel mileage and the travel time are added as parameters of calculating the probability of the ant routing choice, which improve the optimizing character of the algorithm for the target of maximizing the utilization of maintenance cycle mileage standard. The proposed maintenance routing planning method is also tested and verified by an example.
引文
[1]Schrijver A.. Minimum Circulation of Railway Stock[J]. CWI Quarterly,1993,6:205-221.
[2]Abbink E., Berg B.V.D., Kroon L., et al. Allocation of Railway Rolling Stock for Passenger Trains [J].Transportation Science,2004,38(1):33-41.
[3]Alfieri A., Groot R., Kroon L., et al. Efficient Circulation of Railway Rolling Stock[J]. Transportation Science,2006,40(3):378-391.
[4]Fioole P.J., Kroon L., Sehrijver A.. A Rolling Stock Circulation Model for Combining and Splitting of Passenger Trains[J].European Journal of Operational Researeh,2006,172(2):1281-1297.
[5]Peeters M., Kroon L..Circulation of Railway Rolling Stock:A Branch-and-Price Approach [J]. Computers and Operational Research,2006,35(2):538-556.
[6]Mar6ti G, Kroon L.. Maintenance Routing for Train Units:The Transition Model[J]. Transportation Science,2005,39(4):518-525.
[7]Mar6ti G. Operations Research Models for Railway Rolling Stock Planning[D].Eindhoven, Technische Universiteit Eindhoven,2006.
[8]Mar6ti G, Kroon L.. Maintenance Routing for Train Units:The Interchange Model[J]. Computers and Operations Research,2007,34(4):1121-1140.
[9]Hong S.P., Kim K.M., Lee K.S., et al. A Pragmatic Algorithm for the Train-Set Routing:The Case of Korea High-Speed Raiway[J].Omega,2009,37(3):637-645.
[10]赵鹏,杨浩,胡安洲.高速铁路动车组的不固定区段使用问题[J].铁道学报,1997,19(2)：15-20.
[11]赵鹏,胡安洲,杨浩.高速铁路动车组不固定区段使用条件下周转优化问题的研究[J].北方交通大学学报,1997,21(6)：21-24.
[12]赵鹏.高速铁路动车组和乘务运用的研究[D].北京：北方交通大学,1998
[13]聂磊.高速铁路列车运行调整优化理论与方法[D].北京：北方交通大学,1999.
[14]聂磊,赵鹏,杨浩,胡安洲.高速铁路动车组运用的研究[J].铁道学报,2001,23(3)：1-7
[15]赵鹏,富井规雄.动车组运用计划及其编制算法[J].铁道学报,2003,25(3)：1-7
[16]赵鹏,富井规雄.基于概率局域搜索的动车组平日运用计划编制算法[J].系统工程理论与实践,2004,2：123-129
[17]赵鹏,富井规雄.基于路段交换的多基地动车组运用计划的编制算法[J].铁道学报,2004,26(1)：7-11
[18]杨军,杨浩,卢海波.遗传算法在动车组周转优化模型中的应用[J].铁道运输与经济,2004,26(7)：65-67.
[19]陈华群,唐协.基于匈牙利算法的高速动车组周转模型及算法的研究[J].西南民族大学学报-自然科学版,2005,31(5)：779-782
[20]陈华群,唐协.应用神经网络优化高速铁路动车组周转的研究[J].中国安全生产科学技术,2006,2(2)：46-49.
[21]陈华群.动车组运用计划编制系统相关问题研究[D].成都：西南交通大学,2007.
[22]耿敬春,肖国荣,倪少权,牛会想.客运专线动车组周期性运用计划编制的研究[J].铁道学报,2006,28(4)：17-21
[23]耿敬春.客运专线动车组运用计划编制优化研究[J].西华大学学报,2008,27(6)：83-86.
[24]耿敬春.京沪高速铁路动车组运用计划编制相关问题研究[D].成都：西南交通大学,2008.
[25]倪少权,等.客运专线动车组周转图编制优化的研究[J].学术动态,2006(3)：16-20.
[26]张杰,陈韬,施福根.客运专线动车组运用计划的计算机编制[J].西南交通大学学报,2006,41(5)：635-640
[27]郭海燕.客运专线动车组运用计划编制算法的研究[D].北京：北京交通大学,2007.
[28]陈玲娟.遗传算法在动车组运用计划编制中的应用[J].交通运输工程与信息学报,2009,7(2)：67-71.
[29]佟璐,聂磊,赵鹏.蚁群算法在动车组运用问题中的应用[J].交通运输系统工程与信息,2009,9(6)：161-167.
[30]王莹.动车组运用计划和乘务计划的优化方法研究[D].北京：北京交通大学,2009
[31]王莹,刘军,苗建瑞.基于列生成算法的动车组检修计划优化[J].中国铁道科学,2010,31(2)：115-120.
[32]郁宇卫.客运专线动车组运用计划优化研究[D].长沙：中南大学,2009.
[33]苗建瑞,王莹,杨肇夏.基于最优接续网络的动车组交路计划优化模型与算法研究[J].铁道学报,2010,32(2)：1-7.
[34]张才春,花伟,陈建华.双修制下的动车组运用计划编制研究[J].铁道学报,2010,32(3)：16-19.
[35]张才春,陈建华,花伟.基于不同检修能力的动车组运用计划研究[J].中国铁道科学,2010,31(5)：130-133.
[36]张才春.成网条件下客运专线动车组运用的研究[D].北京：北京交通大学,2010.
[37]李鹏.基于交路互换的客运专线动车组检修计划的研究[D].北京：北京交通大学,2010.
[38]蒋继磊,杨志杰.动车组运用计划编制及其优化[J].铁道运输与经济,2010,32(4)：37-40,48.
[39]曲思源,徐行方.城际铁路动车组运用计划模型[J].同济大学学报(自然科学版),2010,38(9)：1298-1302.
[40]史峰,周文梁,郁宇卫,卿力.客运专线动车组运用计划优化模型与算法[J].铁道学报,2011,33(1)：8-13.
[41]王忠凯,史天运,张惟皎,王辉.动车组运用计划和检修计划一体化编制模型及算法[J].中国铁道科学,2012,33(3)：102-108.
[42]王忠凯.动车组运用检修计划优化方法的研究[D].北京：中国铁道科学研究院,2012.
[43]闻克宇.成网条件下高速铁路动车组运用问题的研究[D].北京：北京交通大学,2012.
[44]黄兴亮.动车组交路计划编制优化理论与方法研究[D].成都：西南交通大学,2012.
[45]吴冰芝.客运专线动车组运用优化研究[J].交通运输工程与信息,2011,9(2)：78-82.
[46]吴冰芝.客运专线动车组运用优化研究[D].成都：西南交通大学,2012.
[47]赵鹏,张迦南.铁路动车组的运用问题研究[J].北京交通大学学报,2009,33(3)：6-10,16.
[48]Barnhart C, Belobaba P., Odoni A.R.. Applications of Operations Research in the Air Transport Industry[J].Transportation Science,2003,37(4):368-391.
[49]Feo T A, Bard J F. Flight Scheduling and Maintenance Base Planning[J]. Management Science,1989,35(12):1514-1532.
[50]Barnhart C, Boland N.L., Clarke L.W., et al. Flight String Models for Aircraft Fleeting and Routing[J]. Transportation Science,1998,32(3):208-20.
[51]Gopalan R., Talluri K.T.. Aircraft Maintenance Routing Problem[J]. Operations Research,1998,46(2):260-71
[52]Sarac A.. Daily Operational Aircraft Maintenance Routing Problem[D].State University of NewYork.2000.
[53]Rosenberger J.M.Topics in Airline Operations[D].Georgia Institute of Technology,2001.
[54]Wu C.L., Caves R.E.. Towards the Optimization of the Schedule Reliability of Aircraft Rotations[J].Journal of Air Transport Management,2002,8:419-426.
[55]Wu C.L., Caves R.E.. Modeling of Aircraft Rotation in a Multiple Airport Environment [J]. Transportation Research Part E,2002,38:265-277.
[56]Yan S.Y., Tseng C.H.. A Passenger Demand Model for Airline Flight Scheduling and Fleet Routing [J].Computer and Operations Research,2002,29:1559-1581.
[57]Bartholomew-Biggs M.C., Parkhurst S.C.,Wilson S.P.. Global Optimization Approaches to an Aircraft Routing Problem [J]. European Journal of Operational Research,2003,146(1): 417-431.
[58]Rosenberger J.M.,Johnson E.L.,Nemhauser G.L..Rerouting Aircraft for Airline Recovery [J].Transportation Science,2003,37(4):408-421.
[59]Lohatepanont M., Barnhart C.Airline Schedule Planning:Integrated Models and Algorithms for Schedule Design and Fleet Assignment [J].Transportation Science,2004,38(1):19-32
[60]Boland N., Dumitreseu L. Accelerated Label Setting Algorithms for the Elementary Resource Constrained Shortest Path Problem [J]. Operations Research Letters,2006,34(3):58-68.
[61]Barnhart C, Airline Schedule Planning [EB/OL]. http://www.core.org.cn/OewWeb/Global/all-courses.html.
[62]Sarac A.,Batta R.,Rump CM.. A Branch-and-Price Approach for Operational Aircraft Maintenance Routing[J].European Journal of Operational Research,2006,175:1850-1869.
[63]Lan S.,Clarke J.p.,Barnhart C. Planning for Robust Airline Operations:Optimizing Aircraft Routing and Flight Departure Times to Minimize Passenger Disruptions[J].Transportation Science,2006,40(1):15-28.
[64]Sherali H.D.,Bish E.K.,Zhu X.M.. Airline Fleet Assignment Concepts, Models, and Algorithms [J]. European Journal of Operational Research,2006,172:1-30.
[65]Smith B.C., Johnson E.. Robust Airline Fleet Assignment:Imposing Station Purity Using Station Decomposition [J]. Transportation Seienee,2006,40(4):497-516.
[66]Lohatepanont M., Barnhart C. Airline Schedule Planning:Integrated Models and Algorithms for Schedule Design and Fleet Assignment [J].Transportation Sciencem,2004,38(1):19-32.
[67]孙宏,杜文,徐杰.最小费用最大流模型在航班衔接问题中的应用[J].南京航空航天大学学报,2001,33(5)：478-481.
[68]孙宏,杜文.航空公司飞机排班问题的排序模型及算法[J].系统工程理论方法应用,2002,11(3)：244-247.
[69]孙宏,杜文.航空公司飞机排班问题的分阶段指派算法[J].系统工程学报,2003,18(2)：168-172.
[70]孙宏.航空公司飞机排班问题：模型与算法研究[D].成都：西南交通大学,2003.
[71]Bussieck M.R., Winter T.,Zimmermann U.T.. Discrete Optimization in Public Rail Transport [J].Mathematical Programming,1997,79:415-444.
[72]Ziarati K, Soumis F, Desrosiers J,et al. Locomotive Assignment with Heterogeneous Consist at CN North America[J]. European Journal of Operational Research,1997,97:281-292.
[73]Forbes MA, Holt J N, Watts AM. Exact Solution of Locomotive Scheduling Problems[J]. Journal of the Operational Research Society,1997,42(10):341-253.
[74]Cordeau J.F., Toth P., Vigo D.. A Survey of Optimization Models for Train Routing and Scheduling[J]. Transportation Science,1998,32(4):380-404.
[75]Lindner T.. Train Schedule Optimization in Public Rail Transport[D]. Technischen Universitt Braunschweig,2000
[76]Cordeau J.F., Soumis F., Desrosiers J. Simultaneous Assignment of Locomotives and Cars to Passenger Trains.[J] Operations Research,2001,49(4):531-548
[77]Cordeau J.F., Desaulniers G, Lingaya N., Soumis F., Desrosiers J. Simultaneous Locomotive and Car Assignment at VIA Rail Canada[J]. Transportation Research Part B,2001,35:767-787
[78]Lingaya N., Corduau J.F., Desaulniers G, et al. Operational Car Assignment at VIA Rail Canada[J].Transportation Research Part B,2002,36:755-778.
[79]Huisman D., Kroon L.G., Lentink R.M., et al. Operations Research in Passenger Railway Transportation[R].Econometric Institute Report EI,2005-16.
[80]Ahuja R,K.,Liu J.,Orlin J.B.,Sharma D.,Shughar L.A..Solving Real-Life Locomotive Scheduling Problems[J]. Transportation Science,2005,39(4):503-517
[81]Godwin T, Gopalan R., Narendran T.T.. Tactical Locomotive Fleet Sizing for Freight Train Operations[J]. Transportation Research Part E,2007
[82]李致中,孙焰.用电子计算机铺画最优机车周转图[J].铁道运输与经济,1988,(5)：12-15.
[83]史峰,胡安洲.机车周转图的线性配置算法[J].铁道学报,1996,4：18-24.
[84]肖龙文.最优机车周转图的自动化铺划[J]长沙铁道学院学报,1999,1：54-59.
[85]崔炳谋.机车周转图的计算机优化算法[J].铁路计算机应用,1999,2：18-24.
[86]闫海峰,崔燚.编制机车周转图的优化模型[J].中国铁道科学,2006,27(4)：123-128.
[87]林柏梁,胡安洲.重空车流运行组织的协同优化理论及模型[J].铁道学报,1998,20(5)：9-14.
[88]李文权,杜文,周贤伟.优化空车调配问题[J].西南交通大学学报,1998,33(4)：383-386.
[89]施其洲,施勇.具有双向、空重车流的路网车流径路多目标标线性规划模型及算例[J].铁道学报,1999(1)：2-10.
[90]梁栋,林柏梁,严贺祥,等.车种代用情况下的铁路空车调配研究[J].铁道学报,2005,27(4)：1-5.
[91]胡思继.铁路行车组织(第二版)[M].北京：中国铁道出版社,2009,
[92]杨浩.铁路运输组织学(第三版)[M].北京：中国铁道出版社,2011.
[93]Choi I.C.,Lim S.I.,Lim H.S..A Genetic Algorithm with a Mixed Region Search for the Asymmetric Traveling Salesman Problem [J].Computers and Operations Research,2003, 20(5):773-786.
[94]Yoon H.S., Moon B.R.. An Empirical Study on the Synergy of Multiple Crossover Operators[J]. IEEE Transactions on Evolutionary Computation,2002,6(2):212-223.
[95]Tang L.X.,Liu J.Y.,Rong A.Y.,et al. Modelling and a Genetic Algorithm Solution for the Slab Stack Shuffling Problem When Implementing Steel Rolling Schedules[J]. International Journal of Production Research,2002,40(7):1583-1595.
[96]Fogel D.B..Applying Evolutionary Programming to Selected Traveling Salesman Problems [J]. Cybernetics and Systems,1993,24(l):27-36.
[97]Chellapilla K.,Fogel D.B..Exploring Self-adaptive Methods to Improve the Effciency of Generating Approximate Solutions to Traveling Salesman Problems Using Evolutionary Programming[J].Leture Notes in Computer Science,1997,1213:361-371
[98]Nurnberg H.T.,Beyer H.G.Dynamics of Evolution Strategies in the Optimization of Traveling Salesman Problems[J].Leture Notes in Computer Science,1997,1213:349-361.
[99]Dantzig G.B., Fulkerson D.R.,Johnson S.M..Solution of a Large Scale Traveling Salesman Problem[J].Operation Research,1954,2:393-410.
[100]Kennedy J., Eberhart R.. Particle Swarm Optimization[C]//Proc. IEEE Int'l. Conf. on Neural Networks. IV. Piscataway:IEEE Service Center,1995:1942-1948.
[101]王凌.智能优化算法及其应用[M].北京：清华大学出版社,2001.
[102]梁艳春,吴春国,时小虎,等.群智能优化算法理论与应用[M].北京：科学出版社,2009.
[103]钱颂迪.运筹学[M].北京：清华大学出版社,1990.
[104]Dorigo M. Optimization, Learning and Natural Algorithms [D]. Ph.D Thesis, Dipartimentl di Elettronica, Politecnico di Milano, Italy,1992:140.
[105]Dorigo M., Maniezzo V., and Colorni A. The Ant System:Optimization by a Colony of Cooperating Agents [J]. IEEE Transactions on Systems, Man and Cybernetics-Part B,1996, 26(1):1-13.
[106]Dorigo M. and Ganbardella L. Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem [J]. IEEE Trasactions on Evolutionary Computing,1997,1(1): 53-66.
[107]Dorigo M. and Caro G.D. The Ant Colony Optimization Meta-heuristic [M]. In:New Ideas in Optimization. McGraw-Hill, London,1999:11-32.
[108]Dorigo M., Birattari M., and StUtzle T. Ant Colony Optimization:Artificial Ants as a Computational Intelligence Technique [J]. IEEE Computational Intelligence Magazine,2006, 1(4):28-39.
[109]Jerne N.K. Towards a Network Theory of the Immune System [R], Annual Immunology,1974, 125C(l-2):373-389.
[110]Farmer J.D., Kauffman S.A., Packard N.H. et al. Adaptive Dynamic Networks as Models for the Immune System and Autocatalytic Sets [J]. Perspectives in Biolobical Dynamics and Theoretical Medicine, Annals of the New York Academy of Science,1987,504(1):118-131.
[111]Carter J.H. The Immune System as a Model for Pattern Recognition and Classification [J]. Journal of the American Medical Informatics Association,2000,7(1):28-41.
[112]Castiglione F., Motta S., and Nicosia G. Pattern Recognition by Primary and Secondary Response of an Artificial Immune System [J]. Theory in Biosciences,2001,120(2):93-106.
[113]White J.A. and Garrett S.M. Improved Pattern Recognition with Artificial Clonal Selection [J]. Lecture Notes in Computer Science,2003,2787:181-193.
[114]Tang Z., Tashima K., and Cao Q.P. Pattern Recognition System Using a Clonal Selection-based Immune Network [J]. Systems and Computers in Japan,2003,34(12):56-63.
[115]Sarafijanovic S. and Le Boudec J.Y. An Artificial Immune System Approach with econdary Response for Misbehavior Detection in Mobile Ad Hoc Networks [J]. IEEE Transactions on Neural Networks,2005,16(5):1076-1087.
[116]Gong M.G., Du H.F., Jiao L.C. et al. Immune Clonal Selection Algorithm for Multiuser Detection in DS-CDMA Systems [J]. Lecture Noetes in Artificial Intelligence,2004,3339: 1219-1225.
[117]Aickelin U. Greensmith J., and Twycross J. Immune System Approaches to Intrusion Detection-A Review [J]. Lecture Notes in Computer Science,2004,3239:316-329.
[118]Foukia N., Hassas S., Fenet S. et al. Combining Immune Systems and Social Insect Metaphors: A Paradigm for Distributed Intrusion Detection and Response System [J]. Lecture Notes in Computer Science,2003,2881:251-264.
[119]Cruz-Cortes N., Trejo-Perez D., and Coello C.A.C. Handling Constraints in Global Optimization Using an Artificial Immune System [J]. Lecture Notes in Computer Science, 2005,3627:234-247.
[120]Freschi F. and Repetto M. Multiobjective Optimization by a Modified Artificial Immune System Algorithm [J]. Lecture Notes in Computer Science,2005,3627:248-261.
[121]Du H.F., Gong M.G., Jiao L.C. et al. A Novel Algorithm of Artificial Immune System for High-Dimensional Function Numerical Optimization [J]. Progress in Natural Science,2005, 15(5):463-471.
[122]Coello C.A.C. and Cortes N.C. Hybridizing a Genetic Algorithm with an Artificial Immune System for Global Optimization [J]. Engineering Optimization,2004,36(5):607-634.
[123]Farmer J.D., Packard N.H., and Perelson A.S. The Immune System, Adaptation, and Machine Learning [J]. PhysicaD,1986,22(1-3):187-204.
[124]Hunt J.E. and Cooke D.E. Learning Using and Artificial Immune System [J]. Journal of Network and Computer Application,1996,19:189-212.
[125]Glickman M., Balthrop J., and Forrest S. A Machine Learning Evaluation of an Artificial Immune System [J]. Evolutionary Computation,2005,13(2):179-212.
[126]Nasraoui O., Gonzalez F, Cardona C. et al. A Scalable Artificial Immune System Model for Dynamic Unsupervised Learning [J]. Lecture Notes in Computer Science,2003,2723: 219-230.