Microsoft Word - cet-01.docx Study on High-speed Train Operation Adjustment Based on Differential Evolution Nan Feng Department of Health Management ,Xi'an Medical University, Xi'an, 710021, China fengbaoxiaowei@163.com With the characteristics of numerous constraints, large density and high speed of train, High-speed train operation adjustment problem is a typical large-scale combinatorial optimization problem and also a kind of difficult problem of NP. In combination with the characteristic of China’s high-speed railway, this paper builds the mathematical model of high-speed railway operation adjustment, and the model is solved and optimized with differential evolution algorithm. The result of the experiment shows that the Differential Evolution has very high rationality and feasibility in solving the high-speed train operation adjustment problem. 1. Introduction Train operation adjustment refers to the situation that the train operation needs to be replanned to restore its orderly operation state since the train’s actual operation state deviates from the expected value under the influence of many unexpected factors and emergencies. The searching of an optional train operation adjustment plan is very difficult and complicated due to the complicated network and dynamic changes of the railway transportation. Especially since the high-speed railway has many characteristics, such as the high density and speed of train, its operation is often influenced by many factors like bad weather, line equipment failure and the running of other vehicles. Different situations may involve different variables, and different variable has different influence on the train operation and their expressions of mathematical model can be so different that some variables may be related to the large-scale combinatorial optimization problem which is hard to find the optional solution in traditional mathematical method. In recent years, some new intelligent optimization algorithms like GA, PSO are applied to solve the train operation adjustment problem. However, problems like long searching time and premature are ubiquitous in these algorithm. Differential Evolution (DE) isa new evolutionary computation technology (Storn P, Price K (1995) reported, Vesterstorm J, Thomsen R (2004) reported,) which was put forward by professor Storn and professor Price from Berkeley University in 1995. As a kind of bionic intelligent computation method, DE is considered to have been made great progress in algorithm structure because of its super performance (Duan Haibin et al (2011) reported, Liu Bo et al (2007) reported, Wu Lianghong et al (2007) reported) of less controlled parameters and simple optional process in solving complex optimization problem. However, since there are many problems like premature, low convergence rate and huge computation lying in this algorithm, a differential Evolution (IDE) is put forward in this paper. The simulation result shows that the IDE is superior to the standard differential evolution and can solve the high-speed train operation adjustment problem effectively. 2. The description of high-speed train operation adjustment problem and its mathematical model 2.1 Objective function The train adjustment model of certain adjustment area can be defined as follows: Establishing that in the double operation line area, there are M stations and N trains among which 1 N is the up train while 2N is the down train and 21 NNN  ; 0 ijA and 0ijS show the scheduled time when the i ( Ni ,...,2,1 ) train arrive at and depart from the j ( Mj ,...,2,1 ) station, while ij A and ijS show the actual time when the i train CHEMICAL ENGINEERING TRANSACTIONS VOL. 46, 2015 A publication of The Italian Association of Chemical Engineering Online at www.aidic.it/cet Guest Editors: Peiyu Ren, Yancang Li, Huiping Song Copyright © 2015, AIDIC Servizi S.r.l., ISBN 978-88-95608-37-2; ISSN 2283-9216 DOI: 10.3303/CET1546159 Please cite this article as: Feng N., 2015, Study on high-speed train operation adjustment based on differential evolution, Chemical Engineering Transactions, 46, 949-954 DOI:10.3303/CET1546159 949 arrive at and depart from the j station; sj and aj are the shortest interval time between the train’s departure and arrival time, while ij is the shortest dwell time of the i train in the j station; i jjT )1(  is the i train’s minimum operation time between the j and the ( 1j ) station;  which is given according to the adjustment rule and expertise indicates the relative priority level of the train, and the bigger  is, the higher the train’s priority is. Give a variable ij showed in formula (1) indicating whether the i will dwell in the j station or not.       ijij ijij ij AS AS 0 1  (1) Give a symbolic operation showed in formula sgn       ba ba ba 0 1 ),( (2) Thus we can get the mathematical model of high-speed train operation adjustment showed in formula (3):     )(( 00 1 1 1 ijijijij M j N i i SSAAkf  )),sgn( 0 2 ijijij AAk  (3) In this formula, since )( 00 1 1 ijijijij M j N i i SSAA     , the delay time, and     M j N i ijijij AA 1 1 0 ),sgn( , the amount of delay train, are different in dimension, we adopt 1k and 2k as the weighting coefficient to transfer the two different objects into an optional object, and the value of the coefficient should be taken according to the specific situation. 2.2 Constraint conditions of the high-speed train operation adjustment In consideration of the practical situation of the high-speed train operation, the constraint conditions lying in the operation adjustment area are as follows (1) The constraint condition of the train’s earliest departure time is showed in formula (4) 0 ijij SS  (4) (2) The constraint condition of the train’s operation time is showed in formula (5) i jjijji TSA )1()1(   (5) (3) The constraint condition of the train’s space interval is showed in formula (6) a jijji AA  )1( ; s jijji SS  )1( (6) (4) The constraint condition of the train’s overtaking ( k goes behind i ) is showed in formula (7) ik   ; a jijijkj AA  ; s jijkjij AS  (7) (5) The constraint condition of the train’s station dwell time is showed in formula (8) ijijijij AS  (8) 3. Standard differential evolution Differential evolution is an algorithm that is based on population evolution, and it can be translated into the minimization problem solved as follows: Thereinto, ],...,,[ 21 NPxxxX  makes up the decision space, )(gxi ],...,,[ ,,2,1 gdgg xxx , NPi ,...,2,1 , u ii l i xxx  , , u ix l ix are respectively the upper bound and lower bound of the decision space, and NP is 950 the size of decision space, and d is the dimension quantity, and g is the present evolution algebra. The fundamental principle of differential evolution is: firstly initialize the population, then conduct the operation of variation, crossover and selection to the individual of population and produce progeny population, and get the final result after repeated iteration. The concrete steps are as follows: (1) Initialization population In the decision space X, the initialization vector that generated randomly is shown as formula (9): )(*)1,0()0( l i u i l ii xxrandxx  (9) (2) Mutation operation After the multiplying of the difference vector of differential evolution with the scaling factor, the vector will have vector composition with the base vector. The typical mutation operator is formula (10)  )1(gvi )(1 gxr + F ))()(( 32 gxgx rr  (10) Thereinto, )1( gvi is the ( g +1) th generation variation vector; F is the scaling factor; 1r , 2r , 3r ,are integers that are different from each other; )(1 gxr is the parent base vector in the g generation population ,and ))()(( 32 gxgx rr  are the parent difference vectors. (3) Crossover operation Conduct crossover operation to each individual vector ( ) i x g in the g generation population with variation individual , and there comes the new individual , so as to increase the diversity of the population individual, and the formula is as shown in formula (11): Thereinto, CR is the crossover probability factor; )(gxij means the j dimension component of the i individual in the g generation population, and ]1,0[)( jrand is the corresponding random number of the j dimension. The k is the corresponding coefficient of the i individual and it is always an integer th at is selected randomly in list ],...,2,1[ D and is used to ensure that there is at least one dimension component in the that is from the variation vector individual .       otherwisegx kjorCRjrandifgv gu ij ij i )1( ))(()1( )1( (11) (4) Selecting operation The standard differential evolution takes the greedy selection strategy to conduct the test vector )1( gui and the present population target vector )(gxi ; by evaluating the fitness of both of them, select the superior individual for the search of next generation, and the formula is shown as formula (12).      otherwisegx gxfgufifgu gx i iii i )( ))(())1(()1( )1( (12) Thereinto, f is the fitness function, and is the fitness value that is corresponded with the test individual . 4. Differential evolution algorithm and its solve 4.1 Design of code The differential evolution takes the method of real number encoding, which for the purpose of simplicity, converts the train schedule into the integer minute system, and sets the time of one day to 1440 minutes, the experienced minute quantity from midnight 0 clock to a time present a moment as a certain moment, for example, the time 3:30 is converted into 210 min. The result after the algorithm iteration will be converted into integer value by the method of carrying rounding, for example, the iterated result 187.1 is converted into 188. According to each schedule, for the M stations in the adjustment zone and L train, we take NM 2 matrix for real number encoding, and ),( ikX means the time when the i train arrives at and depart from the k station. ( 1) i v g  ( 1) i u g  ( 1) i u g  ( 1) i v g  ( ( 1)) i f u g  ( 1) i u g  951 4.2 General procedure of Differential Evolution improvement Step 1: initial parameter. Suppose the iteration t=0, then give the maximum iteration maxg , population size NP, exaggeration factor F and cross constant CR. Input the train operation adjustment area, starting time and adjustment time span, and confirm the total amount of train M and each train’s priority level weight  . Step 2: initialize the population according to the designed strategy in 4.1. Step 3:t=t+1. Step 4:make i=1. Step 5:choose another 3 different units at random except the target unit . Step 6: operate mutation to produce the variation individual according to the formula (10). Step 7: calculate the adaptability of and perform the selection operation: if is superior to , perform step 10; otherwise, perform step 8. Step 8: perform crossover operation and according to the formula (11) and get the cross individual . Step 9: calculate the adaptability of and perform the selection operation. Step 10: if 1 ii , then return to step 5 until ; otherwise, perform step 11. Step 11: if the iteration is the maximum iteration, end the loop and output the optional solution; otherwise, return to step 3 and continue the next iteration. 5. Experiments Choose the train operation plan of Beijing-Shanghai high-speed railway between Beijing South Station and Jinan West Station during 7 am to 11 am as the study subject, as shown in Table 1. Let’s suppose that the departure time of G101 and G185 is delayed for 10 minutes because of the underbody service preparation in the EMU base of Beijing South Railway Station, and the arrival time of D333, G113 and G115 in Tianjin South Station is also delayed for 10 minutes due to the interference of unstablizing factor when receiving the control signal between the Langfang Station and Tianjin South Station. Then we make an adjustment to the train operation time according to the adjustment model and algorithm described in this paper, and revert the result to the train operation plan as shown in table2. Through the figure 1, we can get that the model and algorithm put forward in this paper can make an efficient adjustment to the train operation plan with a rational and feasible result, which ensures the train operate as scheduled, and provide a new, efficient and feasible way to the train operation adjustment Table 1: Original train operation plan. Train Numbe r Beijing South Jinan West \Stati on From To From To From to From To From To G101 07:00 07:17 07:17 07:31 07:31 07:51 07:52 08:15 08:15 08:38 D331 07:10 07:29 07:29 07:44 07:46 08:07 08:07 08:30 08:32 09:21 G261 07:15 07:34 07:34 07:49 07:51 08:12 08:12 08:35 08:37 09:03 G57 07:25 07:44 07:44 07:59 08:01 08:22 08:22 08:45 08:47 09:11 G185 07:30 07:49 07:49 08:04 08:06 08:28 08:30 08:52 08:52 09:16 G263 07:55 08:12 08:12 08:25 08:25 08:44 08:44 09:05 09:05 09:27 G11 8 08:17 08:17 08:30 08:30 08:48 08:48 10:40 09:10 09:32 G107 08:08 08:25 08:25 08:39 08:39 08:59 09:01 09:28 09:30 09:54 G55 08:13 08:32 08:32 08:47 08:49 09:10 09:10 09:33 09:43 10:07 D315 08:18 08:38 08:38 08:54 09:14 09:38 09:38 10:05 10:12 10:39 D333 08:23 08:44 09:01 09:19 09:21 09:44 10:04 10:30 10:43 11:07 G31 08:30 08:48 08:48 09:03 09:03 09:24 09:24 09:48 09:48 10:02 G113 09:05 09:22 09:22 09:36 09:36 09:56 09:56 10:18 10:20 10:44 G115 09:16 09:37 09:39 09:53 09:53 10:14 10:14 10:36 10:38 11:02 G41 09:33 09:52 09:52 10:07 10:09 10:30 10:30 10:53 10:55 11:19 D317 09:38 09:59 10:01 10:17 10:17 10:42 10:56 11:26 — — G13 10:00 10:17 10:17 10:29 10:29 10:49 10:49 11:12 　— — D335 10:30 10:51 10:53 11:10 — — — — — — G119 10:45 11:06 — — — — — — — — Langfang Tianjin South Cangzhou West Dezhou East i x i v i v i v i x i x i v i u i u i NP 952 Table 2: Adjusted train operational plan Train Number Beijing South Jinan West \Statio n From To From To From to From To From G101 7:10 7:25 7:25 7:37 7:37 7:51 7:52 8:15 8:15 8:38 D331 7:15 7:31 7:31 7:44 7:46 8:07 8:07 8:30 8:32 9:21 G261 7:20 7:37 7:37 7:49 7:51 8:12 8:12 8:35 8:37 9:03 G57 7:25 7:44 7:44 7:59 8:01 8:22 8:22 8:45 8:47 9:11 G185 7:40 7:56 7:56 8:04 8:06 8:28 8:30 8:52 8:52 9:16 G263 7:55 8:12 8:12 8:25 8:25 8:44 8:44 9:05 9:05 9:27 G11 0:00 8:17 8:17 8:30 8:30 8:48 8:48 9:10 9:10 9:32 G107 8:08 8:25 8:25 8:39 8:39 8:59 9:01 9:28 9:30 9:54 G55 8:13 8:32 8:32 8:47 8:49 9:10 9:10 9:33 9:43 10:07 D315 8:18 8:38 8:38 8:54 9:14 9:38 9:38 10:05 10:12 10:39 D333 8:23 8:44 9:01 9:29 9:31 9:44 10:04 10:30 10:43 11:07 G31 8:30 8:48 8:48 9:03 9:03 9:24 9:24 9:48 9:48 10:02 G113 9:05 9:22 9:22 9:46 9:46 10:02 10:02 10:18 10:20 10:44 G115 9:16 9:37 9:39 10:03 10:03 10:19 10:19 10:36 10:38 11:02 G41 9:33 9:52 9:52 10:08 10:10 10:30 10:30 10:53 10:55 11:19 D317 9:38 9:59 10:01 10:17 10:17 10:42 10:56 11:26 — — G13 0:00 10:17 10:17 10:29 10:29 10:49 10:49 11:12 　— — D335 10:30 10:51 10:53 11:10 — — — — — — G119 10:45 11:06 — — — — — — — — Langf ang Tianjin South Cangzhou West Dezhou East Note: the italics in the figure show the adjusted arrival time and departure time Figure 1: adjusted train operation diagram 6. Conclusions This paper builds up a mathematical model to solve the high-speed train operation adjustment problem, and puts forward a new improved way to solve this problem effectively. The example demonstrates the feasibility and efficiency of the Differential Evolution in solving such problems triggered by itself like pre-mature, simple dimension. References Brest J., Korošec P. & Šilc J., 2013, Differential evolution and differential ant -stigmergy on dynamic optimisation problems, International Journal of Systems Science, 44, 663-679. Chen R.W., Liu L., Guo J., 2012, Optimization Algorithm of Train Operation Energy Consumption Based on Genetic Algorithm, Journal of Traffic and Transportation Engineering, 1, 108-114. 953 Chen S.M., Lai Y.P., Jiang J.H., 2010, Research on Particle Swarm Optimization Algorithm for Train Operation Adjustment, Application Research of Computers, 12, 4460- 4463. Duan H.B., Zhang X.Y., Xv C.F., 2011, Bionic Intelligent Computing. Beijing, China. Gao L.Q., Ren P. & Li N., 2007, A study on the Optimized Scheduling of High-speed Passenger Train Based on CPSO, Journal of Northeastern University, 2, 176-179. Ghosh A., Mondal A. & Ghosh S., 2014, An investigation on evolutionary reconstruction of continuous chaotic systems. Applied Soft Computing Journal, 15, 32-36 Huang J. & Peng Q.Y., 2012, Train diagram optimization of passenger dedicated line based on passenger transport demand in different time, Journal of Railway Science and Engineering, 6, 66-71. Liu B., Wang L. & Jin Y.H., 2007, Research Progress in Differential Evolution, Control and Decision, 7, 721- 729. Lung R.I., Dumitrescu D., 2007, A new collaborative evolutionary-swarm optimization technique. Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation, England: London, 5, 2817-2820. Lu X.F., Tang K., 2014, A new self-adaptation scheme for differential evolution, Neurocomputing, 146, 2-16. Mao S.S., 2004, Probability and Mathematical Statistics, Beijing, China. Meng X.L., Jia L.M., Qin Y., 2010, Train timetable optimizing and res cheduling based on improved particle wwarm algorithm, Transportation Research Record, 2197, 71-79. Mohanty B., Panda S. & Hota P.K., 2014, Differential evolution algorithm based automatic generation control for interconnected power systems with non-linearity, Alexandria Engineering Journal, 53, 537-552. Rathie M., 2012, Stable and generalized-t distributions and applications, Communications in Nonlinear Science and Numerical Simulation, 12, 5088-5096. Reed H.M., Nichols J.M. & Earls C.J., 2013, A modified differential evolution algorithm for damage identification in submerged shell structures, Mechanical Systems and Signal Processing , 39, 396-408. Storn P., Price K., 1995, Differential Evolution-A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces, Berkley: International Computer Science Institute，4，341-359 Vesterstorm J., Thomsen R., 2004, A Comparative Study of Differential Evolution, Particle Swarm Optimization and Evolutionary Algorithm on Numerical Benchmark Problem, Proceedings of IEEE Congress on Evolutionary Computation, 2，1980-1987. Wang R.F., Kong W.Z., Zhan S.Z., 2013, Application of Crossbreeding Particle Swamp Optimization Algorithm in Train Operation Adjustment, Application Research of Computers, 6, 1721-1723. Wu L.H., Wang Y.N., Zhou S.W., 2007, Research and application of Pseudo Parallel Differential Evolution Algorithm with Dual Subpopulations, Control Theory and Applications, 3, 453-458. Zhang Y.S., Jin W.D., 2005, Model and Algorithn for Trail Operation Adjustment on Single Track Railways Based on Genetic Algorithn, Journal of Southwest Jiaotong University, 2, 147-152. 954