Solving the Freight Car Flow Problem to Optimality

Abstract

A pervasive problem in freight railroad operations is to determine a feasible flow of cars to meet the required demands within a certain period of time. In this work we present a method to determine an optimal flow of loaded and empty cars in order to maximize profits, revenue or tonnage transported, given the schedule of the trains, together with their traction capacities. We propose an integer multicommodity flow model for the problem whose linear relaxation leads to very good upper bounds — at the cost of using a very large number of variables and constraints. In order to turn this model into a practical tool, we apply a preprocessing phase that may reduce its size by two or three orders of magnitude. The reduced model can then be solved by standard integer program packages with little, if any, branching effort. Computational results on real instances of the largest Latin American railroad freight company are reported. The product that resulted from this research is already in use at that company.