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 given a car route for each shipment. The TFP considers both the block design and the car-to-block assignment in the tactical level. 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 sum of train cost and classication delay subject to limitations on the classication 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 rst decompose the whole network into a series of rooted trees for each destination separately. Then, we divide the trees into suciently 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 nd their optimal solutions. 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 3 hours. These solutions are on average 43.89% better than those obtained after solving the linear binary program for 1 day.