Usually, the Train Scheduling Problem consists of two main sub-problems: a routing problem where tracks are assigned to trains and a scheduling problem where arrival and departure times for each track of each train are determined. Additionally, a distinction can be made between freight and passenger trains. Possible objective functions are minimization of waiting times of passengers at stations, minimization of train delays or minimization of fuel costs; cf. Cordeau et al. (1998). Train delays can occur for example if a start time and an end time of a train's route are given, but it is not possible to schedule the train within the given time interval.

We consider the second sub-problem mentioned above where the sequence of tracks for the trains has already been given. The input for the Train Scheduling Problem contains a certain number of trains and some additional information for each train. This information includes route information (on which track a train is going), stations to stop, minimal time to occupy each track, minimal time to stay at stations as well as a start station and a destination station. The main constraint is that two trains are not allowed to occupy a track at the same time.

A solution of the problem is a planned schedule for each train w.r.t. a given route. In particular, feasible arrival and departure times for each train on a track are calculated. We consider a decision problem (no optimization).

As a real-life benchmark for the Train Scheduling Problem, we use the rail network of Madrid (Renfe Cercanias Madrid). To have several test sets with different complexity levels we generated scheduling test instances based on the Madrid rescheduling instance (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).

Input format

minTime(MINSEC) : minimal start time for a schedule
maxTime(MAXSEC) : maximal end time for a schedule
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)

Output format

planned_schedule_begin(TRAIN,TRACK,BEGIN) : the start time of a train on a track (for clingo-4 system)
planned_schedule_begin(TRAIN,TRACK)=BEGIN : the start time of a train on a track (for clingcon, ezcsp system and gringo-4 + constraints)
planned_schedule_end(TRAIN,TRACK,END) : the end time of a train on a track (for clingo-4 system)
planned_schedule_end(TRAIN,TRACK)=END : the end time of a train on a track (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 full input data is as follows:

ASP output will look like:

A visualization of this answer set is presented below.

The encodings are available here (ASP), here (gringo-4 + constraints), here (CASP: clingcon) and here (CASP: ezcsp).

Benchmarks based on the Madrid rail network can be found here.

References:

• Cordeau et al. (1998): A Survey of Optimization Models for Train Routing and Scheduling. Transportation Science 32. Volume 4. Pages 380–404.
• 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.