DITTO Project Deliverable 2.2 – Milestone 5
Scenario generation for train timetabling and train scheduling under uncertainty
Tolga Bektas, Attila Kovacs, Chris Potts
University of Southampton, UK
November 2015
Abstract
In this project, we apply operational research techniques to insert new train services into existing timetables while taking into account reliability and punctuality. The optimisation process is performed in a stochastic environment in which trains are subject to random delays. Typically, the risk of propagating delays over the network is higher when the railway infrastructure is highly utilized, i.e., we can increase capacity only by deteriorating reliability. Additionally, it is unclear how to combine these goals into a common objective function (e.g., how much loss in reliability are we willing to accept for inserting one additional train?). This issue is resolved by applying a multi-objective framework that exploits a special characteristic of the problem, namely that the number of train services that can be inserted into the timetable is small.
The train timetabling and scheduling problem is modelled as a two-stage stochastic program: in the first stage, new trains are inserted into the timetable, following which the reliability of the new timetable is optimised in the second stage under various scenarios. The objective is to generate a new timetable with a higher use of operational capacity and with minimal expected delay. Realistic measures are incorporated to recover from delays, including changing the order in which trains leave the station and approach a platform, and reassignment of trains to different platforms if the initially assigned platform is blocked.
A case study is proposed by considering the rail network around Peterborough station. Delay scenarios will be based on historical records.
Acronyms
ACO: Ant colony optimisation.
DEP: Deterministic equivalent program.
FL: Fuzzy logic.
RO: Robust optimisation.
SA: Simulated annealing.
SAA: Sample average approximation.
SCOP: Stochastic combinatorial optimisation problems.
SP: Stochastic programming.
TS: Tabu search.
TSSIP: Two-stage stochastic integer program.
TTSP: Train timetabling and scheduling.
Technical Terms
Heuristics: fast solution algorithms yielding good quality solutions in a short amount of computation time; they are often used for hard optimisation problems.
Metaheursitics: high-level heuristics based on searching multiple solutions; they typically generate better solutions than heuristics.
Exact techniques: provide the best feasible, i.e., optimal, solution; they are rarely used in real-world applications as they might require very long computation times.
Random variable: a variable that can take on multiple values (e.g., the number of spots when rolling a dice) because of an uncertain environment.
Symbols and notation
Ε, ε / Greek epsilon; typically denoting a small positive number∈ / “element of” symbol
i ∈ N / Variable i is element of set N
N = {1,2,3} / Set N contains three elements: 1, 2, and 3
/ Summation: all elements of N are added up
/ Minimum in set N
/ Maximum in set N
Ω = {ω1, ω2, . . . , ωn} / Set of scenarios, omega. It contains n scenarios. E.g., the scenarios in coin flipping are heads and tails
P = {p1, p2, . . . , pn} / Set of probabilities associated with scenarios in Ω. In coin flipping, the set is {½ ,½}
Q(x) / Deterministic objective function Q depending on solution x
Q(x, ω1) / Objective function Q depending on solution x given scenario 1
/ Expected objective value over all scenarios Ω with associated probabilities P
1. Introduction
The aim of this project is to suggest an adequate response to the steadily growing railway traffic and to the increasing demand for high-quality transportation of passengers.
Clearly, a full passenger train is more cost effective and environmentally friendly than a half-full train. Yet, the rapid growth in passenger travel often results in overcrowded trains with dissatisfied customers. A common strategy to overcome the capacity problem, which is also considered in this project, is to offer more train services in a given time period (by increasing train frequency). A side benefit of this strategy is a greater flexibility for passengers in planning their journeys.
Reliability is the single most important requirement of passengers (Department for Transport [21]). It is expressed by the deviations from the current train timetable that are caused, for example, by bad weather conditions, prolonged boarding and alighting, and technical malfunctions.
Improving reliability and increasing operational capacity tend to be conflicting objectives (Armstrong and Preston [6], Preston et al. [42]). Typically, we cannot increase the number of services without causing reliability to deteriorate. We apply operational research techniques to insert as many new trains as possible into the system while complying with the safety regulations and maintaining reliability – measured by the average and maximum delay that is possibly caused by the new train services – at an acceptable level. In this work, we consider small delays, which are in the range of a few minutes as opposed to major disruptions. Increasing the speed of a train for example might compensate small delays; however, disruptions are unforeseeable events with a significant impact on the functionality of a railway system. Disruptions from accidents, broken tracks, malfunctioning signalling, etc., render the entire timetable infeasible. Effective countermeasures include cancelling trains, introducing alternative train services, and allocating replacement buses. Recovering from a major disruption in the shortest amount of time is a very hard optimisation problem that would exceed the scope of this project. For surveys on disruption management, we refer to Cacchiani et al. [18] and Jespersen-Groth et al. [34].
We make the following assumptions: First, when delays occur, they are mainly propagated at large stations with many incoming and outgoing trains. The track segments close to busy stations are highly utilised, thus causing many conflicts between trains (Armstrong et al. [7], Dollevoet et al. [22], Paraskevopoulos et al. [41]). This observation is also made in the DITTO Project Deliverable 2.1 (Armstrong and Preston [6]). Therefore, stations offer a great potential for mitigating delays. Second, trains are scheduled independently from each other, i.e., we ignore passengers transferring between trains. Third, travel and dwell times are random variables. Train timetables are typically generated with fixed buffer times inserted to protect against possible delays. Our work is based on the premise that it is possible to increase the operational capacity of a timetable with minor effects on the reliability if the uncertain nature of delays is taken into account explicitly. If the uncertainty of delays can be described by using probability distributions, then they can be treated as being stochastic. Stochastic optimisation methods set appropriate buffer times so as to increase the overall efficiency of the system. Figure 1 shows an illustrative example with a single platform and six nodes around it. The platform at the top of the figure is used by two trains a and b. Train a arrives from node 1, stops at the platform between nodes 3 and 4, and leaves the station towards node 5. Train b arrives from node 6, stops at the platform, and leaves in the direction of 2. The scheduled arrival times of a and b are 0 and 1 respectively. The dwell time for both trains is one unit of time, respectively. Headways are ignored for the purpose of this example. We assume that train a arrives on time with a probability of 4/5 and it is delayed by five time units with a probability of 1/5. In contrast, b is always on time. In a deterministic approach in which uncertainty is not taken into account, we estimate a reasonable realisation of the random variable denoting the arrival time of a and solve the problem. The estimated value is the mean of the random variable plus a small buffer ε (in our example ε is a value between 0 and 1). Accordingly, the deterministic arrival time of a is 1 + ε, and the optimal sequence in which trains are scheduled at the platform is first b (at time 1) and then a (at time 2). The evaluation of the deterministic solution in a stochastic context is depicted in the middle of the figure with an expected total delay of 2 ´ 4/5 + 5 ´ 1/5 = 2.6 time units. In the stochastic solution, however, which uses the probability information, the trains are scheduled in a reverse order: a first, b second, and has an expected total delay equal to (5 + 5) ´ 1/5 = 2 time units. The solution of the stochastic problem is shown at the bottom of the figure. In this example, therefore, the stochastic solution would be favoured over the deterministic solution, at least as far as the expected delay is concerned.
Given the high complexity of the operations performed at large railway stations as well as the stochastic environment in which decisions are made, we cannot expect to generate optimal solutions to the problem. Therefore, we propose a fast solution approach based on the tabu search heuristic algorithm developed by Paraskevopoulos et al. [41] in the course of the preceding OCCASION project. For this purpose, we first transform the train scheduling and timetabling problem into a job-shop problem of the type that is used in production management. Job-shop problems are well studied in the literature with numerous solution algorithms available, which provide a solid basis for solving our railway problem. Second, we embed the tabu search heuristic into a framework for stochastic optimisation. By examining the behaviour of the system under minor delay scenarios, we can select a solution (i.e., a timetable) that is robust with respect to many different realisations of the random variables.
Figure 1: Example: deterministic versus stochastic solution.
2. Related literature on stochastic optimisation
Our project combines two areas of operational research: stochastic optimisation and metaheuristic algorithms. The following sections give an overview of the state-of-the art.
2.1 Stochastic optimisation
A straightforward approach for solving stochastic optimisation problems is to replace random variables with expected values and apply an algorithm for the corresponding deterministic problems. This approach provides good solutions in short time when variations in the data are small. The cost of implementing the solution in reality would be only slightly lower or higher than the cost indicated by the model. When variations are large, however, ignoring uncertainty in the model often results in solutions that are extremely costly or even infeasible. In many applications, even simple stochastic optimisation approaches result in significantly better solutions. We expect this to be the case in railway operations. There is always some uncertainty, e.g., a train conductor might get sick, or boarding and alighting may take longer than planned. The full potential of the rail network can only be exploited if uncertainty is considered explicitly. Yet, integrating uncertainty into railway management is extremely demanding due to the complexity of the problems.
The challenge in optimisation under uncertainty is in formulating models that are realistic, but at the same time simple enough to be solved by modern solution techniques. The process of balancing these two goals has stimulated research that led to a large number of alternatives for formalising uncertainty. These alternatives are characterised, first, by the way uncertain information is incorporated into the models and, second, by the chronology of making decisions and learning about the realisation of the random variables (Bianchi et al. [11]). With regard to the first point, we distinguish several techniques. Stochastic optimisation is probably the most developed technique for considering uncertain information (Birge and Louveaux [14]). The main assumption is that uncertain data is represented by random variables with known probability distributions. In stochastic optimisation models, we typically minimise the expected value of the objective function or bound the probability of violating certain constraints.
Another common approach for dealing with uncertain parameters is robust optimisation (RO); for details, see Ben-Tal et al. [8]. RO models do not require the probability distributions of the uncertain data. In fact, RO models are deterministic; variations are modelled by providing a set of potential realisations of the uncertain data. RO is a worst-case oriented approach. The generated solution is feasible for each scenario in a given set, but is often very inefficient. Therefore, this approach is too conservative for many application areas.
Fuzzy logic (FL)) is a complementary technique to classical stochastic methods; for details, see Zimmermann [52]. In contrast to randomness, which is caused by chance mechanisms (e.g., flipping coins and rolling dice), fuzziness is the result of a subjective perception of events. Therefore, FL is often inappropriate for modelling uncertain information (Riedewald [45]).
Finally, uncertainty can be modelled as a stream of data that becomes gradually available to the decision maker – predictions about future data are impossible (Albers [1]). The solution algorithm, referred to as an online algorithm, generates solutions periodically based on partial information.
Our train timetabling and scheduling problem belongs to the class of stochastic combinatorial optimisation problems (SCOP) – a subclass of stochastic optimisation. Therefore, we will restrict the remainder of this section to SCOPs. Combinatorial optimisation problems have a finite, but usually large, decision space and solutions to the problem could be represented by permutations or binary variables. For example, a solution to the problem of scheduling trains at a station with a single platform could be the sequence in which trains stop at the platform, i.e., a permutation. Binary variables are often used to model yes-no decisions, e.g., to model whether or not a train is assigned to a particular platform.
SCOPs can be further categorised by the chronological order of receiving information and making decisions (Bianchi et al. [11]). In static SCOPs, decisions are made before the realisation of the random variables is known. The resulting solution is applied without any further modification, regardless of the actual outcome. Yet, sticking to the planned solution irrespective of the outcomes might be extremely costly or even infeasible. This issue is taken into account in dynamic SCOPs by making a decision without knowledge of the future, but taking a recourse action as more information becomes available. Dynamic SCOPs provide a convenient framework for making decisions at different planning levels. For example, trains are assigned to platforms before knowing the realisation of the random variables (e.g., arrival times) at the tactical planning level. However, trains may be reassigned if there is some delay at the operational level.