Modelling railway freight traffic using the methods of graph theory and combinatorial optimization

Abstract

The optimization problem of planning the railway freight traffic was presented, and approaches to reduction of problem dimension by constructing a hierarchy of the problems of train traffic planning were described. The notion of conflict graph on a set of energy-efficient standard threads was introduced. A “traveling wave” algorithm to construct the conflict-free sets of standard threads of the train schedule on the basis of the conflict graph was proposed. The problem of optimal assignments and transportations of locomotives in terms of the minimized number of utilized locomotives was formulated, an algorithm to solve to it was given, and its complexity was estimated.