A Column Generation Algorithm for Solving Wagon Flow Routing Optimization Problem

The wagon flow routes serve as the core foundation of traffic assignment in railway network planning and form the basis for designing train formation plans and train timetables. One significant challenge in railway transportation organization is how to quickly develop high-quality wagon flow routing schemes while considering complex constraints such as line capacity, with the aim of minimizing total transportation costs. Given the distinct tree structure of wagon flow routes, all the wagon flow towards the same destination station was considered as a whole, and the concept of in-tree was proposed. By doing so, the flow routing problem could be transformed into determining the in-tree scheme for each destination station (i.e., root node). On this basis, the classic arc-based multi-commodity flow model was reformulated using the in-tree selection variables. Subsequently, a two-stage solution approach was proposed in consideration of the structure of the reformulated model. The first-stage model aimed to generate a pool of promising in-tree schemes by using the column generation algorithm. The second-stage model was intended to select the best in-tree scheme for each root and obtain the wagon flow routes. Finally, by using basic data from the railway network in Southwest China, test instances of varying network scales were constructed to evaluate the algorithm’s performance. The results demonstrate that the proposed method can obtain near-optimal solutions within a short computation time. Compared to CPLEX, the column generation algorithm achieves higher solution efficiency; compared to a simulated annealing algorithm, it delivers better solution quality. The in-tree model exhibits lower model complexity and higher computational efficiency than the traditional arc-based model.