Annals of Computer Science and Information Systems, Volume 15

DOI: http://dx.doi.org/10.15439/2018F26

Citation: Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 15, pages 227–231 (2018)

Full text

Abstract. Rearranging cars of an incoming train in a hump yard is a widely discussed topic. We focus on the train marshalling problem where the incoming cars of a train are distributed to a certain number of sorting tracks. When pulled out again to build the outgoing train, cars sharing the same destination should appear consecutively. The goal is to minimize the number of sorting tracks. We suggest a graph-theoretic approach for this NP-complete problem. The idea is to partition an associated directed graph into what we call pseudochains of minimum length. We describe a greedy-type heuristic to solve the partitioning problem which, on random instances, performs better than the known heuristics for the train marshalling problem.

References

1. K. Beygang, F. Dahms, and S. O. Krumke, “Train marshalling problem - algorithms and bounds,” University of Kaiserslautern, Tech. Rep. 132, 2010.
2. W. Hiller, Rangierbahnhöfe. Berlin: VEB Verlag für Verkehrswesen, 1983.
3. M. Giger, “Rangierbahnhof Limmattal,” SWISS ENGINEERING STZ AUTOMATE NOW!, vol. 1-2, pp. 93–94, 2010.
4. R. S. Hansmann, Optimal Sorting of Rolling Stock. Göttingen: Cuvillier, 2011.
5. Y. Zhu and R. Zhu, “Sequence reconstruction under some order-type constraints,” Scientia Sinica (A), vol. 26(7), pp. 702–713, 1983.
6. E. Dahlhaus, P. Horak, M. Miller, and J. Ryan, “The train marshalling problem,” Discrete Applied Mathematics, vol. 103(1-3), pp. 41–54, 2000. [Online]. Available: https://doi.org/10.1016/s0166-218x(99)00219-x
7. L. Brueggeman, M. Fellows, R. Fleischer, M. Lackner, C. Komusiewicz, Y. Koutis, A. Pfandler, and F. Rosamond, “Train marshalling is fixed parameter tractable,” in Fun with Algorithms, E. Kranakis, D. Krizanc, and F. Luccio, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 51–56. [Online]. Available: https://doi.org/10.1007%2F978-3-642-30347-0_8
8. E. Dahlhaus, F. Manne, M. Miller, and J. Ryan, “Algorithms for combinatorial problems related to train marshalling,” Proceedings of AWOCA 2000, Hunter Valley, pp. 7–16, 2000.
9. K. Beygang, On the Solution of Some Railway Freight Car optimization Problems. München: Dr. Hut, 2011.
10. F. Rinaldi and R. Rizzi, “Solving the train marshalling problem by inclusion–exclusion,” Discrete Applied Mathematics, vol. 217, Part 3, pp. 685 – 690, 2017.
11. J. T. Haahr and R. M. Lusby, “A matheuristic approach to integrate humping and pullout sequencing operations at railroad hump yards,” Networks, vol. 67, no. 2, pp. 126–138, 2016.
12. J. Dörpinghaus, Pseudostabile Mengen in Graphen. Fraunhofer Verlag, 2018. [Online]. Available: https://kups.ub.uni-koeln.de/8066/