A model predictive control approach for discrete-time rescheduling in complex central railway station areas

Railway networks are operated more and more at capacity margins, schedules are becoming more susceptible to disturbances, and delays propagate and hamper the service level experienced by the customers. As a consequence railway traffic management is becoming increasingly challenging, thus motivating the development of computer-aided systems. This paper proposes a dispatching assistant in the form of a model predictive control framework for a complex central railway station area. The closed-loop discrete-time system suggests rescheduling trains according to solutions of a binary linear optimization model. The model assigns precomputed blocking-stairways to trains while respecting resource-based clique constraints, connection constraints, platform related constraints and consistency constraints with the objective of maximizing customer satisfaction. In collaboration with the Swiss Federal Railways (SBB), the approach was successfully applied for an operational day at the central railway station area Berne, Switzerland. The model is capable of considering many alternative routing possibilities and departure timings, a potential of our approach, which can also be deduced from computational results.     

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.     

基于闭塞区间的高速列车运行时间与节能协同优化方法

提出了一种高速列车运行时间与节能协同优化方法.针对由动态调度层、优化控制层、跟踪控制层组成的列车运行控制与动态调度一体化结构,设计了面向动态调度层和优化控制层的列车运行时间调整策略和节能速度位置曲线.基于高速铁路闭塞区间,建立了列车区间模型和列车速度曲线节能优化模型.利用模型预测控制方法对列车区间运行时间进行调整,优化列车总延误时间;根据调整后的区间运行时间设计列车运行优化速度位置曲线,减少列车运行能耗.仿真算例验证了设计的运行时间与节能协同优化策略的有效性.     

Rescheduling trains with scenario-based fuzzy recovery time representation on two-way double-track railways

Severe weather conditions and inherent uncertainties in various components of railway traffic systems can lead to equipment breakdown and reduced capacity on tracks and stations. This paper formulates a two-stage fuzzy optimization model to obtain a robust rescheduling plan under irregular traffic conditions, and a scenario-based representation is adapted to characterize fuzzy recovery time durations on a double-track railway line. The model aims to minimize the expected total delay time in the rescheduled train schedule with respect to the original timetable. Two decomposed sub-models are further developed corresponding to the trains in different directions, and then GAMS optimization software is used to obtain the robust rescheduling plan. The numerical experiments demonstrate the effectiveness of the proposed approaches.     

A variable neighbourhood search for fast train scheduling and routing during disturbed railway traffic situations

This paper focuses on the development of metaheuristic algorithms for the real-time traffic management problem of scheduling and routing trains in complex and busy railway networks. This key optimization problem can be formulated as a mixed integer linear program. However, since the problem is strongly NP-hard, heuristic algorithms are typically adopted in practice to compute good quality solutions in a short computation time. This paper presents a number of algorithmic improvements implemented in the AGLIBRARY optimization solver in order to improve the possibility of finding good quality solutions quickly. The optimization solver manages trains at the microscopic level of block sections and at a precision of seconds. The solver outcome is a detailed conflict-free train schedule, being able to avoid deadlock situations and to minimize train delays. The proposed algorithmic framework starts from a good initial solution for the train scheduling problem with fixed routes, obtained via a truncated branch-and-bound algorithm. Variable neighbourhood search or tabu search algorithms are then applied to improve the solution by re-routing some trains. The neighbourhood of a solution is characterized by the set of candidate trains to be re-routed and the available routes. Computational experiments are performed on railway networks from different countries and various sources of disturbance. The new algorithms often outperform a state-of-the-art tabu search algorithm and a commercial solver in terms of reduced computation times and/or train delays.     

An effective Lagrangian relaxation approach for rescheduling a steelmaking-continuous casting process

This paper studies a steelmaking-continuous casting (SCC) rescheduling problem with machine breakdown and processing time variations. Two objectives are considered in this study: the efficiency objective and the stability objective. The former refers to the total weighted completion time and total sojourn time, whereas the latter refers to the number of operations processed on different machines in the initial and revised schedules. We develop a time-index formulation and an effective Lagrangian relaxation (LR) approach with machine capacity relaxation to address the rescheduling problem. The LR approach decomposes the relaxed problem into batch-level subproblems with variable processing times. A polynomial two-stage dynamic programming algorithm is proposed to solve the batch-level subproblems. An efficient subgradient algorithm with global convergence is presented to solve the corresponding Lagrangian dual (LD) problem. Computational experiments based on practical production data show that the proposed approach not only produces a high quality schedule within an acceptable time but also performs much better than a practical SCC rescheduling method from a large iron and steel enterprise in China.     

高速铁路运行控制与动态调度一体化的现状与展望

高速铁路运行控制系统是高速铁路的大脑和神经系统, 对列车的安全和高效运行至关重要. 随着我国高铁里程数和客运量的快速增加, 现有的控制手段和调度方法在快速、有效解决列车运行过程中出现的突发事件(比如电力故障、突发地震、山体滑坡、异物侵限等)方面尚有一定差距. 目前列车运行控制与调度采用分层架构, 突发情况下主要依赖调度员和司机的人工经验进行应急处置, 列车晚点时间较长, 旅客满意度不高. 因此, 如何针对高速列车运行过程中可能出现的突发事件, 提升其应急处置能力, 成为保障高铁安全高效运营的一大难题. 本文围绕高铁运行控制与动态调度一体化这一前沿研究热点, 对现有运行控制和动态调度的发展现状进行梳理, 在此基础上给出一体化的基本架构, 明确其基本内涵, 最后提出了未来的主要研究方向.     

An anticipative scheduling approach with controllable processing times

In practice, machine schedules are usually subject to disruptions which have to be repaired by reactive scheduling decisions. The most popular predictive approach in project management and machine scheduling literature is to leave idle times (time buffers) in schedules in coping with disruptions, i.e. the resources will be under-utilized. Therefore, preparing initial schedules by considering possible disruption times along with rescheduling objectives is critical for the performance of rescheduling decisions. In this paper, we show that if the processing times are controllable then an anticipative approach can be used to form an initial schedule so that the limited capacity of the production resources are utilized more effectively. To illustrate the anticipative scheduling idea, we consider a non-identical parallel machining environment, where processing times can be controlled at a certain compression cost. When there is a disruption during the execution of the initial schedule, a match-up time strategy is utilized such that a repaired schedule has to catch-up initial schedule at some point in future. This requires changing machine–job assignments and processing times for the rest of the schedule which implies increased manufacturing costs. We show that making anticipative job sequencing decisions, based on failure and repair time distributions and flexibility of jobs, one can repair schedules by incurring less manufacturing cost. Our computational results show that the match-up time strategy is very sensitive to initial schedule and the proposed anticipative scheduling algorithm can be very helpful to reduce rescheduling costs.     

A Train Dispatching Model Under a Stochastic Environment: Stable Train Routing Constraints and Reformulation

After major capacity breakdown(s) on a railway network, train dispatchers need to generate appropriate dispatching plans to recover the impacted train schedule from perturbations and minimize the expected total train delay time under stochastic scenarios. In this paper, we propose a cumulative flow variables-based integer programming model for dispatching trains under a stochastic environment on a general railway network. Stable Train Routing (STR) constraints are introduced to ensure that trains traverse on the same route across different capacity breakdown scenarios, which are further reformulated to equivalent linear inequality constraints. Track occupancy and safety headways are modelled as side constraints which are dualized through a proposed Lagrangian relaxation solution framework. The original complex train dispatching problem is then decomposed to a set of single-train and single-scenario optimization subproblems. For each subproblem, a standard label correcting algorithm is embedded for finding the time dependent least cost path on a space-time network. The resulting dual solutions can be transformed to feasible solutions through priority rules. Numerical experiments are conducted to demonstrate the efficiency and effectiveness of the proposed solution approach.     

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.     

Train scheduling and circulation planning in urban rail transit lines

This paper proposes a two-stage optimization approach to optimize the train schedule and circulation plan with consideration of passenger demand for an urban rail transit line. A train scheduling model is based on the operation of train services, which results a mixed integer nonlinear programming problem. Moreover, a train circulation model is formulated to adjust the departure and arrival times obtained by the train scheduling model to reduce the number of trains required, which results in a mixed integer linear programming problem. The case study based on the Beijing Yizhuang line illustrates the effectiveness of the proposed model and solution approach.     

A feasible timetable generator simulation modelling framework for train scheduling problem

An important problem in management of railway systems is the train scheduling/timetabling problem. This is the problem of determining a timetable for a set of trains that do not violate track capacities and satisfy some operational constraints. In this study, a feasible timetable generator framework for stochastic simulation modelling is developed. The objective is to obtain a feasible train timetable for all trains in the system. The feasible train timetable includes train arrival and departure times at all visited stations and calculated average train travel time. Although this study focuses on train scheduling/timetabling problem, the developed simulation framework can also be used for train rescheduling/dispatching problem if this framework can be fed by real time data. The developed simulation model includes stochastic events, and can easily cope with the disturbances that occur in the railway system.     

列车运行调度方法的研究与分析

将列车运行调度的相关研究按列车运行图编制和列车运行调整两方面进行分类,介绍列车单双线区段和客运专线的运行图编制方案,分析列车运行实时调整、列车插入(取消)服务及冲突预测方法,探讨研究列车运行自动调度系统的实时性和智能性、突发条件下列车运行的疏解方案、节假日高峰情况下列车运行调度等问题的重要性。     

From timetabling to train regulation—a new train operation model

A new train operation model proposed here not only considers the flexibility of train regulation, or train rescheduling problem, but also the objectives of timetabling process. A genetic algorithm is applied to solve this problem efficiently. Thus no matter the problem is planning the timetable of trains, the unusual passenger flow occurrence or the incident caused delay, our model will make the train regulation as the same as the timetable construction. This will simplify the work of administration. Our model also shows that once the delay occurred, the waiting time of the passengers will be the cost to delay every train. If the delay is not large enough, the system can have some rooms for removing the influence of the delay through our model.     

Modelling disruptions and resolving conflicts optimally in a railway schedule

Resolving disruptions, by dispatching and rescheduling conflicting trains is an NP-complete problem. Earlier literature classify railway operations as: (i) tactical scheduling, (ii) operational scheduling, and (iii) rescheduling. We distinguish the three based on operational criticality. Existing optimisation models do not distinguish precisely between scheduling and rescheduling based on constraints modelling; the only difference is in their objective function. Our model is the first of its kind to incorporate disruptions in an MILP model and to include conflicts-resolving constraints in the model itself. The major advantage of such a formulation is that only those trains which are disrupted are rescheduled and other non-conflicting trains retain their original schedules. Our model reschedules disrupted train movements on both directions of a single track layout with an objective to minimise total delay of all trains at their destinations. Using a small sized data it is proved that all possible conflicts out of a disruption are resolved. Apart from achieving optimal resolutions, we infer through experimental verification that a non-standard dispatch ordering is a requisite for global optimality, as cogitated by other authors.     

基于策略梯度强化学习的高铁列车动态调度方法

高速铁路以其运输能力大、速度快、全天候等优势,取得了飞速蓬勃的发展.而恶劣天气等突发事件会导致列车延误晚点,更甚者延误会沿着路网不断传播扩散,其带来的多米诺效应将造成大面积列车无法按计划运行图运行.目前依靠人工经验的动态调度方式难以满足快速优化调整的实际要求.因此,针对突发事件造成高铁列车延误晚点的动态调度问题,设定所有列车在各站到发时间晚点总和最小为优化目标,构建高铁列车可运行情况下的混合整数非线性规划模型,提出基于策略梯度强化学习的高铁列车动态调度方法,包括交互环境建立、智能体状态及动作集合定义、策略网络结构及动作选择方法和回报函数建立,并结合具体问题对策略梯度强化学习(REINFORCE)算法进行误差放大和阈值设定两种改进.最后对算法收敛性及算法改进后的性能提升进行仿真研究,并与Q-learning算法进行比较,结果表明所提出的方法可以有效地对高铁列车进行动态调度,将突发事件带来的延误影响降至最小,从而提高列车的运行效率.     

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.     

基于STeC的高速列车运行模型与算法

为了使高速列车正点运行到达目的车站,提出了基于STeC(时空一致性)语言的高速列车运行模型与算法。该模型具有位置触发自动调整高速列车运行的特点,实现动态确定高速列车制动点并保证列车正点到达目的车站,从而满足了高速列车运行实时系统对时间和空间的一致性要求。通过Matlab/Simulink的仿真测试,证明了该模型的正确性和有效性。     

Genetic algorithms for match-up rescheduling of the flexible manufacturing systems

Scheduling plays a vital role in ensuring the effectiveness of the production control of a flexible manufacturing system (FMS). The scheduling problem in FMS is considered to be dynamic in its nature as new orders may arrive every day. The new orders need to be integrated with the existing production schedule immediately without disturbing the performance and the stability of existing schedule. Most FMS scheduling methods reported in the literature address the static FMS scheduling problems. In this paper, rescheduling methods based on genetic algorithms are described to address arrivals of new orders. This study proposes genetic algorithms for match-up rescheduling with non-reshuffle and reshuffle strategies which accommodate new orders by manipulating the available idle times on machines and by resequencing operations, respectively. The basic idea of the match-up approach is to modify only a part of the initial schedule and to develop genetic algorithms (GAs) to generate a solution within the rescheduling horizon in such a way that both the stability and performance of the shop floor are kept. The proposed non-reshuffle and reshuffle strategies have been evaluated and the results have been compared with the total-rescheduling method.     

基于IEEE1588标准的列车时间同步技术的研究

随着实时以太网技术的飞速发展,中国铁路速度的不断提高,铁路时间同步网需要为其各个系统提供准确的时间信息,才能保障列车的行车安全,因此对于时间的统一非常重要.以铁路同步网为背景,通过介绍IEEE1588协议中的IEEE 802.1 AS协议,对列车的各个系统之间如何进行精确时间同步进行研究.提出了时钟同步模型和延时测量机...