The article deals with the application problem on the assignments and transportations of locomotives. By the methods of graph theory, the problem on the assignments and transportations of locomotives can be reduced to a graph-theoretical problem of covering of vertices of a directed graph by the set of maximal by inclusion simple directed paths. It is introduced the directed graph of compatibility of transportations, and it is considered an approach to modelling of the application problem, which based on the properties of the directed graph of compatibility of transportations. In the view of the specific structure, the graph of compatibility of transportations has certain structural and combinatorial properties. It is proved an important statement, based on the properties of the directed graph, which is about the possibility of consideration of the set of binary sets a predetermined length, which corresponds to a set of simple directed paths of the graph. An algorithm for the constructing a set of simple directed paths of the graph is developed. For a given set of simple directed paths of the graph, there is settled the problem of constructing a set of maximal by inclusion simple directed paths, and an algorithm for solving the problem is developed. The set of maximal by inclusion simple directed paths is the basis of the algorithm of the covering of vertices of the directed graph of compatibility of transportations by the set of maximal by inclusion simple directed paths. The software complex, which implements the developed algorithms, is described by Visual Basic. The article presents the results of the computer implementation of software complex in the application problem on the assignments and transportations of locomotives.