CAJ | 학술논문

合理安排铁路专用线取送车顺序，对提高调车机车作业效率、加速货车周转具有重要的意义。在已知条件下，以机车在装卸点间走行时间为权，把树枝形专用线取（送）车作业优化问题转换成哈密尔顿图最短路问题，并松弛为指派问题，采用匈牙利算法求出指派问题的最优解，可得到最短回路路长的下界或最优解。若未得到最优解，再利用破圈连接法求出满意的取（送）车顺序，此算法的复杂度为O(n2)。同时对送兼调移、取兼调移、取送结合、送调取结合作业形式进行了深入地讨论。最后举例说明了模型的构造及求解过程。大量小规模案例表明，该算法的平均复杂度及性能是比较优越的。
합리안배철로전용선취송차순서，대제고조차궤차작업효솔、가속화차주전구유중요적의의。재이지조건하，이궤차재장사점간주행시간위권，파수지형전용선취（송）차작업우화문제전환성합밀이돈도최단로문제，병송이위지파문제，채용흉아리산법구출지파문제적최우해，가득도최단회로로장적하계혹최우해。약미득도최우해，재이용파권련접법구출만의적취（송）차순서，차산법적복잡도위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 turn-round. 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, taking-out 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.