Constraint Propagation and Heuristics Backtracking Algorithm for Static Wagon-Flow Allocation at a Marshalling Station

In order to improve the efficiency of stage planning, a hybrid algorithm was designed to solve the lexicographic multi-objective cumulative scheduling model of the static wagon-flow allocation problem at a marshalling station. The proposed algorithm is based on iteration method, constraint propagation technique and heuristic backtracking. The whole model is divided into three layers according to the lexicographical order of the multi-objective. The total priorities of the on-time outbound trains is maximized in the first sub-model, minimizing the total number of the inbound trains providing cars to each outbound trains is the objective in the second sub-model, while, the average dwell time of railcars in the station should be decreased as possible in the final sub-model. Firstly, each sub-model is simplified and the search space is reduced by constraint propagation algorithm. Then, the optimal solution is searched fast by the combined algorithm of heuristic backtracking and constraint propagation. In the lower sub-model, the optimal solution of the upper sub-model is considered as the initial solution, and the constraint is added to avoid degradation of the optimal value of the upper objective, so that the whole model is solved by the iteration algorithm. Experiment results from a marshalling station show that the total running time of the algorithm is less than 20 s, which meets the real-time requirements of scheduling in the field, and the algorithm can solve a better wagon-flow allocation solution compared with other algorithms.