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

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

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

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.