Train Diagram Forming Quality Evaluation And Optimization Method

Train diagram(also known as train timetable)is the technical file which represents the operation of train between stations and departure,arrival as well as through a station,the forming of train diagram is a complex system project.With the constructing of rail network,the period of train diagram reforming has decreased and the regional adjustment has increased,at current time,the forming of train diagam in China is still mainly a manual work,the quality of train diagram forming quality is affected by the diagram maker work skill significantly,the evaluation of train diagram forming quality is important to analyze the work skill of train diagram makers.The train diagram forming problem(also known as train timetabling problem)has a large scale,based on manual work,the process of diagram forming is a tough work and has significant shortage,train diagram optimization is important for reduce the work burden of train diagram makers and improve the automatical level of train diagram forming.The research of the train diagram forming quality evaluation and optimization method has great meaning both theoretically and practically.Train path as the basic unit of train diagram,the drawing and adjustment of it is the main object of train diagram forming quality and evaluation.This dissertation took train path as basic unit,proposed a train path efficiency index to describe the quality of train path;based on DEA method build a solving model,proposed the train diagram forming quality evaluation method taken the train path efficiency index;analyzed the impacts that affect the train diagram forming quality according to the real-world case study,given a departure time window and a total travel prolong time constraint,used a time-space graph to build a integer linear programming model to optimize the train digram;a Lagrangian-relaxation based heuristic algorithm was applied to solve the problem,considered the capacity utilization-orinted strategy,expanded the method.The main contants of this dissertation include:1.Train diagram forming quality definition and impact factors.Proposed the broad and narrow concept of train diagram forming,defined the train diagram forming quality according to the narrow concept,and analyzed the influence patters of train diagram forming quality theoretically.Combined the feature of train diagram forming evaluation to prove that the existing indexes could hardly meet the demands of train diagram forming quality evaluation,proposed the features that the train diagram forming quality evaluation indexes should have,gave the steps of train diagram forming quality evaluation.2.Train diagram forming quality evaluation method.According the features of train diagram forming quality evaluation index,took train path as basic unit,defined the train path efficiency with the weighted ratio of train path feedback technical indexes and transport resource occupations,and used it as the train diagram forming quality evaluation index.Based on the contains of train path efficiency,gave the calculation method of sub-indexes,considered the relative feature of train path efficiency,abstracted the train diagram as a multi-input-multi-output produce system,then transferred the solution of train path efficiency into a produce unit efficiency evaluation of a multi-input-multi-output produce system,introduced Data Envelopment Analysis method to build a train path efficiency solve model,took consideration of the distribution of train path efficiency,gave the evaluation method based on statistical analysis and satisfactory theory,used real-world case to verify.3.Train diagram optimize model and solution algorithm.Giving each train path a departure time adjustment range and total stop stretch limitation,transferred the train path drawing constraints into the node selection constraints of the time-space graph,express the train path drawing as a path solving problem within a time-space graph.Based on the time-space graph to build train diagram optimization integer linear programming model,consider the features of the model,relaxed the hard-constraints in a Lagrangian way,took consider the Lagrangian penalty of each node,used heuristic method to solve the feasible solution of each train path,updated the Lagrangian multiplier by sub-gradient method,to optimize the train diagram iteratively.4.Train diagram optimize considering stop-skip strategy model and solution algorithm.Consider the real world situation that some rail lines had a high capacity requirement,proposed a way to increase the number of train path that scheduled and improve the capacity utilization by cancel some stops of trains.Gave a certain number of stops that can be cancelled and penalty of the stop cancellation,took the stop cancellation affection into train path solve,extended the existing model,a Lagrangian based heuristic method is applied to solve the problem,Bejing to Shanghai high-speed line are used as real world verification.