Graph methods for solving the unconstrained and constrained optimal assignment problem for locomotives on a single-line railway section

We propose a new graph model of transportation on a single-line railway section. Based on a given freight-train delivery schedule, we construct an acyclic graph with vertices denoting deliveries and arcs indicating the possibility of successive implementation of these deliveries by some locomotive. This model of the problem permits applying static graph algorithms to find an optimal locomotive assignment plan. The search for a solution of the problem without time constraints on the locomotives is reduced to finding a minimal path cover of an acyclic graph. Each path in the cover corresponds to a sequence of deliveries carried out by one locomotive. If there are temporary constraints on the locomotives (maintenance breaks), not all paths in the cover can remain valid: for some locomotives, none of the established delivery sequences can be performed from start to finish. In this case, one more solution stage is added, at which the cover is transformed in such a way that all new paths describe a sequence of deliveries that can be carried out by a given set of locomotives under given time constraints.