基于MTSP的机车周转图编制模型与算法

Model and Algorithm for Making Locomotive Working Diagram Based on Multiple Traveling Salesmen Problem

为了提高机车的工作效率,探讨了机车周转图编制模型与算法.对于给定的列车运行图,综合考虑机车使用台数最少和图形均衡性,提出了一种编制机车周转图的新算法.将机车周转图编制问题转化为多旅行商问题(MTSP)并建立数学模型,从而求得问题的最优解.最后,用列车运行图实际数据进行了验证,证明了该算法的有效性.

To improve the working efficiency of locomotives, model and algorithm for making locomotive working diagrams were investigated. To a given train diagram, a new algorithm for making a locomotive working diagram with the minimum number of locomotives used and the equilibrium of time was proposed. A locomotive working diagram was transformed to a multiple traveling salesmen problem, and its mathematical model was set up to gain the optimum solution. Actual train diagram data have proven that this algorithm is useful to obtain the optimal equilibrium of a locomotive working diagram with a minimum locomotive number.