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

郭瑞; 郭进; 苏跃斌; 马亮

doi:10.3969/j.issn.0258-2724.2014.04.024

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

doi: 10.3969/j.issn.0258-2724.2014.04.024

郭瑞^1,2,
郭进¹,
苏跃斌¹,
马亮¹

基金项目:

国家自然科学基金资助项目（61203175）

铁道部科技研究开发计划重点课题（2010X010-F）

计量
- 文章访问数: 965
- HTML全文浏览量: 51
- PDF下载量: 451
- 被引次数: 0
出版历程
- 收稿日期: 2013-06-28
- 刊出日期: 2014-08-25

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

摘要

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

HTML全文

参考文献(15)

王慈光. 运输模型及优化[M]. 2版. 成都:西南交通大学出版社,2010: 46-98.

何世伟,宋瑞,朱松年. 编组站阶段计划解编作业优化模型及算法[J]. 铁道学报,1997,19(3): 1-8. HE Shiwei, SONG Rui, ZHU Songnian. Optimal model and algorithm on stage plan of sorting and marshalling operation for marshalling station[J]. Journal of the China Railway Society, 1997, 19(3): 1-8.

严余松,朱松年. 铁路枢纽车流调度决策模型研究[J]. 铁道学报,2001,23(1): 9-12. YAN Yusong, ZHU Songnian. Study on models of wagon flow's dispatching decision in railway termal[J]. Journal of the China Railway Society, 2001, 23(1): 9-12.

牛惠民. 双向编组站列车调度调整的优化模型及算法[J]. 中国铁道科学,2007,28(6): 102-108. NIU Huimin. Optimal model and algorithm for adjusting the dispatching plan of trains operated at double-direction classification yards[J]. China Railway Science, 2007, 28(6): 102-108.

王正彬,杜文,吴柏青,等. 基于解编顺序的阶段计划车流推算模型及算法[J]. 西南交通大学学报,2008,43(1): 91-95. WANG Zhengbin, DU Wen, WU Baiqing, et al. Model and algorithm for estimation of wagon flow of stage operating plan based on break-up and make-up sequences[J]. Journal of Southwest Jiaotong University, 2008, 43(1): 91-95.

赵军,彭其渊,文超,等. 技术站广义动态配流问题的局部邻域搜索算法[J]. 西南交通大学学报,2010,45(3): 486-492. ZHAO Jun, PENG Qiyuan, WEN Chao, et al. Local neighborhood search algorithm for generalized dynamic wagon-flow allocation of railway technical stations[J]. Journal of Southwest Jiaotong University, 2010, 45(3): 486-492.

景云,王慈光. 不确定条件下编组站动态配流模型及算法研究[J]. 铁道学报,2010,32(4): 8-12. JING Yun, WANG Ciguang. Model and algorithm of dynamic wagon-flow allocating in a marshalling yard under uncertain conditions[J]. Journal of the China Railway Society, 2010, 32(4): 8-12.

赵军,彭其渊,文超,等. 技术站广义动态配流问题的遗传算法[J]. 铁道学报,2010,32(3): 9-15. ZHAO Jun, PENG Qiyuan, WEN Chao, et al. Genetic algorithm for solution to generalized dynamic wagon-flow allocation problem with technical railway stations[J]. Journal of The China Railway Society, 2010, 32(3): 9-15.

黎浩东,何世伟,王保华,等. 铁路编组站阶段计划编制研究综述[J]. 铁道学报,2011,33(8): 10-17. LI Haodong, HE Shiwei, WANG Baohua, et al. Survey of stage plan for railway marshalling station[J]. Journal of the China Railway Society, 2011, 33(8): 10-17.

黎浩东,何世伟,景云,等. 考虑不同满轴约束的编组站阶段计划配流优化[J]. 铁道学报,2012,34(7): 10-17. LI Haodong, HE Shiwei, JING Yun, et al. Wagon-flow allocatioon optimization of stage plan at marshalling station in consideration of different size limitation of departure trains[J]. Journal of the China Railway Society, 2012, 34(7): 10-17.

王慈光. 编组站动态配流模型与算法研究[J]. 铁道学报,2004,26(1): 1-6. WANG Ciguang. Research on the model and algorithm of dynamic wagon flow allocating in a marshalling station[J]. Journal of the China Railway Society, 2004, 26(1): 1-6.

薛锋,王慈光,张展杰. 编组站配流的协调优化算法[J]. 西南交通大学学报,2010,45(6): 932-937. XUE Feng, WANG Ciguang, ZHANG Zhanjie. Optimization algorithm for wagon-flow allocation in marshalling station[J]. Journal of Southwest Jiaotong University, 2010, 45(6): 932-937.

薛锋. 铁路编组站配流协同优化模型与算法[J]. 系统工程理论与实践,2013,33(11): 2930-2936. XUE Feng. Collaborative optimization model and algorithm for wagon-flow allocation in railway marshalling station[J]. Systems Engineering: Theory & Practice, 2013, 33(11): 2930-2936.

刘敏. 工业编组站解体车列选定的模糊综合评[J]. 铁道学报,2002,24(2): 932-937. LIU Min. Fuzzy synthetic evaluation of choosing optimum from trains to be disintegrated in industrial marshalling station[J]. Journal of the China Railway Society, 2002, 24(2): 932-937.

HOROWITZ E, SAHNI S, RAJASEKARAN S. 计算机算法:C++版[M]. 冯博琴,叶茂,高海昌,等译. 北京:机械工业出版社,2006: 117-118.

施引文献

附加材料(0)

访问统计

点击查看大图

计量

文章访问数: 965
HTML全文浏览量: 51
PDF下载量: 451
被引次数: 0

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

doi: 10.3969/j.issn.0258-2724.2014.04.024

计量

出版历程

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

计量

出版历程

目录