Overview
Train Rescheduling Problem
Typically, there is the information about the planned (daily) schedule for a railway line and the current schedule that reflects the actual arrival and departure times of trains until the current moment as well as a forecast. Due to some disturbances, several trains can be delayed which would cause conflicts between the trains on tracks, i.e. at least two trains want to occupy a track at the same time. The Train Rescheduling Problem contains the current schedule and its goal is to find a new schedule for the intermediate future, e.g. an hour, so that there are no conflicts between trains any more. Additionally, an optimization statement can be considered, e.g. minimization of the total delay of traffic, the accumulated delay that passenger suffer, the end times at end stations or the overall deviation from the original schedule.
As a real-life benchmark for the Train Rescheduling Problem, we use the rail network of Madrid (Renfe Cercanias Madrid). The rescheduling instance is given as an XML-file (Madrid rescheduling instance). In the rescheduling instance, the network comprises 93 block sections (tracks) and is used by 475 trains in an operational period of 20 hours. More information about the network can be found in Espinosa-Aranda & García-Ródenas (2013).
The input for the Train Rescheduling Problem contains the current schedule of trains in a network including the current time. Every train event that starts earlier the current time shows how the trains moved in the past. Every train event that starts at or after the current time shows a forecast of how the trains will move in the future (possibly containing conflicts). In addition to the current schedule, some information about the trains occurring in network is given. This information includes route information (on which tracks a train is going), stations to stop, time to occupy a track, time to stay at stations, a start station and a destination station.
A solution of the problem is a feasible schedule (solved schedule) for each train that says how the train should move in the future so that there are no conflicts between trains on tracks. Feasible arrival and departure times for each train on a track are obtained by delaying a train on a track and by considering possible alternative routes for a train. We consider a decision problem (no optimization).
Input format
minTime(MINSEC) : minimal start time for a schedule
maxTime(MAXSEC) : maximal end time for a schedule
minDelay(MINDELAY) : minimal possible delay for a train on a track
maxDelay(MAXDELAY) : maximal possible delay for a train on a track
current_time(TIME) : the current time in the network
track(TRACK) : tracks that occur in the network
track_next(TRACK1,TRACK2,DIRECTION) : TRACK1 is followed by TRACK2 in a certain DIRECTION, defines the topology of the network
station(STATION) : stations in the network
station_tracks(STATION,TRACK) : tracks of a station
train(TRAIN) : trains that must be scheduled
train_start(TRAIN,STATION) : start station of a train
train_destination(TRAIN,STATION) : end station of a train
route_direction(TRAIN,DIRECTION) : direction of the route of a train
route_first(TRAIN,TRACK) : first track of a trains' route
route_next(TRAIN,TRACK1,TRACK2) : TRACK2 follows TRACK1 in the route of TRAIN
route_last(TRAIN,TRACK) : last track of a trains' route
train_stay(TRAIN.STATION,STAY) : duration of planned stops of a train
train_timeontrack(TRAIN,TRACK,TIMEONTRACK) : duration of a train running on a track (is defined for all tracks)
current_schedule_begin(TRAIN,TRACK,BEGIN) : start time of a train on a track in the current schedule
current_schedule_end(TRAIN,TRACK,END) : end time of a train on a track in the current schedule
Output format
solved_schedule_begin(TRAIN,TRACK,BEGIN) : start time of a train on a track for the solved schedule (for clingo-4 system)
solved_schedule_begin(TRAIN,TRACK)=BEGIN : start time of a train on a track for the solved schedule (for clingcon, ezcsp system and gringo-4 + constraints)
solved_schedule_end(TRAIN,TRACK,END) : end time of a train on a track for the solved schedule (for clingo-4 system)
solved_schedule_end(TRAIN,TRACK)=END : end time of a train on a track for the solved schedule (for clingcon, ezcsp system and gringo-4 + constraints)
train_trackoccupation(TRAIN,TRACK,OCCUPATION) : duration of a train occupying a track (run + stay)
Example
The example comprises 4 trains, 2 stations and 10 tracks. All trains are going in the same direction and occupy the same tracks: tracks t1-1, t2-1 and t3-1. The track topology looks as follows:
The current time is 7. Train 1 is delayed on track t1-1, therefore the forecast for this train has a conflict with train 4 on track t3-1. The visualization of the current schedule is given below:
The full input data of the example is as follows:
|
minTime(0). |
ASP output will look like:
|
train_trackoccupation("train1","t1-1",3) train_trackoccupation("train1","t1-2",3) |
No route changes were made, but train 1, train 4 and train 3 were delayed on track t2-1 in order to resolve the conflict. Note that there is no optimization criterion. A visualization of the answer set is presented below.
The encodings which resolve conflicts by only delaying trains on tracks are available here (ASP), here (gringo-4 + constraints), here (CASP: clingcon) and here (CASP: ezcsp).
The encodings which resolve conflicts by delaying trains and finding alternative routes for them are available here (ASP), here (gringo-4 + constraints) and here (CASP: clingcon). Note that there is no encoding for ezcsp because, for computing alternative routes, we used choice rules which are not supported in ezcsp.
The complete instance of the Madrid rail network can be found here.
Benchmarks of the Madrid rail network split into 1-hour intervals can be found here.
References:
- Espinosa-Aranda & García-Ródenas (2013): A demand-based weighted train delay approach for rescheduling railway networks in real time. Journal of Rail Transport Planning & Management. Volume 3. Issues 1–2. Pages 1–13.