Single-Car Routing in Rail Freight Transport

Single cars in rail freight service are bundled into trains at classification yards. On the way from their respective origins via intermediate yards to their destinations, they are reclassified several times, which is a time-consuming and personally consuming procedure. The single-car routing problem asks for the design of such routes for a given set of orders (origin-destination pairs with associated data) on an infrastructure network, such that the number of trains and their travel distances are minimal. A number of hard restrictions must be obeyed, such as restrictions for the train length and weight, and capacity restrictions for the yards, as well as further operational rules. We present a mixed-integer linear programming (MILP) formulation for this car-routing problem arising at Deutsche Bahn, one of the largest European railway companies. In a further step, we refine the handling of the turnover waiting time for the cars in the yards, which leads to the inclusion of nonlinear constraints in the model. Using adequate linearization techniques, this model can be reduced to a MILP again. Instances of this model turn out to be hard to solve. Further techniques are thus presented to speed up the numerical solution process, among them a tree-based reformulation and heuristic cuts. The different model formulations are computationally compared on a test set of randomly generated instances whose sizes are comparable to real-world instances. Using state-of-the-art MILP solvers, optimal or near-optimal solutions can be computed within a reasonable time frame.