Study On Railway Car Flow Assignment Optimization Model And Lagrangian Relaxation Algorithm

With the formulation of the high-speed network and the separation of railway passenger and freight line, the congested existing rail lines for freight have been freed up greatly, which provides the prerequisites for resources allocation optimization and railway products development in railway freight. On one hand, railway car flow assignment and routing problems need to be overall optimized in consideration of the capacity of lines and stations in the environment of new railway network, so that the transportation demand could match with the capacity of railway network. On the other hand, optimizing railway car flow routing can help sharply reducing roundabout railway car flow.This dissertation will study the railway car flow assignment and routing problem based on the characteristics of railway transport organization in railway network of China by learning from the multi-commodity flow problem, and the results will provide theoretical guidance for railway transportation organization for the programming and designing of railway network. This paper mainly includes the following several parts:(1) The basic theory of traffic flow distribution is described, including the definition of railway car flow assignment and routing, their relationship in the railway transportation organization, and the affecting factors for railway car flow assignment. In addition, typical railway car flow distribution optimization method was introduced and analyzed in this paper including heuristic method based on shortest path and the typical mathematical programming model.(2) Optimization problem of railway car flow distribution based on single railway car flow without split is investigated. Based on the multi-commodity network flow theory, a mixed integer programming model for railway car flow distribution optimization is established with the consideration of the requirement of each car flow moving on one route only for railway transport organization. For possible infeasible car flow, the paper sets super segmental arc by referencing the ideas of virtual arc to deal with those unallocated OD traffic flow so that the proposed model is improved. Finally, the optimization model is verified and the numerical example results show that with the different data of ability the proposed optimization model can both get car flow adistribution and routing plan, and it can deal with the infeasible railway car flow effectively.(3) Existing railway car flow tree-formed routing path optimization model is analyzed and improved. Firstly, the characteristics and forming reason of the tree-formed routing for technical car flow is explained. Secondly, the classical optimization model with tree-formed routing is introduced, which is a nonlinear mathematical programming model. The analysis reveals that it is difficult to solve the model because of the higher order terms in the objective function and constraint conditions. In order to improve the applicability and reduce computational load, this existing model is improved, with the replace of two groups of variables.(4) On the base of the results in (3), it is found that the improved model cannot obtain the path directly. Therefore, integrating the multi-commodity network flow theory, a new railway car flow distribution optimization model is proposed, with the structure of the tree-formed routing rooted in the same destination. In essence, it is a mixed integer programming model. Besides the constraint that single railway car flow cannot be split, the proposed model is subjected to the structure of the tree-formed routing constraint. Similarly, infeasible flow problem is dealt with by introducing of the super arc and super variables, and the proposed model is improved. The numerical example results show that, the proposed optimization model can not only obtain both car flow assignment and routing plan, but also deal with the infeasible railway car flow effectively.(5) To solve the mixed integer optimization model of railway car flow assignment proposed in the content (2) and content (4), the Lagrange relaxation algorithm is investigated. First of all, the original problem is broken down into sub problems which are easy to solve, with introduce of Lagrange relaxation multiplier vectors to eliminate the station and line capacity constraints. Then traditional subgradient optimization algorithm is used to solve the Lagrangian dual problem for lower bound, and a heuristic algorithm is designed for the upper bound. To address the railway car flow assignment optimization model with the constraint that single railway car flow cannot be split, a heuristic algorithm is designed with the reverse relationship between the variables and traffic flow order. To address the railway car flow assignment optimization model with the structure of the tree-formed routing, a new algorithm is designed. Finally, the numerical example results show that the Lagrange relaxation algorithm can solve the model effectively. And it can make a tradeoff between computational accuracy and speed by setting the error range.