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

摘要

合理安排铁路专用线取送车作业，对提高调车机车作业效率、加速货车周转具有重要的意义。在已知条件下，以机车在专用线间走行时间为权，把树枝形专用线取送车作业转换成哈密尔顿图最短路问题，指出其松弛问题为指派问题，应用匈牙利算法求出指派问题的最优解，再设计破圈连接法求出最佳可行的取送车顺序，并举例说明了模型构造及求解过程。