Closing the loop between data mining and fast decision support for intelligent train scheduling and traffic control

. HNSEN

(Delft University of Technology, Delft 2628CD，the Netherlands )

Abstract：The existing Big Data of transport flows and railway operations can be mined through advanced statistical analysis and machine learning methods in order to describe and predict well the train speed, punctuality, track capacity and energy consumption. The accurate modelling of the real spatial and temporal distribution of line and network transport, traffic and performance stimulates a faster construction and implementation of robust and resilient timetables, as well as the development of efficient decision support tools for real-time rescheduling of train schedules. In combination with advanced train control and safety systems even (semi-) automatic piloting of trains on main and regional railway lines will become feasible in near future.

Keywords:intelligent train rescheduling; train control; big railway data; statistical learning; robust timetabling

1 Introduction

Every day, a huge amount of data on the actual transport flows containing the number, origin and destination of railway passengers, cargo and trains is collected and saved by railway undertakings. Simultaneously, signals, track circuits, axle counters, interlocking machines, radio block centres, substations and on-board units generate and communicate automatically billions of real-time messages on the actual occupation of the railway infrastructure and rolling stock, respectively. The digital data is filtered, selected and used for line planning, timetabling, traffic control, failure, incident/accident detection and maintenance scheduling in order to ensure safe, punctual and efficient train operation, as well as reliable customer and management information.

The enormous size and speed of new information requires very powerful data processing, storage and analysis tools to be understood and handled well by the railway personnel and staff. Which kind of data is now relevant for intelligent train scheduling, traffic management and customer information? Above all, the compilation and communication of safety-related vital data must be assured so that the responsible staff members can take appropriate decisions quickly, if necessary. This means any signalling and safety system data affecting thereal-time train detection, safe route interlocking, headway calculation, train control and movement authority are crucial. Non-vital data, as regular passenger and cargo flow information, train delay records or commercial advertisement may be transmitted later on and analysed off-line.

However, the capability, reliability and speed of on-line information recognition, evaluation and decision making of the railway personnel involved in train driving, scheduling and traffic control is limited. Depending on the traffic density and trains’ speed, actual environmental conditions (weather, visibility, noise), clarity of the information, complexity of the operator’s task, and personal professional experience the reaction time of train drivers and traffic/signal controllers varies considerably. In general, a well-trained driver of a conventional train is expected to start braking if a signal aspect changes to yellow or red within a few seconds. Ergonomic and empirical research on the work load and the time to take a decision of train drivers and railway dispatchers/traffic controllers, respectively is still very rare[1-2].

The main barriers for a successful development and implementation of intelligent decision support tools for real-time train scheduling and traffic control are:

2)High robustness, accuracy, computation and communication speed of real-time rescheduling and driver advisory tools;

3)Insufficient performance evidence and end user acceptance in daily practice;

4)Missing clarity and easy understanding of the user interface and output;

5)Diverging political, business and social interests of stakeholders.

The objective of the following section is to describe briefly, how some complex and routine human tasks for timetabling, train dispatching and traffic management can be performed through more efficient computerized decision support systems.

2 Promising computerized decision support approaches

2.1 Statistical learning

Principal train operations times, such as running/headway/dwell/arrival/departure/delay times, can be monitored and analysed rather easily based on automatically generated train detection, signalling and safety system data (track occupation/clearance, signals, switches, route set-up/release, movement authority). Updating of scheduled process times was done in the past mostly only when timetables changed, new rolling stock was employed or obviously proved infeasible by simply increasing the scheduled times here and there. Instead, the distributions of the main train operations times should be analysed regularly offline in order to estimate their statistical fitting and standard parameters that may be used for the ex-post evaluation of timetable quality and train operations performance, as well as for a consistent, more accurate adaptation of the scheduled train operations times. By the way, the probability distribution of running times and dwell times are generally right-skewed due to scheduled supplements and possible headway and route conflicts. Arrival delays seem to fit lognormal and gamma distributions, while departure delays fit well to negative exponential, Weibullor gamma density distributions[3].

Online prediction of train operation times requires the use of sophisticated statistical learning methods. For this purpose Multiple Linear Regression (MLR), Regression Tree (RT), and Random Forest (RF) models have been tested for the estimation of running times and dwell times, respectively, on a local and a global level[4]. The local model described the variation of running times of trains of the same line over a particular lock section, while the global model aggregated the process times of all recorded trains into two separated test sets for running times and dwell times, respectively. The process times of the trains which had been hindered by preceding trains or route conflicts have been filtered out, so that only conflict-free running times have been included in the data set. As the models must be robust against outliers, models that can cope with errors are favoured compared to models with high variance that may overfit the data. The prediction accuracy of the trained models for running times was significantly less than for dwell times, because the former depend only weakly from train delays, while arrival delays and variation of passenger volume between peak and off-peak periods impact strongly on the latter. The prediction error of the global models was clearly higher than of the local models. Comparing the accuracy of the different methods, the least-trimmed squares (LTS) method for robust linear regression outperformed the RM model and even more clearly the RT model for, both, running time and dwell time.

Once she was somewhat disappointed on hearing that we had decided17 to wait for two years before getting married, but when she learned that my father and mother were both pleased with the match she seemed reassured18

2.2 Robust timetabling

Four main approaches for timetabling can be distinguished: graphical, analytical, simulation models, and combinatorial optimization models.

1)Graphical timetable models like time-distance diagrams of scheduled train arrival and departure times at stations and platform track occupation times are standard means to illustrate the planned movement of trains and the use of track infrastructure generally at macroscopic scale (minutes, kilometres). Train diagrams are also used to examine quickly the timetable feasibility based on the expected transport demand (train frequency and speed) and required (minimum) headway times on each line. However, the discretisation steps of macroscopic graphical timetable models are too big for describing accurately the impact of technical and safety constraints concerning track alignment, signalling, interlocking and train dynamics on track capacity[5].

2)So far, railway timetables are based principally on deterministic running, dwell and headway times between stations. Small variations of the service times are compensated by standard running time and dwell time supplements, as well as margins (buffer times) between the train paths. The determination of supplements and buffer times in practice is mainly based on rules of thumb, sometimes validated by simulation. Queuing models enable to estimate the waiting time of a timetable as a function of track occupancy and the coefficients of variation of the scheduled headway and service times of individual lines and simple stations. Major stations with multiple tracks and routes may be modelled as multi-channel service systems. However, the type, properties and parameters of the distributions of stochastic analytical models need to be validated by means of statistical analysis of real-world operations data[6-7]. Scheduled waiting times generated by stochastic variables of the timetable must be clearly distinguished from estimated original and consecutive delays during operations. In particular on densely occupied, strongly interconnected networks this may lead to underestimation of the delay propagation, because the real train speed and service time of the signaling and safety systems at headway and route conflicts are mostly unknown. The distributions of headway times at arrivals and service times in stations, in fact, are stochastically interdependent.

3)Macroscopic simulation models used for the estimation of varying train trip and dwell times cannot estimate accurately the impact of specific rules of operation, different signalling and safety systems, block signal spacing, local speed restrictions, interlocking of signals and routes, train length, braking and acceleration, (minimum) headway times, and delays experienced in station areas. In the worst case, tight train schedules might even become infeasible and train delays, in fact, would be underestimated. That is why microscopic timetable simulation models have been developed and implemented in several European railway networks and countries[8]. Headway and route conflicts, use of track capacity and the propagation of primary and consecutive delays are computed on the basis of so called blocking time diagrams at a scale of seconds and metres, thus being 60 times more precise than before[9].

4)Combinatorial optimization models aim at solving the formulated (timetable) problem for a certain objective function under predefined constraints to optimality and, thus, generating an optimal design for individual train departure and arrival times in a network. They are computed via (Mixed) Integer Linear Programming ((M)ILP) by means of a general-purpose solver or, if intractable, by heuristic methods using e.g. Branch-and-Bound or Lagrangian relaxation. When the scope of the investigated railway network and data exceeds the computation memory and speed for solving the timetable problem a hybrid optimisation approach integrating macroscopic global network timetable optimisation and microscopic simulation of local/regional networks offers a loophole[10-11]. In general, optimisation models apply deterministic variables for searching the (near) optimal value of the objective function as minimisation of overall running times in networks at given constraints like minimum headway and transfer times between train are also validated insufficiently. The feasibility of the given scheduled train running times and minimum headway times is often not proven with respect to conflict-free train routing in multi-track stations, while the exact track occupation, size, allocation and use of timetable slack remains unknown. An exemption is the recent iterative approach for constructing an innovative conflict-free and passenger robust routing plan and microscopic timetable for complex railway station areas from scratch, which enables a smart allocation of buffer times and supplements[12]. However, the running times and safety headway times are still treated as given timetable design input and the train speed profiles are not optimised. Essential graphical output for the evaluation of train schedules in form of e.g. standard time-distance, speed-distance and headway time distributions is missing in most mathematical programming publications, which is an important barrier for their application in practice.

2.3 Real-time rescheduling

Smaller train delays (one to two minutes) are recovered automatically due to existing running time supplements (at least 3 % on top of the minimum technical running time) and knock-on delays are avoided or reduced by buffer times (at least one minute) provided in the timetable. Larger delays of individual trains may disturb the train traffic, while technical failures lead mostly to disruptions of train operations at least in one direction lasting longer than one hour. Real-time rescheduling models can support dispatchers and traffic controllers in recognizing and solving route conflicts quickly. Regular train delays that lead to congestion of trains at junctions and stations and may propagate over (parts of) the network, so far, are handled locally by simple dispatching measures (holding, rerouting, reordering, cancellation) based on experience. Major disruptions due to technical failures, very bad weather or accidents are managed by (centralised) traffic controllers using (static) contingency plans. On densely occupied lines, in particular single track sections every disruption reduces the track capacity significantly so that cancelling some train services is unavoidable. The efficiency of the dispatching decisions may be sub-optimal, because they are fed only by radio communications, limited visual network traffic incident information and cannot predict well the impact of their measures on the local and regional network traffic.

During the past decade, a few computerised real-time rescheduling tools have been developed that can and must generate quickly (near) optimal timetables for disturbed/disrupted local and regional networks[13-20].

Real-time rescheduling models need to address and solve subsequently:

1)Data loading from and communications with the signalling, safety, traffic control and interlocking systems.

2)Route assignment to each train.

3)Detection and resolution of potential headway and route conflicts.

4)Determination of exact arrival and departure times at the borders of the network, intermediate stations, and relevant signals/junctions/crossings.

5)Adaptation of speed profiles.

None of these tools was connected, communicated and tested until today in real-time with data processors and traffic control operators of railway undertakings. All tools had to compile previously saved copies of log files containing the train schedules, signal box and interlocking messages as input data for testing. The output was then computed offline in laboratories, because the railway undertakings still hesitated to let test and demonstrate the use of rescheduling tools simultaneously in real world traffic control operations. That means the proposed dispatching measures in case of incidents and new real-time traffic plans could not be presented online to traffic controllers on duty in order to be confirmed or rejected and the performance of the rescheduling tool be compared with the dispatching decisions made by dispatchers.

Nonetheless, an innovative framework for closed-loop control of railway traffic during perturbations has been developed and demonstrated recently by means of simulation in case studies on four main railway corridors in United Kingdom, the Netherlands, Sweden and Norway[21]. Optimal Real-Time Traffic Plans based on traffic predictions over a given optimisation horizon have been computed and presented to a human dispatcher by means of a Human-Machine Interface. If accepted, the plans can be implemented directly by an Automatic Route Setting module through setting up the optimised train routes and transmitting speed advices for energy-efficient driving by the Driver Advisory System. Two different conflict detection and resolution modules (ROMA and RECIFE) have been adopted for the simulated Iron Ore line in Sweden/Norway in order to compare their performance.

The existing models for (optimised) rerouting and rescheduling in case of incidents and (partial) track blockage differ with regard to scope (often restricted to a few standard (passing) routes within interlocking areas), discretisation (macro-/meso-/microscopic infrastructure; train length and operation time steps (position, speed, acceleration, deceleration)), and discrete event or synchronous computation of track occupation/clearance, interlocking times with(out) partial route release, headway and corresponding blocking times. The applied mathematical integer programming methods for route and headway conflict detection range from e.g. Alternative (job-shop disjunctive graphs with train speed coordination[14-16], Bi-level Resource Tree Conflict Graph[17], Resource-based set-packing with speed alteration on entrance of block sections[18]to Mixed-integer linear program without speed variations (Pellegrini). In general, heuristic algorithms are needed to solve the rerouting and rescheduling problem within short time (one to two minutes) in order to satisfy the dispatcher’s tasks. The preferred objectives of the real-time rescheduling models may be minimization of ① (maximum) consecutive train delays, ②consecutive passenger delays or ③priority weighted timetable deviation. The minimization of total train delays is also used as objective. However, this objective is infected by primary delays, which occur independently from applying a rescheduling tool, whereas it can reduce the amount of knock-on delays more or less.

2.4 Driver advisory systems

Train drivers cannot precisely determine the earliest and latest time to start coasting and braking in order to maximize energy-saving and to arrive just on time, respectively. Only well trained and experienced train drivers know the amount of available running time supplement of their trains’ trip and may recover (partly) from delays. Current train Driver Advisory Systems (DAS), if applied on top of Automatic Train Protection (ATP)/Automatic Train Control (ATC) systems, are bound to the simple communication of the amount of actual train delay (scaled in minutes) and predetermined local speed advices for regular train operation without considering the impact of actual train delays and traffic congestion in the network. Some Urban Rail Rapid Transit systems in Europe, North America and Japan have implemented on-board a kind of Automatic Cruise Control (ACC) that controls continuously the individual trains’ acceleration, actual speed and deceleration according to the nominal speed profile, distance travelled, traction/braking force and safety headway required.

Intelligent driver advisory systems can make use of real-time traffic information generated by the signalling and safety systems, which are communicated via digital radio/Radio Block Centre (RBC) to the central traffic control unit. Flexible speed advices are required in particular for densely occupied railway lines operated by a mix of trains with different maximum speed levels and stop patterns, heavily loaded (freight) trains and at abnormal weather conditions. The central traffic control unit then computes and transmits globally optimised speed profiles in real-time to the on-board unit of each train involved in order to generate conflict-free and energy-optimal speed advices at local level. The DAS system architecture may be central, intermediate or on-board depending on where the re-computation of speed trajectories and speed advices, respectively, takes place[22]. The development of intelligent algorithms for the ①real-time prediction of train event times, ② computation and communication of accurate advisory speed changes based on optimal speed profiles ③at open track sections and in interlocking areas is a very challenging actual research topic[23-25]. Proven DAS systems can assure conflict-free train operations, reduce train delays, improve punctuality of train services and save energy. The advisory speed information is not-vital and would be overruled by the ATP/ATC system in case of over-speed, headway or route conflict.

3 Conclusions

The attractiveness, transport volume and market share of the railways increase, if the capacity of the infrastructure, quality of train services, accuracy and reliability of real-time process information was improved. This can be achieved by an integrated approach for lifting the treasure of existing Big Railway Data through sharing transport, technical, operations, safety and business data, developing advanced statistical analysis and learning methods in order to describe and predict better the determinants of real train speed, punctuality, capacity and energy consumption. Further research on the spatial and temporal distribution of railway transport, traffic and performance line by line, as well as local, regional and national networks, will stimulate the development, test and faster implementation of robust timetables, while the introduction of efficient decision support tools for real-time rescheduling of train schedules can minimise the impact of incidents and disruptions on capacity and quality of operations. The dedicated railway infrastructure and high performance of train control and safety systems favours automatic piloting of main line and even regional trains[26].

The most important actual barriers for faster and (near optimal) re-planning of railway operations in case of traffic disturbances and disruptions are not limited technical resources or computational power, but current human competences of timetable planners, train drivers and traffic controllers, as well as organisational barriers due to the separation between infrastructure management and train operating companies. The reticence of human actors against innovative train driving and rescheduling can be resolved by information, training and incentivising. The elimination of organisational barriers in the railway industry require wise political governess dominated by societal aims and not by fragmented business goals.