基于Greedy方法的动态配流模型与近似算法

为研究寻优能力强、求解效率高且可及时调整的动态配流智能化编制方法，构建了基于Greedy算法的多阶段决策模型.以编组顺序为准依次划分阶段，提出了根据各阶段Δti（将最晚编组时刻和最早解体时刻之差与解体标准作业时间作求余运算所得之值）动态划分解体区间的方法；在解体区间内，以当前阶段待编列车的车流需求为匹配目标，设计了5种依据不同规则与策略的最优解体列车选择算法；将各阶段决策变量依次组成序列，得到最终的解体顺序.选取不同策略或改变参数，进行了8组对比实验，结果表明:简单规则和策略无法保证解的质量，匹配度选择算法的优劣取决于解体区间数量与解体列车选择策略；在基于R_PPCD2（根据当前阶段车流资源与后续阶段所需车流的去向匹配度选择解体列车的策略）的算法中，适当调整解体时间、编组作业时间、出发车作业时间等参数，可以在2 s内寻找到该NP难问题的一个高质量近似解. 

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.