Exact Methods for Solving the Train Departure Matching Problem

Jørgen Thorlund Haahr, Simon Henry Bull

    Research output: Book/ReportReport

    606 Downloads (Pure)


    In this paper we consider the train departure matching problem which is an important subproblem of the Rolling Stock Unit Management on Railway Sites problem introduced in the ROADEF/EURO Challenge 2014. The subproblem entails matching arriving train units to scheduled departing trains at a railway site while respecting multiple physical and operational constraints. In this paper we formally define that subproblem, prove its NP- hardness, and present two exact method approaches for solving the problem. First, we present a compact Mixed Integer Program formulation which we solve using a MIP solver. Second, we present a formulation with an exponential number of variables which we solve using column generation. Our results show that both approaches have difficulties solving the ROADEF problem instances to optimality. The column generation approach is however able to generate good quality solutions within a few minutes in a heuristic setting.
    Original languageEnglish
    PublisherDTU Management Engineering
    Number of pages18
    Publication statusPublished - 2015


    Dive into the research topics of 'Exact Methods for Solving the Train Departure Matching Problem'. Together they form a unique fingerprint.

    Cite this