A review of passenger-oriented railway rescheduling approaches

<jats:title>Abstract</jats:title><jats:p>Railway operations are highly susceptible to delays and disruptions caused by various factors, such as technical issues, operational inefficiencies, and unforeseen events. To counter these delays and ensure efficient railway operations during real-time management, several rescheduling approaches can be implemented. Among these approaches, passenger-oriented rescheduling considers train rescheduling while taking passenger data into account, as opposed to operation-oriented rescheduling. This paper provides an overview of the former group of approaches. Particular focus is put on different ways passenger data is exploited to optimize rescheduling and on the measures, the approaches can decide on. The rescheduling measures typically considered vary from decisions on maintaining transfers, canceling trains, adding emergency trains, changing routes and orders of trains, skipping or adding stops at stations, short-turning trains, applying speed control, and modifying rolling stock compositions. In this regard, the paper presents a comprehensive analysis of real-time rescheduling approaches adopted in both the conventional railway and urban rail transit and points out possible directions for further research in the field.</jats:p>

section_content: Railway transportation has long been recognized as a highly efficient and sustainable mode of transport, offering a wide range of unique advantages over other modes. In particular, railways are known for their superior safety record, good organization, exceptional dependability, and capacity to move large quantities of passengers and goods. Despite these numerous benefits, however, the smooth operation of railways can be hampered by a multitude of unexpected internal and external factors, resulting in significant delays that can propagate throughout the system and ultimately lead to congestion and even the cancelation of some trains. Such disturbances can significantly compromise the competitiveness of railways with respect to other modes. 

When unexpected events occur within the railway system, dispatchers are in charge of the critical responsibility of making rescheduling decisions that will either restore the original timetable or implement a new timetable to mitigate the impact of disturbances. These decisions may apply several measures like rerouting, retiming, reordering, adding or skipping stops, neglecting transfer connections, or canceling trains. Mostly, dispatchers make such decisions according to their intuition and experience. However, given the complexity of the system, these decisions may be inefficient and unable to properly mitigate delays. Therefore, it is necessary to deploy appropriate optimization approaches to support dispatchers. These approaches may account for various levels of detail and realism of the system, and must be designed to run in a computational time compatible with real-time applications. 

In the existing literature, many optimization approaches have been developed for railway rescheduling, and several studies have analyzed the current state of the art in this area. Notably, Törnquist [1] presents an overview of tactical, operational, and rescheduling approaches published between 1973 and 2005. The author classifies the papers based on problem types, solution techniques, and types of evaluation. Similarly, Cacchiani et al. [2] provide a comprehensive review of rescheduling algorithms and models, categorizing them based on the magnitude of the unexpected events they are intended to cope with. The paper delves into the specifics of timetable, rolling stock, and crew rescheduling. Moreover, Fang et al. [3] conduct a detailed study of rescheduling papers, classifying them with respect to modeling choices, solution approaches, and problem types. Meanwhile, Qu et al. [4] provide an overview of the literature on passenger and freight train rescheduling, focusing on the level of detail considered for the infrastructure. Josyula & Törnquist Krasemann [5] conduct a review of passenger-oriented railway traffic rescheduling strategies that utilize dynamic passenger flow data. Lastly, König [6] concentrates on delay management and the decisionmaking process concerning whether trains should wait to ensure connections or not in case of disturbances. 

In this paper, we propose a novel and comprehensive literature review on rescheduling approaches that take into account passengers, in both conventional and urban rail transit. The emphasis is on similarities and differences between the existing approaches as per their positioning under different perspectives: rescheduling measures, types and strategies of passenger information, modeling choices, nature of capacity, and other constraints imposed. Moreover, we specify and discuss various other criteria that differentiate the analyzed approaches. To the best of our knowledge, this is a novel contribution, as a thorough overview of how passenger data have been incorporated in rescheduling is still missing despite the growing attention passengers are receiving in the latest years. Previous studies have tended to focus on specific passenger data (Josyula & Törnquist Krasemann, [5] ) or a specific rescheduling problem (König, [6] ). Here, we set the scope of the analysis to cover all aspects of passenger demand as they appear in the literature (static information, dynamic data, preferences, complaints, etc. ) and on how they are articulated with the used solution techniques, infrastructure considerations, and rescheduling measures. At the end of this analysis, we identify promising areas for future research in this field. 

The rest of the paper is structured as follows: Sect. 2 focuses on the methodology we use to collect papers for this review paper. Section 3 describes the classification criteria that we propose for both the conventional railway and urban rail transit. Section 4 focuses on the actual literature review on the conventional railway and Sect. 5 on urban rail transit. Section 6 discusses research gaps and further research directions, and Sect. 7 concludes the paper.
section_name: Introduction

section_content: We apply a systematic review approach to overview the state of the art in real-time traffic management explicitly considering passengers. Figure 1 shows the design of the research protocol we follow to identify the papers we analyze in this review. 

We consider all papers resulting from the search of two groups of keywords in various databases: ScienceDirect and Scopus, as well as Google Scholar. The search is not time-limited. "Railway rescheduling" and "Real-time traffic management" are the keywords of the first group. "Passenger perspective" and "Passenger viewpoints" are the keywords of the second group. The boolean operator "OR" is used in the search to combine the two keywords from each group. The Boolean operator "AND" is used to combine the two groups of keywords. This gives four different combinations for the search. We find 138 results in total (ScienceDirect-29 results; Scopus-12 results; Google Scholar-97 results). We exclude the papers found to be duplicates across the different databases. We use multiple databases to compare findings and provide a comprehensive overview of the subject. Once the papers are collected, we study their title and abstract for relevance. In particular, we exclude the papers that do not mention passengers specifically: we consider only articles that propose or analyze algorithms for optimizing traffic while taking into account the passenger perspective in either the objective function or in the problem constraints. We account for both the conventional railway and urban rail transit. Finally, we add to the analysis relevant papers from the references of the ones collected so far. 

The paper provides a clear and concise summary of the 26 so identified papers dealing with rescheduling for conventional railway and the 11 papers addressing urban rail transit with passenger considerations.
section_name: Methodology

section_content: The papers we study are different from several perspectives. To organize the analysis, we identify a variety of criteria that differentiate them, including the types of rescheduling measures implemented, the specific passenger details considered, and the objective functions optimized. In this Section, we present the list of these criteria, which we will use in the following to point out commonalities and differences among the studies. Specifically, we indicate several categories which are used with respect to each criterion.
section_name: Classification criteria for rescheduling approaches

section_content: There are several rescheduling measures adopted in case of unexpected events that disturb the normal operations of trains. ) is the elimination of some designated stops for a train. Short-turning (ST) involves reducing a train service by changing its terminus to an earlier station along its route and starting a new service from there. Rolling Stock Rescheduling (RSR) consists in changing the train units used to perform the timetable, with respect to the ones originally planned. Finally, during the rescheduling process, it may be pertinent to alter the train speed profiles, which is known as Speed Control (SC).
section_name: Rescheduling measures

section_content: The rescheduling models in railway systems are subject to a multitude of capacity constraints that require careful consideration. However, the varying degrees of precision with which these constraints can be taken into account may pose computational challenges. This results in certain constraints being overlooked in many rescheduling models. In this paper, we identify four distinct categories of capacity constraints that are commonly encountered in railway systems. The first is Track Capacity (TC), which refers to the maximum number of vehicles that can travel along a given route within a specified time period. This is typically modeled as the minimum headway constraint which is the minimum time separation required between two trains passing a location.
section_name: Capacity constraints

section_content: The models may involve various levels of Passenger details. In this classification, we define three categories: a model is designated as static (S) if passenger data do not change during the rescheduling process. A model is designated as dynamic (D) if the passenger count is calculated dynamically. Other (O) models account for additional layers of passenger information, such as passenger complaints, time spent going from one platform to another in any station, and information other than the number of passengers.
section_name: Passenger details

section_content: The objectives in several rescheduling approaches considered in this review are generally in the interest of passengers. Several approaches explore multi-objective functions that include both passenger and operation interests. In some cases, the passenger and operational perspectives are combined into a single goal, with different weights assigned to each of them. However, determining the appropriate value of weights can be challenging. Several passenger-oriented objectives like minimizing total passenger delay, passenger inconvenience, passenger cost, and total passenger travel time in the system in combination with operation-oriented objectives are considered in this review.
section_name: Objective function

section_content: As real-world railway networks are complex, rescheduling models entail several constraints and variables, and solving them takes a long time. The solution space generally grows exponentially when increasing the scale of rescheduling problems. Several solution approaches consider a balance between computation time and solution accuracy. We define three categories of solution approaches. Exact methods are used for less complicated networks meanwhile heuristics and meta-heuristics are applied for large-scale models to find rescheduling solutions in real-time. An exact method (E) will always find the optimal solution to the problem as long as the computation time is not limited. Problem-specific Heuristics (H) and metaheuristics (M), do not guarantee optimality but aim to return near-optimal results often quicker than exact methods. Problem-specific Heuristics (H) are methods defined specifically for a given problem. Metaheuristics (M) are problem-independent algorithmic principles that can be converted into methods for tackling specific problems.
section_name: Solution approach

section_content: The infrastructure representation considered defines the scope of the approaches. Microscopic models (MI) represent the railway infrastructure with more details, such as tracks divided into block sections separated by signals and including switches. Such models generally consider blocking time graphs with details about the specific allocation time of block sections and track detection sections for the trains. Macroscopic models (MA) do not take into account the fine details of railway networks, such as signals, block sections, and track detection sections, instead opting for an aggregated view of the infrastructure with stations represented by nodes of a graph and tracks by arcs. Some approaches consider both microscopic and macroscopic representations for different sections of the infrastructure.
section_name: Infrastructure scope

section_content: A further criterion for classification is the type of disturbance for which approaches are designed. There are two main types of disturbances considered for railway system rescheduling problems: perturbations and disruptions. Perturbation (P) is a term used to describe relatively smaller delays from which it is simpler to return to the original schedule. When the train takes longer than the specified time for events such as dwell time in any station, running time between two stations, and transfer time between two trains in the same station, it is considered a perturbation. Perturbations can propagate if not properly handled and cause further delays in the system. Disruption (D) refers to exceptionally long delays, train breakdowns, major infrastructure failures, or line interruptions. With disruptions, the original timetable cannot be easily recovered and some major modifications must be decided.
section_name: Type of disturbance

section_content: Rescheduling approaches for conventional railway services are discussed in this section. Trains that travel large distances and often connect cities make up the conventional railway system. The trains run on laid-on tracks which are generally shared by trains offering various types of services (e. g., conventional or high speed) and carrying either passengers or freight. Trains have fixed arrival and departure times at stations and can overtake other trains by using sidings. While considering all classification criteria presented in Sect. 3, we first group approaches according to their infrastructure scope. We discuss macroscopic approaches first, then pass to microscopic ones. In Table 2 we show the number of these approaches in which each criterion and category is considered. In the Appendix, Table 3 contains the details regarding all criteria for the approaches discussed in this section. 

Most of the papers cited in this section are related to delay management and the reduction of passenger inconvenience in the case of disturbances.
section_name: Conventional railway rescheduling

section_content: The papers in this section consider macroscopic representation for different sections of the infrastructure. We further split papers on macroscopic rescheduling on the basis type of disturbances handled.
section_name: Macroscopic approaches

section_content: There are a number of papers that propose macroscopic rescheduling models dealing with perturbations and focusing on passengers. 

As a first contribution, Schöbel [7] defines the novel problem of delay management. It is relevant when passenger transfers are planned, and it decides whether connecting vehicles should wait for feeder ones in case of perturbation. If the connecting train waits, the delay propagates through the network. To the best of our knowledge, this is the first paper in which the problem of delay management is discussed. The author presents a MIP model that minimizes the sum of all delays of passengers when they reach their destination. Passenger origin-destination (OD) data are considered as weights in the objective function. The model is based on an event-activity network with nodes representing all train arrival and departure events at stations. Edges connect nodes and have weights corresponding to slack times that represent dwell time at stations, train driving time between stations, and train connection time between two trains at any station to facilitate passenger transfer. The purpose of the approach is to determine the best paths for multiple ODs on this graph, so as to identify which connection arc should be maintained in the event of a perturbation in order to reduce total passenger delays. 

Solving the complete model introduced by Schöbel [7] takes a lot of computational effort. To try to decrease it, Heilporn et al. [8] propose two equivalent MIP models for variable reduction for the problem in Schöbel [7]. The two models are designed by neglecting departure events. Equivalence between those proposed two models and one derived by Schöbel [7] is presented. They differ in the number of variables, constraints, and set of paths. They are solved by a branch and cut procedure and by a constraint generation approach respectively. They consider passenger OD data as in Schöbel [7] and solve the problem with faster computation time, especially for the MIP model solved using the constraint generation approach. 

In their paper, Schachtebeck and Schöbel [9] present an Integer Programming (IP) formulation for the capacitated delay management problem. They consider the use of disjunctive constraints to make priority decisions, with the goal of reducing the delay across all trains and the number of missed connections. The authors propose a reduction technique that facilitates the extension of the never-meet property from an uncapacitated delay management problem to a capacitated one. To solve the problem, exact and heuristic approaches such as First Scheduled, First-Served (FSFS), First Rescheduled, First-Served (FRFS), FRFS with Early Connection Fixing (EARLYFIX), and a combination of FSFS and FRFS are developed. The efficacy of these approaches is evaluated both theoretically and on realworld data provided by a German railway company. 

The approaches described up to now, do not take track capacities into consideration. Schöbel [10] incorporates constraints to take this capacity into account in the delay management problem. The author includes capacity constraints in the macroscopic model considering only edges between stations and minimum separation time between departures of two trains. The paper uses heuristics like firstrescheduled-first-served (FRFS) and branch-and-bound with optimal scheduling decision (B and B-OS) to calculate the solution. The approaches are applied and compared to a real-world example provided by Deutsche Bahn. Dollevoet et al. [11] extend the delay management problem with the possibility of rerouting passengers. In the previously discussed approaches, if passengers missed a connection, they would have to wait for the next train operating the same service as the missed one, which is rarely the case in practice. Dollevoet et al. [11]. assume that passengers are informed of upcoming train and choose the shortest route to get to their destination. The proposed approach is based on an event-activity network as the previous ones, with additional events to include the origin and destination of passengers. For modeling the routing decisions, binary decision variables that indicate if any connection is utilized by passengers in OD pair are introduced. The approach is tested on part of the Dutch railway network with promising results. Dollevoet and Huisman [12] is a follow-up paper to Dollevoet et al. [11]. It introduces heuristics to solve large instances of the delay management problem with passenger rerouting. With weights specified by the average number of passengers per OD pair, the weighted total of delays is minimized. The first set of heuristics uses dispatching rules like the fixed maximum waiting time rule or the ratio of transferring passengers that are commonly used by dispatchers nowadays. The second set of heuristics solves the traditional delay management model without passenger rerouting, whereas the third set of heuristics iteratively updates the parameters of the traditional model to incorporate passenger rerouting until convergence, or until the maximum number of iterations is reached. The performance of these heuristics is examined using six real-world case studies of various sizes from the Dutch railway, with satisfactory results using the no-wait policy as a benchmark for comparison. Dollevoet et al. [13] include station capacities in the delay management problem. Small instances of this problem can be solved exactly, but bigger ones require the use of heuristics. According to the paper, platform track adjustments for trains help lessen passenger inconvenience during disruptions. The priorities of trains are initially calculated keeping platform track assignments fixed. Then, Platform track assignments in each station are modified iteratively. The approach is tested on a Dutch railway network. The results show that platform reassignment minimizes passenger delays. 

Kanai et al. [14] present a model to find a delay management plan minimizing a passenger disutility function. This function includes the total time passengers spend on board, waiting time, number of transfers, and train congestion rate. The authors propose an approach to combine simulation and optimization. They develop a simulation framework that includes passenger flow and train traffic simulators, working in parallel. A tabu search approach is used for optimizing the delay management plan. The paper assumes static OD passenger data. It also assumes that passengers always decide their routes to minimize the disutility function defined. The approach is implemented and tested on a high-frequency Japanese rail network with satisfactory results. 

In summary, the delay management problem has been studied by considering several infrastructure constraints and solution approaches. For all the above-mentioned literature, the passenger OD demand is taken into account for defining weights in the objective functions. 

Other literature aims to lessen passenger inconvenience in case of perturbation. Many criteria are used to define what constitutes passenger inconvenience. Norio et al. [15] investigate rescheduling with passenger-related objective function but without employing passenger data sources. Instead, the paper analyzes the situation where the passenger would complain and collect them in a chain file. With minimization of passenger dissatisfaction as the objective function, the model is solved with Project Evaluation and Review Technique (PERT) and Simulated Annealing (SA) approaches. They are applied to a case study from the Japanese railway network. 

Tanaka et al. [16] consider passenger inconvenience defined by three factors: traveling time, transfer burden, and congestion. The model uses shortest-path algorithms and a disaggregate demand model to calculate the number of passengers selecting paths during rescheduling. The approach considers retiming and reordering of trains during rescheduling and considers trains with limited capacity.
section_name: Perturbations

section_content: Zhu & Goverde [17] propose a MIP model for rescheduling during complete track blockage with a plethora of possible measures: retiming, reordering, flexible stopping adding and skipping stations, train canceling, and flexible short turning. To reduce passenger delay, the authors introduce flexible short turning and stopping for the first time for rescheduling. The model is tested on a sub-network of the Dutch railways and the results show that flexible shortturning is advantageous in a network with high frequency. 

Zhu and Goverde [18], the same authors propose a novel model that integrates timetable rescheduling and passenger reassignment which assigns passenger groups to a particular path based on the weight of the path. The authors formulate a model that minimizes generalized travel time, which includes time spent in the vehicle or waiting at stops and number of transfers. Passengers are assigned to trains after the application of several rescheduling measures, including retiming, reordering, canceling, adding stops, and a skip-stop strategy. Iteratively, the model is solved using the fix-and-optimize technique with a restricted passenger group. An optimal operation-oriented rescheduling model for a Dutch railway network with the goal of minimizing train cancelation and arrival delays is considered a benchmark. In experiments based on a part of the Dutch network, the proposed approach reduces passenger generalized travel time by thousands of minutes, while adding about ten minutes to the total train arrival delays. 

Binder et al. [20] develop a multi-objective rescheduling approach. The objectives are the minimization of passenger dissatisfaction, along with the minimization of operation costs and deviation from the original timetable. An epsilon-constraint method is used, setting passenger dissatisfaction as an objective function and the other two objectives as constraints. Passengers might adjust their destination, their desired departure time, or even their chosen travel mode in a disrupted situation. The paper included dynamic passenger demand following the announcement of the disruption. The approach is tested on a portion of the Dutch railway network and solved with a commercial solver. 

Binder et al. [21] consider a passenger choice model in which passengers choose their route and compete for limited resources. The model considers a single disruption that blocks tracks between stations completely. The authors assume that the duration of the disruption is known at its beginning, and will not change over time. The paper uses three objective functions: operating costs, deviation from the original timetable, and passenger convenience. The approach considers OD passenger data, as well as passenger awareness of the timetable and selection of the most convenient option. It creates an approximation Pareto frontier and is successfully tested on the Swiss and Dutch railway networks. 

Hong et al. [21] focus on adding extra stops to noncanceled trains for serving disrupted passengers. The train rescheduling and passenger reassignment problems are integrated taking into consideration the limited seat capacity of the trains. A new timetable is determined using a MIP model, where the objective is to minimize the weighted delay of non-canceled trains and maximize the number of disrupted passengers reaching their final destination. The disrupted passengers are represented by passenger groups with the same destination. The model is implemented on part of the Beijing-Shanghai high-speed railway line. The efficiency and efficacy of the approach by obtaining Pareto optimal solutions using the weighted sum method. 

All approaches discussed so far take train unit compositions as fixed. The next three papers, instead, also deal with Rolling Stock Rescheduling. 

First in this group, Kroon et al. [22] consider rescheduling under dynamic passenger flow with aim of minimizing passenger delay. The approach proposes a simulation model for passenger flows, based on their traveling strategies and capacities allocated to the train. It also considers iterative heuristics to solve rolling stock rescheduling with dynamic passenger flow. The author presents a two-step simulation approach in which passenger traffic is first simulated and then the results are fed into a rolling stock rescheduling model. The simulation is done again to see if the optimized rescheduling model fits better with the passenger flow. The model is tested on a number of instances of Dutch railways. 

Veelenturf et al. [23] aim for rescheduling by changing rolling stock composition in response to changes in passenger demand. The approach uses a passenger simulation model introduced by Kroon et al. [22] to determine dynamic passenger flow during disruption. The approach develops an IP model based on [24] to minimize rolling stock rescheduling costs, passenger rescheduling costs, and passenger service costs by combining rolling stock rescheduling and adding extra stops. The approach is tested on the Dutch railway network with satisfactory results. 

Finally, Hoogervorst et al. [25] introduce the Passenger Delay Reduction Problem (PDRP) to minimize passenger delays using rolling stock rescheduling. It minimizes the delay of passengers considering comfort and operational efficiency. The paper uses changes in train composition through shunting movements at stations and turn-around. It considers a large number of mutually conflicting objectives with predetermined weights. Two approaches are proposed: a delay composition and a delay path model. These are tested in a part of the Dutch network. Delay composition is found to perform best in finding a high-quality solution in a limited time. 

We discuss the summary of the approaches for rescheduling conventional railways with passenger consideration in Table 1.
section_name: Disruptions

section_content: As with macroscopic approaches in Sect. 3. 1, we group the papers representing infrastructure microscopically on the basis of the type of disturbances handled.
section_name: Microscopic approaches

section_content: All the papers presented in this section consider delay management and microscopic train rescheduling in case of perturbation. Rescheduling measures allowed include retiming, reordering, speed control, and cancelation of trains. 

First, Corman et al. [26] develop a bi-objective delay management strategy that aims to minimize weighted passenger delays and the number of missed connections. The paper uses two heuristics algorithms based on alternative graphs to calculate an approximated Pareto front of non-dominated schedules. It iteratively reschedules trains with fixed connections and chooses connections to be enforced. The approach is tested on part of the Dutch railway network with five stations. Espinosa-Aranda and García-Ródenas [27] consider the minimization of total passenger delay at the destination. The paper introduces the Avoid Most Delayed Alternative Arc (AMDAA) approach to solve the problem. This approach is an extension of the Avoid Maximum Current Cmas Branch-and-Cut. AMDAA, AMCC, and FCFS approaches are used to solve the model and the results are tested for the Renfe Cercanias Madrid railway, considering four stations. The results demonstrate that exact approaches are practical for solving medium-sized problems in real-time, whereas heuristics can provide near-optimal outcomes for large problems at a lower computational cost. Also, for randomly generated passenger OD data, the AMDAA approach considerably reduces passenger delay, sometimes at the expense of the total makespan. Dollevoet et al. [28] consider the weighted sum of passenger arrival time at the final destination as an objective function in the delay management problem. The delay management model calculates which connection to maintain and which to drop, whereas microscopic train scheduling validates the departure and arrival times and respects the detailed information about the tracks and switches within the stations. The approach applies the two algorithms iteratively. It is tested on the Dutch railway network with 46 stations including Utrecht Central Station, which is considered microscopically in the train scheduling problem. The rest of the network is represented macroscopically. Two sets of instances are generated for testing: one with small initial delays and the other with large ones. The proposed approach is found to be efficient for small initial delays but less so for large delays. 

As a follow-up to Corman et al. [26], [29] consider the same problem and develops an algorithm for the fast calculation of upper and lower bounds. Passenger OD data in terms of average volume of passengers at the station is considered for delay management. The problem is decomposed into train rescheduling and passenger routing problems, and three heuristics are proposed. The instance is studied on the Dutch railway network. Two sets of instances are considered: one is small, with eleven stations, and the other is much larger, encompassing a considerable portion of the Dutch railway network, but no details are supplied in the paper. The problems are solved to optimality for small-size instances whereas four heuristics are developed to solve large-size instances in a short time. 

Sato et al. [30] propose a model to minimize the inconvenience defined by the sum of onboard traveling time, waiting time at platforms, and the number of transfers. The paper shows that passenger and operation-oriented objectives are often in conflict, as decreasing passenger inconvenience comes at the expense of additional train delays. The research considers two objectives: minimizing train arrival delays and passenger inconvenience. The first phase determines the amount of inconvenience to passengers in the planned timetable. A second phase aims to reduce train arrival delays after a perturbation occurs, and a final phase tries to reduce the positive difference in inconvenience between the planned and revised timetables. The approach is tested in a case study representing a part of the Japanese railway network. 

Finally, Toletti and Weidmann [31] present a train rescheduling approach for mixed traffic (both passengers and freights) that minimizes passenger discomfort. It establishes three alternative objective functions to minimize: train delay, passenger delay, and passenger inconvenience. As Sato et al. [30], it perceives station waiting time to be twice as inconvenient as time on board. The approach implements a Resource Conflict Graph and exploits a commercial IP solver. Computational experiments are run on a part of the Swiss rail network with two large and four small stations. The results demonstrate that only minimizing train delays has an extraordinarily large negative impact on passenger delay. Thus, the authors suggest that for any rescheduling approach, it is better to include passengers.
section_name: Perturbations

section_content: Only two papers propose microscopic rescheduling approaches dealing with disruptions and focusing on passengers. They have both been published extremely recently. 

Shakibayifer et al. [32] aim to reduce weighted train delays and deviations from the original timetable, with weights that are proportional to passenger demand at each station. A MIP formulation models the railway infrastructure imposing limited station capacity. To solve the problem, an exact approach and two heuristics, namely right-shift rescheduling and two-stage rescheduling, are provided. They are tested on the Iranian railway network with 53 stations, with several disruptions considered in bottleneck areas. Only one train at a time is allowed to use a track between two stations. The exact approach is shown to be useful only when track blockage duration is short: it is unable to find a realistic solution in a fair amount of time as this duration increases. 

Zhan et al. [33] take into account the limited seat capacity for trains. The authors consider train routing in a station area at a microscopic level. The approach is based on the Disrupted Trains Waiting Strategy (DTWS): trains are stopped ahead of the blockage until the track is cleared; then they are allowed to continue their journey. A passenger routing problem and a train rescheduling problem are integrated into a set of shortest-path problems. The paper aims to reschedule the affected passengers such that operational costs for the railway companies and travel costs for the passengers are minimized. The cost of each available passenger route depends on travel time, waiting time, number of transfers, and late departure of trains. Passengers are assumed to select the route with the lowest cost. The problem is solved with a dynamic programming approach and tested on a part of the Chinese railway network with 17 stations, with satisfactory results. 

In Table 1, we present the overview of the literature discussed for rescheduling the conventional railway.
section_name: Disruptions

section_content: The nature of urban rail transit systems presents unique challenges that set them apart from conventional railway systems Urban rail transit is comprised of highcapacity, high-frequency, homogeneous lines that run on independent tracks and are not amenable to reordering or rerouting. Typically, these systems are tailored to the needs of metropolitan centers and their suburbs, covering shorter distances and having stations in closer proximity than conventional trains (Li et al. [34] ). As passenger flows in urban transit systems exhibit a high degree of uncertainty and follow complex dynamics, probabilistic approaches are often employed to model them. Moreover, due to the extremely short intervals between trains during rush hour, even minor delays can rapidly propagate throughout the system. 

A fundamental difference between rescheduling in conventional railways and urban rail transit lies in the considerations made for passengers. In conventional railway systems, rescheduling typically relies on static data where the number of passengers traveling on each origin-destination is known to the dispatcher. In contrast, in urban rail transit, rescheduling primarily relies on dynamic data where the origin-destination plans of passengers are not static. Here, passenger flow distribution models are commonly employed to approximate passenger flow in the network. Automatic fare collection data is often leveraged to calculate passenger flow dynamics in a large spatiotemporal space. Moreover, some models take into account passenger behavior change and network factors beyond just passenger flow, providing a more comprehensive picture of the system. Dynamic data can approximate passenger behavior in case of delay whereas static data cannot. Another drawback of static data is that it doesn't incorporate changes in the number of passengers in real-time, although passengers may accumulate in stations in case of delays. The models used for dynamic data collection are approximation ones. This section presents an in-depth review of the literature on rescheduling approaches in urban rail transit, which often model passenger behavior and minimize passenger inconvenience during disturbances. Interestingly, none of the eleven publications examined in this review discusses train reordering, rerouting, or adding stops as potential rescheduling measures. Instead, retiming, skip-stop, and speed control are the most commonly used rescheduling measures. It is noteworthy that station capacity is restricted to accommodate only one train at a time. Moreover, the reviewed papers assume that only one train can operate between two stations at any given time. As no track details are present, all papers are classified as macroscopic in this review. Nonetheless, we classify the papers according to all Sect. 3 criteria in the appendix, as done for conventional railways: Table 2 indicates the number of papers in which each criterion and category is considered, and Table 4 reports the details for each paper. 

Almodovar and Garcia-Rodenas [35] propose an online optimization approach based on a discrete event simulation model for rescheduling trains. It tries to minimize the total time passengers spend in the system. The disruption here is caused by unexpectedly high demand that exceeds service capacity. The authors discuss ways of rescheduling rolling stocks from other lines to the disturbed ones to meet excess demand. A discrete event simulation model uses the demand and service model to represent passenger flow dynamically. The optimization model is solved with two greedy heuristics to get nearoptimal solutions. The simulation model used in the paper properly depicts the dynamic features of passenger flow and the response of the passengers to disturbances. This work demonstrates that when using an on-line optimization strategy in conjunction with a simulation model to estimate the objective function, a trade-off between accuracy and response speed must be found, as emerges in the experiments run on the Madrid regional train network. 

Studying urban transit, Zhen and Jing [36] propose a rescheduling model that takes passenger behavior into account. The paper assumes that, under a rescheduled timetable, passengers may wait for the next train, choose a different route or cancel their planned trip altogether. The approach proposed attempts to reduce the negative impact of railway delays on passengers, which is measured by total travel time and cost for canceling a planned trip. The formulated train rescheduling problem is nonconvex and tackled with a genetic algorithm. It manages to significantly reduce travel time and planned trip cancelations on Beijing subway instances. 

Another paper that makes use of a genetic algorithm is the one by Xu et al. [37]. It presents a passenger-oriented rescheduling algorithm to minimize generalized travel time: delay time of alighting passengers and penalty time of stranded passengers. The authors use a genetic algorithm with adaptive mutation rate and elite strategy to deal with the rescheduling problem. The approach is tested in Beijing metro line 13 with a 9. 47% reduction of average generalized delay time in comparison to trainoriented models. 

Considering a very different approach, Yin et al. [38] present a stochastic programming model for urban rail transit rescheduling problems with dynamic passenger flow. It aims to minimize passenger delay, total travel time, and total energy consumption. The model uses a non-homogeneous probability distribution for passenger arrivals at the station, with an intensity function based on a time-varying OD passenger demand matrix. To deal with the proposed model's complexity and uncertainty, and swiftly discover a reasonably practicable solution, approximate dynamic programming (ADP) is used. 

Here the problem is decomposed into a multistage stochastic decision process. Each stage concerns the movement of a train from one station to another. The train is rescheduled at each stage based on predicted costs, and the system is updated with new data on running time, dwell time, and number of people alighting, waiting, and boarding. The ADP effectiveness and robustness are tested using a small simulated metro line and real-world data from the Beijing metro Yizhuang line. 

Hao et al. [39] present a rescheduling approach based on a Markov decision process. It examines the interactive link between train operation and passenger behavior and reschedules trains considering dynamic passenger flow. The number of waiting passengers who are unable to board the train because of capacity and time constraints is the number of controlled passengers. This number and the train running time between two stations are two decision variables. The solution process is divided into numbers of multiple decision-making stages. The paper aims to minimize the weighted combination of total passenger delay calculated by waiting delay at stations, passenger control penalty, and train regulation penalty. Like Yin et al. [38], the authors use ADP. In this proposal, the ADP approximates the value function using state features to increase computational efficiency, to deal with largescale problems. 

Li et al. [34] develop a coupled dynamic model for both passenger flow regulation and train rescheduling. The dynamic model considers an accurate picture of the train rescheduling problem. Rather than using a time-dependent OD matrix to describe passenger demand, as most papers do, this work accounts for a dynamic evolution of passenger demand based on train headway. The number of alighting passengers at stops is also considered to be proportional to the number of passengers in trains. The model aims to minimize the cost function which is a weighted function of timetable deviation, headway regularity, and train control actions. It is solved with a model predictive control (MPC) approach. This approach is shown to be exploitable in actual metro lines in realtime. Moreover, it is found to be effective in reducing train delays, passenger load errors, and train headway deviations. 

Hou et al. [40] propose a MIP approach for train rescheduling. It takes into account the onboard Automatic Train Operation (ATO) system's preprogrammed speed profiles. To minimize total train delay, total number of stranded passengers, and total train energy consumption, the authors formulate a multi-objective optimization problem. They use continuous decision variables for arrival and departure timings, as well as binary variables to indicate the preprogrammed speed profile. The model is tested using real-world data, and its efficiency is confirmed. Some papers consider skipping stops during rescheduling. Gao et al. [41] propose an optimization approach to reschedule a metro line under disturbances. It considers over-crowded passenger flows: passengers with different destinations randomly arrive and get mixed in each station. The capacity of trains is presumed to be limited. The authors describe methods for linearizing constraints of the optimization model. Then, they decompose it into a series of MIP problems using heuristics and solve them using an iterative approach. Results obtained with this approach indicate that during interruptions, regardless of arrival rate or OD matrix, a suitable skip-stop pattern outperforms the standard all-stop pattern if the number of stranded passengers is substantial. Twelve distinct conditions are tested, including a heterogeneous/ homogeneous OD matrix, increasing/decreasing arrival rates, and a short/medium/long disturbance period. The approach is tested on Beijing Metro and results are found to ascertain its effectiveness and efficiency. 

Altazin et al. [42] also present a rescheduling approach for urban rail transit with stop skipping. The objective of the paper is the minimization of the waiting time of passengers and the recovery time of the original timetable. An IP approach is proposed. It uses passenger OD data with a fixed number of boarding and alighting passengers at each station. Rolling stock limitations are taken into consideration. The approach does not take train capacity into account. It is tested on a crowded railway system in the Paris area, and it demonstrates that skipping stops is an efficient approach for lowering recovery time. 

Along with Altazin et al. [42], Cadarso et al. [43] also deal with rolling stock rescheduling in event of disturbances. Cadarso et al. [43] present an integrated optimization model to deal with both timetable and rolling stock rescheduling under dynamic demand. In contrast to many of the previous studies, this approach is applied to a metro network rather than a metro line. The authors use two iterative steps to solve the model. In the first step, anticipated passenger demand is calculated using the multinomial logit model. The authors solve a MIP model for both timetabling and rolling stock rescheduling problems in the second step, with objectives related to the operation of trains, rolling stock allocation and cancelation, number of denied passengers, train empty movements, and deviation from the original timetable. Operation strategies like canceling and adding emergency trains are considered, but the possibility of changing departure times for planned service is not considered. The approach is applied to RENFE's regional network in Madrid with satisfactory results. 

Hassannayebi et al. [44] develop a rescheduling model with short-turn and skip-stops to minimize passengers' waiting time. The arrival rate of passengers at stations is defined as a non-stationary Poisson arrival rate. As a decision support system for managing disturbances in urban rail transit lines, the authors present a new integrated simulation-optimization approach, supplemented with a variable neighborhood search algorithm. They show that the variable neighborhood search algorithm can find the optimal solution in a reasonable time for some instances representing large disturbances. The approach is tested on the Tehran metropolitan network with considerable success.
section_name: Urban rail transit rescheduling

section_content: The analysis of the literature reported in the previous sections shows that one of the less explored research areas is one on the microscopic rescheduling approaches, specifically dealing with perturbations. These approaches are extremely well studied when focusing on an operational perspective, but they have been seldom extended to consider passengers. In particular, there is currently no literature that attempts to incorporate rerouting in the case of microscopic rescheduling approaches considering passengers. Currently, rescheduling approaches do not consider the stopping platforms of the trains involved during rescheduling as modifiable. However, exploiting rerouting is known to be an effective measure to limit delay propagation in railway traffic management (D' Ariano et al. [45], Pellegrini et al. [46], Corman et al. [47] ). When considering passengers, new subtleties need to be accounted for. For example, to allow the transfer, it is necessary to consider that passengers have to walk from one train to another in the available connection time, hence the assignment of faraway platforms may become impossible. On the other hand, if trains stop at very close platforms, some delay propagation may be avoided by reducing the minimum connection time. How to efficiently model the additional subtleties associated with rerouting is an open research question. This will require the extension of the existing models or a complete change of approach if the computation becomes too time-consuming. 

The present analysis of the literature reveals a research gap in the inclusion of passenger behavior modeling in delay management for conventional railways. While existing approaches mostly assume demand inelastic to the schedule or use simplistic models to capture passenger reactions, it is crucial to acknowledge that passengers can decide to wait, choose an alternative route, or cancel their trip when facing delays. In this regard, there is a need to incorporate advanced techniques to predict passenger behavior into rescheduling approaches. Although some studies have explored this avenue in urban rail transit, it remains largely unexplored in conventional railways, where the service mix and infrastructure topology pose additional challenges to traffic management. Nonetheless, the integration of passengers into rescheduling approaches will be crucial to address the growing demand for mobility and ensure sustainable railway operations. 

An area that has received very little attention in the discussed literature is the management of mixed traffic, which encompasses both passenger and freight trains. Devising an appropriate objective function that takes into account the distinct objectives of freight and passenger traffic presents a significant challenge. Furthermore, the rescheduling measures that are appropriate for different types of passenger trains may vary considerably, potentially resulting in diverse levels of inconvenience. Addressing the emerging challenges will require a comprehensive understanding of the unique characteristics of each type of traffic and the development of sophisticated algorithms that can account for the complexities associated with mixed traffic management. 

In order to make theoretical and methodological advancements in traffic management, it is imperative to have a comprehensive understanding of passenger habits and preferences. However, the current literature lacks a multi-disciplinary approach that integrates insights from surveys and other related fields to better define and measure passenger inconvenience. While some studies have been conducted in specific cities and for particular types of passenger trips, there is a scarcity of generalization attempts, which are crucial for establishing a comprehensive understanding of passenger inconvenience. Future research should thus focus on developing a more nuanced understanding of passenger inconvenience that incorporates a wide range of factors and is generalizable across different contexts. 

Other factors that will need to be considered in future research are the availability and reliability of the information on passengers. Indeed, too optimistic assumptions may limit the scope of the applicability of the proposed approaches. However, the set of hypotheses made on the knowledge available on passengers when making decisions is always neglected in the discussions. In particular, all the approaches studied for this literature review consider the origin and destination of passengers as known when making decisions. However, apart from trains requiring a reservation, today the system can be aware of passenger destinations only when this destination is actually reached. And even in this case, only a few existing systems actually monitor when passengers leave. In most conventional railway services, no information is available at all, unless the train or station personnel is interviewed. The impact of this lack of information is today completely unknown. At the very least, in our opinion, the research community will need to find a way to assess this impact to show the usefulness of the approaches we propose even when not everything is known in advance. Then, we may propose new approaches, maybe considering robust or stochastic optimization, to see if this impact can be decreased. This type of research may be particularly useful for practitioners, not only to move towards optimized traffic management but also to decide what investment would be most beneficial for improving the quality of service. For example, different benefits will derive from the installation of passenger counters on all trains, on station platforms, or even from the deployment of a system in which passenger has to declare their destination when entering the system.
section_name: Research gap and open issues

section_content: This study offers a comprehensive review of the literature on rescheduling, with a focus on the passenger dimensions, for both conventional railways and urban rail transits. The review encompasses a broad spectrum of rescheduling measures, including but not limited to retiming, reordering, rerouting, adding and skipping stops, canceling trains, adding emergency trains, speed control, short-turning, and rolling stock rescheduling. Our study shows how these measures are employed by different papers for rescheduling. Furthermore, the study evaluates various capacity constraints, rescheduling models, and solution methods that are utilized by the rescheduling approaches described in the literature. We also discuss several ways in which passenger details are accounted for. 

It is evident from the literature review that the majority of papers adopt a macroscopic representation of the railway infrastructure to deal with perturbations and disruptions. However, there are a few notable exceptions that propose the integration of microscopic and macroscopic representations. Furthermore, the literature review highlights the significant attention given to delay management, with passenger demand serving as a crucial factor in the optimization objective function. The papers reviewed in this study also place a significant emphasis on minimizing passenger inconvenience, with several different definitions proposed. Finally, during disruptions, rolling stock rescheduling emerges as a viable and effective rescheduling measure, with several papers exploring this option. 

Our review reveals that while retiming and reordering rescheduling measures are widely considered in all papers on conventional railway rescheduling, the papers on urban rail transit tend to neglect reordering, rerouting, adding stops, and rolling stock rescheduling. Moreover, the majority of studies on conventional railway rescheduling primarily focus on track capacity evaluation at the macroscopic level, i. e., imposing minimum headway times between passing trains. Less than half of the papers take station capacity into account, in terms of number of available platforms. In contrast, all papers on urban rail transit consider both track and station capacity. Furthermore, we found that the consideration of passenger count varies significantly between conventional railway and urban rail transit rescheduling. In conventional railway rescheduling, static passenger count is commonly used. Conversely, urban rail transit studies tend to place more emphasis on dynamic passenger count. Finally, we also observe a disparity in the representation of the railway infrastructure between the conventional railway and urban rail transit studies. The majority of pa pers on conventional railway tend to adopt a macroscopic approach, whereas only about one-third of papers consider a microscopic representation of infrastructure. 

Through our review, we identified several research gaps that need to be addressed in future studies. While the approaches presented in the literature have shown promising results in experiments, deploying them in real-time railway operations remains a significant challenge. This is due to the complex nature of railway operations and the cultural changes that optimization tools require. The explicit consideration of passengers, as demonstrated in the approaches we reviewed, adds a further layer of complexity. In reality, monitoring passenger flows and utilizing them in optimization remains a challenge, although advancements in technology are constantly being made. To overcome these challenges, a clear understanding of available data and how to properly exploit it is necessary. This is a critical milestone that needs to be achieved in order to advance the state of the art in railway traffic management optimization.
section_name: Conclusion and further research

section_name: Acknowledgements

section_content: Rail Concept and Gustave Eiffel University both contributed to this study. We thank our Gustave Eiffel University colleagues for their knowledge and experience, which considerably aided the composition of this review work.
section_name: Acknowledgements

section_name: Funding

section_content: This research received no external funding.
section_name: Funding

section_name: Availability of data and materials

section_content: The data sets used and analyzed during the current study are available from the corresponding author upon reasonable request.
section_name: Availability of data and materials

section_name: Appendix

section_content: Table 2 includes the various criteria considered for each paper, as well as the number of papers for which criterion is used in the rescheduling process. For each paper, Tables 3 and 4 cover the rescheduling approaches as well as the criteria used in conventional railways and urban rail transits (URT), respectively. Problem Specific Heuristics (H) 13 5 Meta heuristics (M) 4 4

Author contributions BS formulated the first draft of the paper along with regular guidance and correspondence with PP. JR and NC reviewed the drafts and provided suggestions and corrections. All authors read and approved the final manuscript.
section_name: Appendix

section_content: Bishal Sharma is a Gustave Eiffel University Ph. D. researcher. He has a master's degree in traffic and transportation engineering from Beijing Jiaotong University, and he is interested in railway timetable optimization, having published a couple of papers on the topic. Bishal is pursuing a doctorate in train rescheduling with passenger dimensions. Linear programming, heuristics and metaheuristics, machine learning, and big data are all topics that he is interested in.
section_name: Author information

section_name: Declarations

section_content: The authors declare that they have no competing interests.
section_name: Competing interests

section_content: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
section_name: Publisher's Note