We consider a variant of the freight railcar flow problem. In this problem, we need 1) to choose
a set of transportation demands between stations in a railroad network, and 2) to fulfill these
demands by appropriately routing the set of available railcars, while maximizing the total profit.
We formulate this problem as a multi-commodity flow problem in a large space-time graph. Three
approaches are proposed to solve the Linear Programming relaxation of this formulation: direct
solution by an LP solver, a column generation approach based on the path reformulation, and a
“column generation for extended formulations” approach. In the latter, the multi-commodity flow
formulation is solved iteratively by dynamic generation of arc flow variables. Three approaches
have been tested on a set of real-life instances provided by one of the largest freight rail transportation
companies in Russia. Instances with up to 10 millions of arc flow variables were solved
within minutes of computational time.