A fuzzy Petri net model to estimate train delays

Even with the most accurate timetable, trains often operate with delays. The running and waiting times for trains can increase unexpectedly, creating primary delays that cause knock-on delays and delays for other trains. The accurate estimation of train delays is important for creating timetables, dispatching trains, and planning infrastructures. In this work, we proposed a fuzzy Petri net (FPN) model for estimating train delays. The FPN model with characteristics of hierarchy, colour, time, and fuzzy reasoning was used to simulate traffic processes and train movements in a railway system. The trains were coloured tokens, the track sections were termed places, and discrete events of train movement were termed transitions. The train primary delays were simulated by a fuzzy Petri net module in the model. The fuzzy logic system was incorporated in the FPN module in two ways. First, when there were no historical data on train delays, expert knowledge was used to define fuzzy sets and rules, transforming the expertise into a model to calculate train delays. Second, a model based on the Adaptive Network Fuzzy Inference System (ANFIS) was used for systems where the historical data on train delays were available (from detection systems or from the train dispatcher’s logs). The delay data were used to train the neuro-fuzzy ANFIS model. After the results of the fuzzy logic system were verified, the ANFIS model was replicated by a fuzzy Petri net. The simulation was validated by animating the train movement and plotting the time-distance graph of the trains. Results of the simulation were exported to a database for additional data mining and comparative analysis. The FPN model was tested on a part of the Belgrade railway node.     

Analysing stability and investments in railway networks using advanced evolutionary algorithms

We consider a network of periodically running railway lines. Investments are possible to increase the speed and to improve the synchronisation of trains. The model also includes random delays of trains and the propagation of delays across the network. We derive a cost‐benefit analysis of investments, where the benefit is measured in reduced waiting time for passengers changing lines. We also estimate the actual mean waiting time simulating the train delays. This allows us to analyse the impact that an increasing synchronisation of the timetable has on its stability. Simulation is based on an analytical model obtained from queueing theory. We use sophisticated adaptive evolutionary algorithms, which send off avant‐garde solutions from time to time to speed up the optimisation process. As there is a high correlation between scheduled and estimated waiting times for badly synchronised timetables, we are even able to include the time consuming simulation into our optimisation runs.     

Urban rail transit planning using a two-stage simulation-based optimization approach

In urban metro systems, stochastic disturbances occur repeatedly as a result of an increment of demands or travel time variations, therefore, improving the service quality and robustness through minimizing the passengers waiting time is a real challenge. To deal with dwell time variability, travel time and demand uncertainty, a two-stage GA-based simulation optimization approach is proposed in order to minimize the expected passenger waiting times. The proposed method here has the capability of generating robust timetables for a daily operation of a single-loop urban transit rail system. The first stage of the algorithm includes the evaluation of even-headway timetables through simulation experiments. In the second stage, the search space is limited to the uneven-headway patterns in such a manner where the algorithm keeps the average of headways close to the best even-headway timetable, obtained from the first stage. The optimization is intended to adjust headways through simulation experiments. Computational experiments are conducted on Tehran Metropolitan Railway (IRAN) and the outcomes of optimized timetable obtained by this proposed method are demonstrated. This newly proposed two-stage search approach could achieve to a more efficient solution and speed up the algorithm convergence.     

Train Timetable Problem on a Single-Line Railway With Fuzzy Passenger Demand

The aim of the train timetable problem is to determine arrival and departure times at each station so that no collisions will happen between different trains and the resources can be utilized effectively. Due to uncertainty of real systems, train timetables have to be made under an uncertain environment under most circumstances. This paper mainly investigates a passenger train timetable problem with fuzzy passenger demand on a single-line railway in which two objectives, i.e., fuzzy total passengers' time and total delay time, are considered. As a result, an expected value goal-programming model is constructed for the problem. A branch-and-bound algorithm based on the fuzzy simulation is designed in order to obtain an optimal solution. Finally, some numerical experiments are given to show applications of the model and the algorithm.      

Generation of classes of robust periodic railway timetables

In this paper we discuss the problem of randomly sampling classes of fixed-interval railway timetables from a so-called timetable structure. Using a standard model for the timetable structure, we introduce a natural partitioning of the set of feasible timetables into classes. We then define a new probability distribution where the probability of each class depends on the robustness of the timetables in that class. Due to the difficulty of sampling directly from this distribution, we propose a heuristic sampling method and illustrate using practical data that our method indeed favors classes containing robust timetables over others.     

Solving a periodic single-track train timetabling problem by an efficient hybrid algorithm

Train timetabling with minimum delays is the most important operating problem in any railway industry. This problem is considered to be one of the most interesting research topics in railway optimization problems. This paper deals with scheduling different types of trains in a single railway track. The primary focus of this paper is on the periodic aspects of produced timetables and the proposed modeling is based on the periodic event scheduling problem (PESP). To solve large-scale problems, a hybrid meta-heuristic algorithm based on simulated annealing (SA) and particle swarm optimization (PSO) is proposed and validated using some numerical examples and an Iranian case study that covers the railway line between two cities of Isfahan and Tehran.     

A Case Study in Periodic Timetabling

In the overwhelming majority of public transportation companies, designing a periodic timetable is even nowadays largely performed manually. Software tools only support the planners in evaluating a periodic timetable, or by letting them comfortably shift sets of trips by some minutes, but they rarely use optimization methods. One of the main arguments against optimization is that there is no clear objective in practice, but that many criteria such as amount of rolling stock required, average passenger changing time, average speed of the trains, and the number of cross-wise correspondences have to be considered.This case study will demonstrate on the example of the Berlin underground (BVG) that all these goals can be met if carefully modeled, and that timetables constructed by optimization lead to considerable improvements.Our approach uses the Periodic Event Scheduling Problem (PESP) with several add-ons concerning problem reduction and strengthening. The resulting integer linear programs are solved with the CPLEX MIP-Solver. We have been able to construct periodic timetables that improve the current timetable considerably. For any of the above criteria, we have been able to identify global lower and upper bounds. Our favorite timetable improves the current BVG timetable in each of these criteria.     

A decomposition based hybrid heuristic algorithm for the joint passenger and freight train scheduling problem

We study the joint problem of scheduling passenger and freight trains for complex railway networks, where the objective is to minimize the tardiness of passenger trains at station stops and the delay of freight trains. We model the problem as a mixed integer program and propose a two-step decomposition heuristic to solve the problem. The heuristic first vertically decomposes the train schedules into a passenger train scheduling phase and then a freight train scheduling phase. In the freight train scheduling phase, we use a train-based decomposition to iteratively schedule each freight train. Experimental results show the efficiency and quality of the proposed heuristic algorithm on real world size problems.     

A Stochastic Process Approach for Frequency-based Transit Assignment with Strict Capacity Constraints

Transit assignment models represent the stochastic nature of waiting times, but usually adopt a deterministic representation route flows and costs. Especially in cities where transit vehicles are small and not operating to timetables, there is a need to represent the variability in flows and costs to enable planners make more informed decisions. Stochastic process (SP) models consider the day-to-day dynamics of the transit demand-supply system, explicitly modelling passengers’ information acquisition and decision processes. A Monte Carlo simulation based SP model that includes strict capacity constraints is presented in this paper. It uses micro-simulation to constrain passenger flows to capacities and obtain realistic cost estimates. Applications of the model and its comparison with the De Cea and Fernandez (Transp Sci, 27:133–147, 1993) model are presented using a small network.     

The periodicity and robustness in a single-track train scheduling problem

The most important operating problem in any railway industry is to produce robust train timetables with minimum delays. The train scheduling problem is defined as an application of job shop scheduling which is considered to be one of the most interesting research topics. This paper deals with scheduling different types of trains in a single railway track. The authors have focused on the robust and periodic aspects of produced timetables. This paper is also concerned with some applicable constraints, such as the acceleration and deceleration times, station capacity and headway constraints. The periodic timetable for railways is modeled based on the periodic event scheduling problem (PESP). Furthermore, a fuzzy approach is used to reach a tradeoff among the total train delays, the robustness of schedules, and the time interval between departures of trains from the same origins. To solve large-scale problems, a meta-heuristic algorithm based on simulated annealing (SA) is utilized and validated using some numerical examples on a periodic robust train scheduling problem. Finally, a robustness measure is defined in order to assure the effectiveness of the proposed SA to find robust solutions.     

Towards railway traffic management using switching Max-plus-linear systems

In this paper we present a railway traffic model and a model predictive controller for online railway traffic management of railway networks with a periodic timetable. The main aim of the controller is to recover from delays in an optimal way by changing the departure of trains, by breaking connections, by splitting joined trains, and - in the case of multiple tracks between two stations - by redistributing the trains over the tracks. The railway system is described by a switching max-plus-linear model. We assume that measurements of current running and dwell times and estimates of future running times and dwell times are continuously available so that they can be taken into account in the optimization of the system’s control variables. The switching max-plus-linear model railway model is used to determine optimal dispatching actions, based on the prediction of the future arrival and departure times of the trains, by recasting the dispatching problem as a Mixed Integer Linear Programming (MILP) problem and solving it. Moreover, we use properties from max-plus algebra to rewrite and reduce the model such that the MILP problem can be solved in less time. We also apply the algorithm to a model of the Dutch railway network.     

Reducing airport gate blockage in passenger aviation: Models and analysis

Commercial flights are typically assigned to an arrival gate at their destination station (airport) prior to their departure from their origin station. Although the gate is scheduled to be available when the flight arrives, this is not always the case in practice. Due to variability in departure and flight times, the arriving flight might arrive early, the previous flight departing from the gate might depart late, or both. When a flight arrives at its scheduled gate but has to wait because the preceding aircraft is still occupying that gate, we refer to this as gate blockage. Gate blockage can have many negative impacts, including passenger delays, missed connections, and increased fuel burn. Our research is focused on incorporating the inherent stochasticity of the system into the planning process to reduce the prevalence and impact of gate blockage. Specifically, we formulate an optimization problem to assign flights to gates so as to minimize the expected impact of gate blockage. We use historical data to predict delay distributions and conduct experiments to assess both the computational tractability of our approach and its potential for improvement in solution quality over existing approaches.     

Stability of systems with uncertain delays: a new "Complete" Lyapunov-krasovskii functional

Stability of linear systems with uncertain time-varying delay is considered in the case, where the nominal value of the delay is constant and nonzero. Recently a new construction of Lyapunov-Krasovskii functionals (LKFs) has been introduced: To a nominal LKF, which is appropriate to the system with nominal delays, terms are added that correspond to the perturbed system and that vanish when the delay perturbations approach 0. In the present note we combine a "complete" nominal LKF, the derivative of which along the trajectories depends on states and their derivatives, with the additional terms depending on the delay perturbation. The new method is applied to the case of multiple uncertain delays with one nonzero nominal value. Numerical examples illustrate the efficiency of the method.     

Ant colony optimization with immigrants schemes for the dynamic railway junction rescheduling problem with multiple delays

Train rescheduling after a perturbation is a challenging task and is an important concern of the railway industry as delayed trains can lead to large fines, disgruntled customers and loss of revenue. Sometimes not just one delay but several unrelated delays can occur in a short space of time which makes the problem even more challenging. In addition, the problem is a dynamic one that changes over time for, as trains are waiting to be rescheduled at the junction, more timetabled trains will be arriving, which will change the nature of the problem. The aim of this research is to investigate the application of several different ant colony optimization (ACO) algorithms to the problem of a dynamic train delay scenario with multiple delays. The algorithms not only resequence the trains at the junction but also resequence the trains at the stations, which is considered to be a first step towards expanding the problem to consider a larger area of the railway network. The results show that, in this dynamic rescheduling problem, ACO algorithms with a memory cope with dynamic changes better than an ACO algorithm that uses only pheromone evaporation to remove redundant pheromone trails. In addition, it has been shown that if the ant solutions in memory become irreparably infeasible it is possible to replace them with elite immigrants, based on the best-so-far ant, and still obtain a good performance.     

Non-Discriminatory Automatic Registration of Knock-On Train Delays

Incidents and waiting for train connections are registered by dispatchers as sources of train delays, but route and headway conflicts are not always clearly recognized. Moreover, traffic management and route setting are the primary task of dispatchers and signallers, whilst monitoring and incident registration is not allowed to take up too much of their time. This paper describes a tool that automatically and without discrimination identifies route conflicts and the train numbers involved. It is based on standard train describer and infrastructure messages recorded on the Dutch railway network. The logic of these messages is captured in a coloured Petri net (CPN) model on which a prototype tool for route conflict identification and estimation of knock-on delay has been developed.     

Flight operations recovery: New approaches considering passenger recovery

The sources of disruption to airline schedules are many, including crew absences, mechanical failures, and bad weather. When these unexpected events occur, airlines recover by replanning their operations. In this paper, we present airline schedule recovery models and algorithms that simultaneously develop recovery plans for aircraft, crews, and passengers by determining which flight leg departures to postpone and which to cancel. The objective is to minimize jointly airline operating costs and estimated passenger delay and disruption costs. This objective works to balance these costs, potentially increasing customer retention and loyalty, and improving airline profitability. Using an Airline Operations Control simulator that we have developed, we simulate several days of operations, using passenger and flight information from a major US airline. We demonstrate that our decision models can be applied in a real-time decision-making environment, and that decisions from our models can potentially reduce passenger arrival delays noticeably, without increasing operating costs.     

Exact formulations and algorithm for the train timetabling problem with dynamic demand

In this paper we study the design and optimization of train timetabling adapted to a dynamic demand environment. This problem arises in rapid train services which are common in most important cities. We present three formulations for the problem, with the aim of minimizing passenger average waiting time. The most intuitive model would consider binary variables representing train departure times but it yields to non-linear objective function. Instead, we introduce flow variables, which allow a linear representation of the objective function. We provide incremental improvements on these formulations, which allows us to evaluate and compare the benefits and disadvantages of each modification. We present a branch-and-cut algorithm applicable to all formulations. Through extensive computational experiments on several instances derived from real data provided by the Madrid Metropolitan Railway, we show the advantages of designing a timetable adapted to the demand pattern, as opposed to a regular timetable. We also perform an extensive computational comparison of all linear formulations in terms of size, solution quality and running time.     

A new conceptual structure for travel information

This paper describes how to improve dynamic transport timetables. Mostly, such information as departure time, gate number, platform number, intermediate stops, and delays is arranged per flight or train. Each train or flight has one line or one column. A field observation of passengers using such a system showed that presenting information in this fashion is not optimal. Of passengers, 38% were unable to find the correct departure time. We analysed the performance of passengers. This analysis suggested that the information should not be arranged per train or flight but per destination. Each train or flight has one line or one column. An empirical comparison supported this conclusion. When a destination-based structure was used, the number of correct answers was 16% higher, the delay of each passenger was 75% less, and the time needed to search for a train decreased by 42%.     

Variable and adaptive neighbourhood search algorithms for rail rapid transit timetabling problem

Supplying affordable and efficient transportation services to the users is one of the main tasks of the public transport systems. In this study, the objective is the minimization of the total and maximum waiting time of the passengers through optimization of the train timetables for urban rail transit systems. For this purpose, mixed-integer linear and non-linear programming models are developed which could solve the small to medium-sized test instances optimally. In order to tackle large instances, adaptive and variable neighbourhood search algorithms are designed based on different novel solution encoding schemes and decoding approaches. The effectiveness of the proposed models and solution methods are illustrated through the application to the Tehran intercity underground rail lines in IRAN. The outcomes demonstrate that the variable neighbourhood search algorithm outperforms the adaptive step-size neighbourhood search method in the different scenarios of the real case. Furthermore, the generated headway for the period of study result in a significant reduction in total waiting time of the passengers compared with the current baseline timetables.     

基于灵活编组的城轨车底运用计划及鲁棒客流控制策略

针对通勤客流需求的动态性、不均衡性和随机性等复杂特征,提出基于灵活编组的城轨车底运用计划及鲁棒客流控制策略两阶段随机规划模型.第1阶段为编组类型指派和车底运用计划优化模型,以极小化系统运营成本为目标;第2阶段为车站协同限流鲁棒优化模型,以极小化乘客等待时间为目标.通过线性化方法将原模型重构为可被CPLEX等优化软件直接求解的混合整数线性规划模型.算例结果表明,灵活编组模式在仅增加0.5%乘客等待时间的基础上,可降低约30.2%的系统运营费用,表明灵活编组方案在满足客流需求的同时可合理地降低运营费用.此外,所提出鲁棒客流控制策略能够避免传统鲁棒优化方法过于保守的问题,对于实际运营过程中随机客流需求具有较好的适应性.