Optimal Sorting of Rolling Stock

This thesis is concerned with the problem of optimally rearranging objects, in particular, railcars in a rail yard. The work is motivated by a research project of the Institute of Mathematical Optimization at Technische Universität Braunschweig, together with our project partner BASF, The Chemical Company, in Ludwigshafen. For many variants of such rearrangement problems ¿ including the real-world application at BASF ¿ we state the computational complexity by exploiting their equivalence to particular graph coloring, scheduling, and bin packing problems. We present mathematical optimization methods for determining schedules that are either optimal or close to optimal, and computational results are discussed from both a theoretical and practical point of view. In addition to the railway industry, there are other fields of application in which efficiently rearranging, sorting, or stacking is an important issue. For instance, the results obtained in this thesis could also be applied to solving certain piling problems in warehouses or container terminals.