One-block train formation in large-scale railway networks: An exact model and a tree-based decomposition algorithm

We investigate the one-block train formation problem (TFP) in the railway freight transportation industry. The input to this problem is a railway network and a set of demands for transportation. Each demand is a request for shipping a number of rail cars from one station to another. The one-block TFP now addresses two subproblems in the tactical level: Which pairs of stations are directly connected via a block (or: train service); and which demands are transported by each block. The aim is to service all demands against minimal costs. Moving beyond current researches on service network design, the unitary rule and the intree rule are taken into account in this study based on the Chinese railway background. We develop a linear binary programming formulation to minimize the total sum of train accumulation costs and car classification costs, subject to limitations on the classification capacity and the number of sort tracks at each station. Furthermore, we propose a novel solution methodology that applies a tree-based decomposition algorithm. Here, we first decompose the whole network into a series of rooted trees for each destination separately. Then, we divide the trees further into sufficiently small subtrees, whose size is regulated by a node size parameter. Finally, we construct a restricted linear binary model for each subtree and solve these models sequentially to find their optimal solutions. The algorithm ensures that an overall feasible solution is obtained if one exists. Our computational results on a realistic network from the Chinese railway system with 83 stations, 158 links and 5700 randomly generated demands show that the proposed algorithm can derive high-quality solutions within a few hours of computation time. These solutions are on average 48.05% better than those obtained after solving the linear binary program with a commercial solver for 1 day.