Integrated optimization of train makeup problem and resource scheduling in railway marshalling yards: A hybrid MILP-CP approach with Logic-based Benders decomposition

Abstract

In the marshalling yard, various complex operations occur, leading to inefficiencies in railcar connections. Therefore, designing an effective operational research methodology is essential for the marshalling yard, and even for the local rail freight network. This paper addresses the integrated Train Makeup and Resource Scheduling (TMRS) problem. A Mixed-Integer Linear Programming (MILP) model is developed, where the train makeup problem is formulated as an assignment problem, guiding the overall operations. Additionally, a series of hybrid flow shop scheduling tasks are established to coordinate the operations of trains, blocks, and railcars. Due to the complexity of TMRS, the integrated problem is reformulated as a hybrid mixed-integer linear programming (MILP) and constraint programming (CP) model. Logic-based benders decomposition (LBBD) is used to partition the TMRS problem, with lower bounds designed and integrated into the solving procedure to accelerate the convergence. We propose feasibility cuts, optimality cuts, and symmetry cuts based on the structure of the subproblem, which are dynamically added to the master problem. Two numerical examples are designed to demonstrate the effectiveness of the proposed hybrid modelling approach, lower bounds, and cuts. Finally, the proposed approach and algorithm are tested on a series of artificial instances and real-scale examples, demonstrating their practical effectiveness and ability to achieve high-quality solutions.

Peiran Han

PhD candidate of Railway Operations

My research interests include railway yard operation optimization, train (re)scheduling and timetable robustness/resilience.