Research On Train Formation Plan Optimization In Railway Network Based On Branch And Price Algorithm

Compared with other modes of transportation,railway transportation has the advantages of large capacity,low cost,fast-speed and eco-friendly.Freight train formation plan is the basic technical document of railway freight transport organization.It decides how to transport all heavy and empty car flow from departure station to arrival station in the railway network,and plays a decisive role in the efficiency of railway freight transport.Therefore,it is of great practical significance to optimize the train formation plan.Based on the summary and analysis of relevant research results at home and abroad,this paper focus on the optimization of train formation plan in railway network.The specific work and conclusions are as follows:(1)The theoretical study of train formation plan.Firstly,the concept,Compilation principle and Compilation process of train formation plan are introduced.On this basis,the key factors involved in freight train formation plan are analyzed.Finally,through discussing the scale of train formation plan problem in railway network,the complexity of its solution is illustrated,which lays a foundation for the establishment of optimization model of train formation plan in railway network.(2)A 0-1 integer programming model for train formation plan in railway network is established.The train formation plan problem is transformed into a network optimization problem,and the problem is abstracted based on the related concepts of graph theory.The optimization model of train formation plan in railway network is established with the objective of minimizing the sum of accumulation time,running time and transit time.An example of small-scale railway network is designed and solved by Lingo programming software.The correctness of the model is verified by the example.(3)The design and realization of algorithm based on the branch and price algorithm.According to the characteristics of the model,a solution algorithm is designed based on the basic idea of branch and price algorithm,including the D-W decomposition strategy of the model,the generation of the initial feasible column,the solution of the restricted master problem,the solution of the price sub-problem and the design of the branch strategy.The algorithm is programmed by C#language,and the correctness and efficiency of the algorithm are verified by solving small-scale railway network.(4)Case calculation and results analysis of train formation plan based on actual railway network.Based on the network marshalling station,the national freight railway network is simplified,and a simplified railway network with 14 large marshalling stations is obtained.The train formation plan of the simplified railway network is solved by using actual freight demand data.The results are analyzed from three aspects:feasibility,optimization effect and algorithm efficiency.It is proved that the model and algorithm proposed in this paper have a certain practical value.In addition,through the case study of a large-scale railway network with 40 marshalling stations,it is proved that the optimization method proposed in this paper still has a good optimization effect when the scale of the railway network is further expanded.