Model and algorithm for wagons' placing-in and taking-out problem in railway station

摘要

Taking the locomotive running time between goods operation sites as weights, wagons' placing-in and taking-out problems can be regarded as a single machine scheduling problem 1 | p_(ij)| C_(ij), which can be transformed into a shortest cycle problem of Hamilton graph whose relaxation problem is assignment problem. Firstly, we use a Hungarian algorithm to calculate the optimal solution of the assignment problem. Then we provide a Broken-circle and Connection method to find the available order of placing-in and taking-out wagons. The complexity of the algorithm is O(n~2). Extensive problems such as placing-in and transferring combined or taking-out and transferring combined, placing-in and taking-out combined, placing-in, transferring and taking-out combined, can also be resolved with the modified model and algorithm. At last, an instance is given to illustrate the model and the algorithm's reliability and efficiency.