Research On Discrete Differential Evolution Algorithm In Train-set Scheduling Problem

The use of EMU related to the travel time of the EMU on the railway,the contents of the EMU play trips through the station,departure time and arrival time,path and maintenance.EMUs scheduling problem is essentially the optimization and utilization of EMUs under the conditions of full consideration of train connection and maintenance constraints.It is a typical optimization problem in a complex environment.The Differential Evolution algorithm(DE)has the advantages of less control parameters,relatively simple principle,easy to understand and implement,and its unique differential mutation operation does not need to use the characteristic information of the problem in the evolution process.Strong global convergence performance and high reliability of DE are suitable for solving optimization problems in complex environments.From the perspective of the optimized connection of EMU,this paper mainly studies the optimization model and algorithm of EMU scheduling.The details are as follows:(1)In this paper a new Discrete Differential Evolution for the Permutation EMU Scheduling Problem with the total residence time criterion for one station is proposed.The optimized model of EMU scheduling is established based on Train Scheduling Diagram and the Pairing Diagram.The Discrete Differential Evolution for the Permutations space based on Optimal Q(DDEP-Q)is used to solve this model,and the Optimal Working Scheme of EMU is obtained.First,the initial individual in the DDEP-Q algorithm are represented as the discrete job permutation,which is the Pair of the Final train and the Originating train on the station.Second,based on this representation,new mutation operator is designed with a Randomized Bubble Sort algorithm,and the adaptive adjustment strategy is introduced.Third,through the process of the algorithm evolution,on the basis of the binomial cross strategy,we randomly select the intersection of the individual,and then carry out partial gene exchange to preserve the excellent information of the individual and avoid the destruction of the optimal solution.Meanwhile,in order to improve the effectiveness of the algorithm,we introduce the greedy selection strategy with certain probability to find the optimal working time of EMU.The validity of the DDEP-Q algorithm is demonstrated by the convergence and the quality of the result.Taking Wuhan-Guangzhou high-speed railway for an example,the DDEP-Q algorithm is more feasible than the ant colony algorithm.(2)Aiming at the optimization problem of EMU application planning considering maintenance constraints,a hybrid algorithm(TS-DDEP-Q)combining Tabu Search(TS)and DDEP-Q is proposed.Using an ordered positive integer arrangement of all trains in a train diagram to indicate the use of crossroads in EMU.In the use of EMUs,EMU trains meet maintenance mileage and time period constraints.Minimizing the number of EMUs used as the optimization goal and establishing an optimization plan for the use of EMUs.For TS-DDEP-Q algorithm,the idea of TS optimization algorithm is applied,and the initial solution of the algorithm is generated through the neighborhood function.Using the DDEP-Q algorithm variation method and design repair strategy for infeasible solution;Based on the traditional two-point crossover strategy,cross operation are designed using the idea of "road segment exchange" in the crossroads.Combined with an example,the TS-DDEP-Q algorithm solve the EMU planning problem is presented.The MATLAB simulation study is conducted to verify the rationality and effectiveness of the algorithm in EMU application optimization.The simulation results show that the TS-DDEP-Q algorithm shows better advantages than the discrete differential evolution algorithm under other mutation methods.