Graph Methods for Improving the Non-Optimal Solution of the Locomotive Assignment Problem under Time Constraints

Abstract

Finding the optimal assignment of locomotives to fulfill freight train transportation schedule under time constraints is a complex problem, even on a linear section of the railway. In previous studies, a graph model was proposed that allows solving the assignment problem using a static graph algorithm. It was proved that finding the optimal assignment without constraints is equivalent to finding the minimal path cover of a specific acyclic graph. However, due to time constraints, the optimal solution may not be valid. This paper presents methods for modifying the found solution in order for it to satisfy the time constraints on locomotives. Two operations on path in the minimal path cover of a graph are introduced: crossover and changeover. They allow to rebuild the found solution without spoiling the admissible sequences of transportation, while the invalid ones are corrected.