交通运输系统工程与信息

交通运输系统工程与信息 ›› 2014, Vol. 14 ›› Issue (5): 105-109.

• 系统工程理论与方法 • 上一篇    下一篇

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

郭垂江*1，雷定猷2   

  1. 1. 湖南铁路科技职业技术学院运输管理学院，湖南株洲412000；2. 中南大学交通运输工程学院，长沙410075
  • 收稿日期:2014-02-19 修回日期:2014-04-15 出版日期:2014-10-25 发布日期:2014-12-17
  • 作者简介:郭垂江（1980-）男，湖南武冈人，讲师，博士生.

Hamilton Model and Algorithm for Placing-in and Taking-out Wagon Problem on Branch-shaped Siding

GUO Chui-jiang1, LEI Ding-you2   

  1. 1.College of Transportation Management, Hunan Vocational College of Railway Technology, Zhuzhou 412000, Hunan, China; 2. School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China
  • Received:2014-02-19 Revised:2014-04-15 Online:2014-10-25 Published:2014-12-17

PDF

摘要：

合理安排铁路专用线取送车顺序，对提高调车机车作业效率、加速货车周转具 有重要的意义.在已知条件下，以机车在装卸点间走行时间为权，把树枝形专用线取（送） 车作业优化问题转换成哈密尔顿图最短路问题，并松弛为指派问题，采用匈牙利算法求 出指派问题的最优解，可得到最短回路路长的下界或最优解.若未得到最优解，再利用破 圈连接法求出满意的取（送）车顺序，此算法的复杂度为O(n2).同时对送兼调移、取兼调 移、取送结合、送调取结合作业形式进行了深入地讨论.最后举例说明了模型的构造及求 解过程.大量小规模案例表明，该算法的平均复杂度及性能是比较优越的.

关键词: 铁路运输, 取送车作业, 破圈连接法, 树枝形专用线, 哈密尔顿图

Abstract:

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.

Key words: railway transportation, placing- in and taking- out wagons, broken- circle and connection method, branch-shaped siding, Hamilton graph

中图分类号: