The new method for solving a multi-commodity nonliner flow problem

Abstract

The problem of rational distribution of transport flows in the transport network is considered. The paper deals with modelling and solution methods of transport flow distribution in a tran- sport network under the steady state of transport network elements and in the presence of a possibility of changing them. The problem of flow distribution in the transport network is formulated as an optimization problem. A new method, called a contour optimization algorithm, is presented in the paper that efficiently solves voluminous flow distribution problems. The algorithm is based on the idea of cyclic coordinate descent and the known analogies between the system of equations describing flow distribution in a network and the structure of graph describing the network. These analogies allow use effective graph theory techniques for solving the flow distribution problem. If the state of transport network is not changed, then the problem is a convex one and its solution can be found by contour optimisation algorithm with a desired accuracy. The flow distribution problem at a varying state of network element as a non-linear programming problem with non-convex, piece-wise-smooth objective function. The contour optimisation algorithm can be applied directly to solve the problem if there is no restriction for capital investments necessary to improve the technical state of the network elements. However in this case the algorithm converges to local minimum only. The proposed algorithm was verified by calculating flow distribution in a real railway transport network and the results of calculations were compared with that obtained by the known methods.