Multiple Solution Approaches for the Assignment of Train Units

In this thesis, we discuss different solution approaches for the train unit assignment problem (TUAP). The TUAP covers the aspect of distributing train units over a known timetable. The goal is to minimise the costs of the used train units while the capacity of the train units must exceed the estimated demand. In this paper, we first discuss a mixed-integer linear program which could solve the TUAP exactly. Afterwards, we discuss the peak period heuristic as introduced by Cacchiani et al. (2019). This heuristic defines the peak period of a timetable as a set of so-called incompatible trips and iteratively tries to search for the least cost solution. Then we come up with a heuristic which is similar to the exact formulation of the set cover problem. However, instead of considering all possible routes, we only use a smaller subset of 'significant' routes, such that the problem is also solvable for larger instances within sufficient time. Finally, we come up with a local search algorithm which can improve the outcome of any given feasible solution. This local search technique checks for a randomly chosen trip, whether there is an alternative composition of train units, which decreases the total costs until no further improvements can be found. We compare these heuristics with the exact formulation and observe that the performance of the peak period heuristic is relatively poor. The results of the set cover heuristic and local search are decent. However, the exact formulation still solves the instances optimally within an acceptable time.