Our approach is to use a decomposition technique that reduces the problem into smaller sub-problems associated with the line and the stations. This decomposition is the basis for a master-slave solution algorithm, in which the master problem is associated with the line and the slave problem is associated with the stations.
The two sub-problems are modeled as mixed integer linear programs, with specific sets of variables and constraints. Similarly to the classical Benders' decomposition approach, slave and master communicate through suitable feasibility cuts in the variables of the master.
In a general picture a rail network may be viewed as a set of stations connected by tracks. Each train runs through an alternating sequence of stations and tracks (train route); each route also includes the movements performed by a train within each station. Trains run along their routes according to the production plan, that specifies the movements (routing) and the times when a train should enter and leave the various segments of its route (schedule), including station arrival and departure times, which define the official timetable. Even if the production plan (timetable) ensures that no two trains will occupy simultaneously incompatible railway resources, one or more trains can be delayed and potential conflicts in the use of resources may arise.
In short, the RTD amounts to establishing, for each controlled train and in real-time, a route and a schedule such that no conflicts occur among trains and some measure of the deviation from the official timetable is minimized. As such, the RTD falls into the class of job shop scheduling problems, where trains correspond to jobs and the occupation of a railway resource is an operation.
In disjunctive formulations, continuous variables are associated with the starting times of operations, whereas a conflict is represented by a disjunctive precedence constraint, namely, two standard precedence constraints one of which (at least) must be satisfied by any feasible schedule. A disjunctive graph, where disjunctions are represented by pairs of directed arcs, can be associated to such disjunctive formulation and its properties can be exploited in solution algorithms. This type of disjunctive formulations can be easily casted into mixed integer linear programming models by associating a binary variable with every pair of (potentially) conflicting operations and, for any such variables, a pair of big-M precedence constraints representing the original disjunction. These constraints contain a very large coefficient and tend to weaken the overall formulation, which is the main reason why (TI) formulations were introduced.
Back to archive