On the problem of sorting railway freight cars

In this thesis the algorithmic foundations of a particular sorting problem from railway optimization are studied. The addressed problem is called train classification, and it refers to the fundamental procedure of rearranging the cars of several trains into other compositions of different orders comprising new trains. The train classification methods applied today present rather conservative approaches, and there is a lot of room for systematic improvement by applying optimization methods. The sorting processes are performed according to plans prepared in advance called classification schedules. They are conducted in specific railway facilities called classification yards. Without expensive redesigns of existing classification yards, the dwell time of railway cars can be reduced by accelerating the core classification process itself. To this aim, the combinatorial structure of the sorting processes are studied in this thesis in order to provide algorithmic solutions for the abstract problems derived from the practical setting with formal proofs of their efficiency. Conversely, the gained insights are applied to real-world problem instances to show that the theoretical approaches work in practice and improve on the methods applied today. First of all, a novel encoding of classification schedules is presented. This does not only yield an efficient representation of train classification schedules, but it also allows characterizing feasible classification schedules and is applied to derive an algorithm for computing optimal classification schedules for the core version of the sorting problem. Several practical problem settings then yield further restrictions on a feasible schedule, which are shown to translate to formal constraints in the above mentioned representation. Successful solution approaches are then developed for various infrastructural as well as operational constraints. The former particularly cover different dimensions of limited track space, the latter include train departures and track space varying over time. The approaches comprise efficient exact and approximation algorithms and also integer programming models that allow integrating several such constraints simultaneously. Then, another problem variant deals with the robustness aspect of uncertain input, which here corresponds to disruptions in the railway network resulting in trains arriving delayed at the classification yard. A model is introduced in which a prepared schedule that became infeasible by an arising disruption is adjusted by inserting some additional steps into the sorting process. Without any assumptions on the amount of disruption, this robust problem variant is shown to be NP-hard. Still, a generic method is provided for the general setting, from which an efficient algorithm for a realistic model of disruption is derived. The developed theoretical approaches are compared to each other and evaluated experimentally using various synthetically derived and real-world traffic instances to show that the achieved insights and solutions are relevant in practice.