期刊文献+

树枝形专用线取送车问题哈密尔顿图模型及算法 被引量:4

Hamilton Model and Algorithm for Placing-in and Taking-out Wagon Problem on Branch-shaped Siding
下载PDF
导出
摘要 合理安排铁路专用线取送车顺序,对提高调车机车作业效率、加速货车周转具有重要的意义.在已知条件下,以机车在装卸点间走行时间为权,把树枝形专用线取(送)车作业优化问题转换成哈密尔顿图最短路问题,并松弛为指派问题,采用匈牙利算法求出指派问题的最优解,可得到最短回路路长的下界或最优解.若未得到最优解,再利用破圈连接法求出满意的取(送)车顺序,此算法的复杂度为O(n2).同时对送兼调移、取兼调移、取送结合、送调取结合作业形式进行了深入地讨论.最后举例说明了模型的构造及求解过程.大量小规模案例表明,该算法的平均复杂度及性能是比较优越的. Reasonable scheduling for placing-in and taking-out wagons in railway siding is of great significance to improve the operation efficiency of shunting locomotive and speeding up wagon's turnround. Under given conditions, taking the locomotive running time between sites as weights, the paper transforms the problem of placing-in(or taking-out) wagons into the shortest route problem of Hamilton graph and changed as assignment problem. The Hungarian algorithm is applied to calculate the optimal solution of the assignment problem. Then the lower bound or optimal solution of shortest route is obtained. If it is not a optimal solution, the broken-circle and connection method designed will be applied to find the satisfactory order of placing-in and taking-out wagons, and its computation complexity is O(n2). The paper simultaneously makes a deep discussion on other forms, such as placing-in and transferring combined, takingout and transferring combined, placing-in and taking-out combined, placing-in-transferring and taking-out combined. Finally, an example is given to illustrate the model's formulation and solution process. A large number of small cases also show that the algorithm's average complexity and performance is relative superior.
出处 《交通运输系统工程与信息》 EI CSCD 北大核心 2014年第5期105-109,139,共6页 Journal of Transportation Systems Engineering and Information Technology
关键词 铁路运输 取送车作业 破圈连接法 树枝形专用线 哈密尔顿图 railway transportation placing-in and taking-out wagons broken-circle and connection method branch-shaped siding Hamilton graph
  • 相关文献

参考文献4

二级参考文献21

  • 1石红国,彭其渊,郭寒英.树枝型专用线取送车问题的哈密尔顿图解法[J].中国铁道科学,2005,26(2):132-135. 被引量:25
  • 2王慈光.树枝形专用线取送车问题的研究[J].西南交通大学学报,1996,31(6):675-680. 被引量:14
  • 3Holland J H.Adaptation in natural and artificial system[M].Ann Arbur:University of Michigan Press,1975.
  • 4Dejong K A.Analysis of the behavior of a class of genetic adaptive systems[D].Ann Arbir:Univ of Michigan, 1975.
  • 5Goldberg D E,Lingle Jr R.Alleles,loci,and the traveling salesman problem[C]//Second Int Conf on Genetic Algorithms and Their Applications, 1985 : 154-159.
  • 6Goldberg D E, Jr Lingle R. Alleles, loci and the traveling salesman problem[C]//Second Int Conf on Genetic Algorithms and Their Applications Pittsburgh, 1985: 154-159.
  • 7Stutzle T, Hoos H H. MAX-MIN ant system[J]. Future Generation Computer System, 2000, 16(8): 889-914.
  • 8Dorigo M, Gambardella Luca Maria. Ant colony: a cooperative learning approach to the traveling salesman problem[/]. IEEE Trans on Evolutionary, 1997, 1(1): 53-66.
  • 9Chang P C, Huang W H, Ting C J. Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems[J]. Expert Systems with Applications, 2010, 37: 1863-1878.
  • 10Lee Z J, Su S F, Chuang C C, ctal. Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment[J]. Applied Soft Computing, 2008, 8: 55-78.

共引文献32

同被引文献34

引证文献4

二级引证文献14

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部