Hybrid Algorithm of Constraint Propagation and Multi-point Constructive Search for the Dynamic Wagon-flow Allocation Problem at a Railway Marshalling Station

To improve the versatility and stability of the dynamic wagon-flow allocation model, the dynamic wagon-flow allocation lexicographic multi-objective cumulative scheduling model is set up to maximize the sum of priority of the departure trains, minimize the average residence time of the cars, and maximize the resource utilization, based on the theory of constraint programming cumulative scheduling and lexicographic multi-objective optimization. In this model, the precedence and logical relationship among traffic jobs, the demands of the train shift plan and the train formation plan, and the capacity limit of the resources are all taken into account as constraints. The model is then be adapted for different disassembly modes and is divided into three sub-layers, according to the lexicographic order of the three objectives. Then, the optimized schemes of job scheduling and wagon-flow allocation are received by solving the model iteratively, using the hybrid algorithm of constraint propagation and multi-point constructive search. In each sub-layer, the search space is initially reduced by constraint propagation and then the solution is achieved by a multi-point constructive search algorithm with constraint propagation. This new model's instance validation results indicated that this algorithm is more scalable, realistic, and stable. Furthermore, this algorithm is proved to be very efficient, with solve times that are potentially appropriate for real-time applications.