Discrete Optimization: Energy-Efficient Train Timetables
Presented by the Chair of EDOM (Economics – Discrete Optimization – Mathematics)
What is this challenge about?
Railway traffic is among the most energy-efficient modes of transport. However, it is still the biggest individual energy consumer in Germany. Its share of 2 % of the country’s total energy consumption equals that of the entire city of Berlin. Discrete optimization allows us to increase efficiency in various ways. This challenge focuses on timetables to create a better balance in the electric power supply and thereby also optimize the use of the recuperated energy from braking trains.
Interested? Get the full story below!
Railway traffic is the biggest individual electricity consumer in Germany. It amounts to 2 % of the country’s total electricity usage, which equals the consumption of the city of Berlin. However, the annual electricity cost (1 billion Euros per year) is not only determined by the total amount of energy used. Electricity contracts of big customers normally also incorporate a price component that is dependent on the highest power value drawn within the billing period, i.e. it depends on the timely distribution of the energy usage. This power component accounts for up to 20 % of the energy bill.
In the FAU Open Research Challenge “Energy-Efficient Train Timetables”, the aim is to optimize the timetables of railway traffic in order to avoid high peaks in power consumption as they lead to high electricity costs. This can be done by desynchronizing too many simultaneous departures as well as synchronizing accelerating trains with braking trains to make better use of the recuperated braking energy. Starting with a raw timetable (before its publication), the task is to shift the departures of the trains from the stations within small time intervals (several minutes) to come to the final optimized timetable.
Your goal is to compute optimal timetables with respect to the above goal. To this end, you are given problem instances featuring the following data:
A railway network in the form of a directed multi-graph
The planning horizon under consideration
A set of trains to schedule, and for each such train
the intermediate stations and tracks travelled
feasible departure intervals for each departure from a station
minimum stopping times in the stations (for getting on and off)
travel times for the tracks
power profiles for each track travelled , i.e. a time-power-curve
For each track in the network, the order in which it is passed by which trains
as well as the necessary safety distances.
The task is to ensure a favourable system-wide power load over the given planning horizon to minimize the power component of the electricity bill. The system-wide power load is determined by summing up all the individual power profiles of the trains under consideration. Obviously, this total power profile changes when shifting the trains in time. To minimize the power cost of the railway system, you have to minimize the average power drawn by all trains together over any consecutive 15-minute interval within the planning horizon.
To achieve this, your task is to come up with models and algorithms to optimize the departure times of the trains from the stations, keeping to the following requirements:
Each train travels the stations and tracks in the order given in data
Each train departure is within the feasible interval for the corresponding station
The minimum stopping time at each station is respected
The trains pass the tracks in the given order and respect the safety distances
Passenger connections at the stations are respected
The winning team for a given problem instance is the one with the lowest 15-minute average of power consumption over the planning horizon. This value is summed up over the 10 instances given in the contest. To win the whole contest, you have to be the team with the lowest overall value over these 10 instances.
Precise Description of the Optimization Problem
The degree of freedom in this optimization problem are the departure times of the trains from the stations. As a part of each problem instance (format description see readme file), you are given a series of train runs. Each of them consists of a series of legs, i.e. journeys between two consecutive stations at which the train stops. You are to adapt the current departure times to form a new timetable which has to respect several side constraints:
Maximal deviation from the current timetable: Each leg has an earliest and a latest possible departure time. The new departure has to lie in this interval.
Minimal stopping time: The description of each leg contains a minimum stopping time. This is the minimal time (in minutes) which the train has to wait at the destination of the leg before it can depart for the next leg. The corresponding value for the final leg can be ignored.
Safety distances: Each leg possesses a safety distance value (in minutes). This is the minimal time which the subsequent train passing the same track has to wait before it can depart for the corresponding leg. The order of the trains passing a given track has to be retained.
Passenger connections: At each station, we have to ensure that the passenger connections established in the original timetable are retained. If the arrival time of one train and the departure time of another lie in an interval of 5 to 15 minutes, their new arrival and departure times have to lie in this interval, too.
Under these timetable constraints, you are to find a new timetable that minimizes the system-wide power cost. The description of each leg contains (in a separate file) the time-power curve induced by the corresponding train. We assume that this curve as well as the travel time of the leg are fixed. Summation of the power curves for all trains over the complete planning horizon (starting at minute 0 and ending with the latest possible arrival time) leads to the system-wide power curve. Its power cost is determined by averaging its values over 15-minute intervals. The first such interval starts at minute 0, the next one at minute 15, etc. The power cost is now given by the value of the highest such 15-minute average multiplied by a constant cost factor. That means your objective is to minimize the highest arising 15-minute average of the system-wide power curve. Have fun!
NEW: Updates and specification to the problem description
Several of your questions in the forum have shown us that we need to clarify certain points of the problem description. Below you find a list of updates concerning the above description of the optimization problem. The list might be appended over time, when further clarification is needed. Your solutions have to fulfil the following requirements in addition to the above rules:
- Trains may only depart at full minutes in the planning horizon (which starts at minute zero, second zero). In the timetable data, you find an earliest and a latest departure time for each leg (given in full minutes). The departure time for this leg has to be a full minute from this interval.
- When computing the 15-minute averages , you have to set negative values of the summed, system-wide power curve to zero! If braking trains provide more energy than accelerating trains can use at the same time, this energy is lost. That means: You calculate the system-wide curve by summing over the individual curves of the trains, depending on their departure times. Then you compute the maximum of this curve and zero. And then you average over 15-minute intervals - the first of them starting at minute zero, second zero, and ending at minute 15, second zero, interval ends including (the next would start at minute 15, second zero and end at minute 30, second zero).
- The calculation of the 15-minute average power values follows the trapezoidal rule for the approximate calculation of integrals as described in the following. Each 15 minute-interval consists of 901 seconds (as the last second is also part of the next interval). Thus, to compute the average of the system-wide power curve, we sum over the 899 "inner" seconds of the interval (with weight 1) and add the value for the first and the last second with a weight of 1/2. This value is then divided by 900 - the length of the interval. The resulting value is the 15-minute average which is to be optimized (Explanation: without the division by 900, this value represent the total energy consumed by the trains over that interval - under the assumption that the system-wide power curve is a piecewise-linear function. Division by the length of the time interval yields the average power drawn from the system).
- To enable you to check the feasibility of your solutions and the correctness of your objective values, we provide you with a solution checker (download link below). It is written for Python 2.7 and is executed as follows: "python solution_checker.py instance-data-file power-data-file solution-file". Together with the solution checker, we also provide two sample solutions for instances 1 and 10 (which correspond to the initial timetable, i.e. to the "CurrentDepartureTimes"). Please submit all your solutions in the json-format as in these two examples. Basicly, you have to give one value (in minutes) for the departure time of each leg. Please pack your 10 solutions to one zip file before uploading.
You find the case material behind this link. Good luck!
Join the discussion or look for a team or team members >>HERE<< !
The final submission to this Challenge has to include the following:
- A feasible timetable for each given problem instance respecting all the above requirements with respect to the given data
- A report in form of a PDF file documenting your modelling of the problem as well as your solution approach
To join the challenge, also see the general rules for the FAU Open Research Challenge. Detailed information on the submission process for this challenge will be posted in time.
References and Reading Material
- Sansó, Girard: Instantaneous Power Peak Reduction and Train Scheduling Desynchronization in Subway Systems - Transportation Science 31, No.4, 1997
- Albrecht, Oettich: A new integrated approach to dynamic schedule synchronization and energy saving train control - Computers in Railways VIII. WIT Press, 2002
- Hansen, Pachl: Railway Timetabling & Operations – Eurailpress, 2nd edition 2014