The Train Unit Shunting Problem with Reallocation

This thesis is concerned with formulating the Train Unit Shunting Problem (TUSP) with Reallocation (TUSP-R) as an MIP and solving it using exact solution methods. The TUSP has been formulated as an MIP in several different ways in previous works, but reallocation was never incorporated. Exactly solving the TUSP-R proved to be very challenging, so a method using a combination of the exact solution method row generation and the heuristic method tabu search was developed which solved the real life instances for shunting yard Utrecht OZ in acceptable solution times. The instances for a simplified version of Kleine Binckhorst were solved up to a certain problem size; hereafter the computation times became too long for practical use. Our method performs best for problem instances with diverse train types and relatively many different services on a LIFO style shunting yard layout. This keeps the size of the constraint matrix of the initial problem without crossing constraints relatively small compared to other types of problem instances.