Model and Approximation Algorithm for Dynamic Wagon-Flow Allocation Based on Greedy Strategy

To develop a method for the intelligent generation of dynamic wagon-flow allocation, which can search and solve efficiently and timely perform adjustment, the multi-stage decision model was built based on greedy algorithm. By dividing the decision process into several stages of the marshaling sequence, a division method was proposed for dynamically sorting intervals in each stage according to Δti, which is the value of the difference between the final formation time and the earliest sorting time mod standard break-up operation time. For each sorting interval, with train demand used as matching targets, five optimal selection algorithms of sorting trains were designed on the basis of different rules and strategies. The decision variables in each stage were queued to form the final sequence of sorting trains. Comparison tests of 8 groups show that simple rules and strategies can not guarantee a desirable solution, and whether a selection algorithm of matching targets is suitable depends on the number of sorting intervals and the selection strategy of sorting trains. Using the R_PPCD2-based algorithm (R_PPCD2 is a strategy which selects the sorting train by the matching degree of wagon-flow's orientation between the current stage and other remaining stages), a high-quality approximate solution for this type of NP-hard problem can be found in 2 s by proper adjustment of parameters such as break-up operation time, marshalling operation time, departure operation time.