Abstract
The paper aims to provide an overview of the key factors to consider when performing reliable modelling of rail services. Given our underlying belief that to build a robust simulation environment a rail service cannot be considered an isolated system, also the connected systems, which influence and, in turn, are influenced by such services, must be properly modelled. For this purpose, an extensive overview of the rail simulation and optimisation models proposed in the literature is first provided. Rail simulation models are classified according to the level of detail implemented (microscopic, mesoscopic and macroscopic), the variables involved (deterministic and stochastic) and the processing techniques adopted (synchronous and asynchronous). By contrast, within rail optimisation models, both planning (timetabling) and management (rescheduling) phases are discussed. The main issues concerning the interaction of rail services with travel demand flows and the energy domain are also described. Finally, in an attempt to provide a comprehensive framework an overview of the main metaheuristic resolution techniques used in the planning and management phases is shown.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
1 Introduction
Rail transport benefits from several specific features which make it a key element in public transport management, above all in high-density contexts. Indeed, rail transport is environmentally friendly (low pollutant emissions), high-performing (high travel speeds and low headways) and competitive (low unit costs per seat-km or passenger-km), while presenting a high degree of adaptability to intermodality. However, it is highly vulnerable in the event of breakdowns: a faulty convoy cannot be easily overtaken and sometimes cannot be easily removed from the line, especially in the case of isolated systems (i.e. systems which are not integrated into an effective network) or when a breakdown occurs on open tracks. Thus, re-establishing ordinary operational conditions may require excessive amounts of time and, as a consequence, an inevitable increase in discomfort (user generalised cost) for passengers, who might decide to abandon the system or, if already on board, exclude the railway system from their future choice set. Hence developing appropriate techniques and decision support tools for optimising rail system management, both under ordinary and under disrupted conditions, would clearly affect the modal split in favour of public transport and therefore bring about a considerable reduction in the externalities caused by the use of private transport, such as air and noise pollution, traffic congestion and accidents, conferring clear quality-of-life benefits for both transport users and non-users (i.e. individuals who are not system users).
However, a rail service is generally considered as a stand-alone system, and other systems, which are strictly connected with it by means of reciprocal interactions, are regarded just as constant input variables or, at worst, totally neglected. Therefore, after an overview of the main rail simulation and optimisation models proposed in the literature, the paper focuses on the main issue concerning interactions of rail service with travel demand flows and the energy domain.
First, as rail transport, just like any other transport system, has the task of moving people or goods around, a realistic and accurate cost–benefit analysis cannot ignore the flow features involved. In particular, considering travel demand within the analytical framework presents a two-sided effect. First and foremost, it leads to introducing elements such as convoy capacity constraints and the assessment of dwell times as flow-dependent factors which make the simulation as close as possible to reality. Specifically, the former takes account of the possibility that not all passengers can board the first arriving train, but only part of them, due to overcrowding, with a consequent increase in waiting times. Due consideration of this factor is fundamental because, if it were to be repeated, it would make a further contribution to passenger discontent. By contrast, estimation of dwell times on the basis of flows becomes fundamental in the planning phase. Indeed, estimating dwell times as fixed values, ideally the same for all runs and all stations, can result in deviations between actual and planned operations, with a subsequent deterioration in system performance. Thus, neglecting the above aspects, above all in crowded contexts, would render the simulation distorted, in terms of both costs and benefits. The second aspect, on the other hand, concerns correct assessment of effects of the strategies put in place, both in planning phases (strategic decisions such as the building of a new infrastructure, improvement in the current signalling system or the purchase of new rolling stock) and in operational phases (operational decisions such as the definition of intervention strategies for addressing disruption conditions). Indeed, nowadays in the management of failures, there are operational procedures which are based on hypothetical times for re-establishing ordinary conditions, estimated by the train driver or by the staff at the operation centre who generally tend to minimise the impact exclusively from the company’s point of view (minimisation of operational costs), rather than from the standpoint of passengers. Additionally, in defining intervention strategies, passenger flow and its variation in time (different time intervals) and space (different points in the railway network) are rarely considered. Relying on suitable estimation and forecasting techniques for travel demand, which have to allow for the peculiarities of the railway system as well as be able to properly model the behaviour of passengers in the various phases of the trip (turnstile access, transfer from the turnstiles to the platform, waiting on the platform, boarding and alighting process, etc.) would thus appear clearly important.
As regards the energy domain, the paper focuses on the analysis of energy-saving policies which are put in place for reducing energy consumption in railway systems. It is worth noting that this is closely linked to what has so far been described. Indeed, in order to implement proper energy-saving strategies, it is, above all, necessary to obtain a reliable estimate of the operational times involved (e.g. recovery times, inversion times, buffer times). Moreover, as the adoption of eco-driving strategies generates an increase in train running times and hence in passenger travel times, it is important to investigate the trade-off between energy efficiency and increases in user generalised costs.
Managing to model such a complex framework (Fig. 1), in which three different systems reciprocally influence each other, requires making use of suitable simulation and optimisation techniques. These enable both knowledge to be acquired on the effects of any intervention, prior to being carried out, and the best resolution strategy to be identified according to the target pursued.
The remainder of this paper is organised as follows: Sect. 2 provides a description of rail simulation models proposed in the literature; Sect. 3 deals with an extensive overview of rail optimisation models, both for planning and for management phases; Sect. 4 addresses estimation and forecasting techniques for travel demand and the related peculiarities in the case of rail systems; Sect. 5 illustrates contributions to the implementation of energy-saving strategies; Sect. 6 presents an overview of the most widely used metaheuristic algorithms for solving dispatching and rescheduling problems; this is followed by some concluding remarks in Sect. 7.
2 Rail Simulation Models
As shown by [1], in the both design and management phases, it is necessary to rely on suitable simulation techniques, which allow the effects of any intervention to be identified, before being put into practice, so as to give adequate support to the decision-making process. The railway simulation models proposed in the literature can be classified according to different criteria. A first criterion concerns the level of detail adopted for the representation of the network and enables the distinction among macroscopic, microscopic and mesoscopic models.
Macroscopic rail models describe the network by means of a graph whose nodes indicate the various stations and whose links usually define the frequency and travel times of the various trains. The main advantages of macro-approaches lie in the fact that they require a limited set of input data and a low computational effort. As this makes them able to deal with large-size networks in a reasonable computation time, they are usually implemented in planning phases to carry out strategic evaluations related to different infrastructure scenarios or solve routing problems which consist in defining train paths without time restrictions. However, the low degree of detail adopted in the network representation affects the accuracy of results: they usually contain far fewer nodes and links compared to the microscopic model and consider infrastructure in a more abstract manner. This means that such models are unable to reproduce some aspects such as signalling equipment installed and layout of station tracks and thus are unable to detect train conflicts or provide a reliable estimation of running times.
Microscopic rail models, by contrast, portray the networks in great detail. They take into account information concerning tracks (e.g. the number, length and alignment of the block sections, speed, gradient), features of the signalling system (e.g. signal position, release points, permissive occupancy), layout of stations (e.g. number of tracks, length of platforms, shunting yards, points, vehicle depots), characteristics of the rolling stock (e.g. acceleration/deceleration features, tractive/effort diagram, total and adherence load), operational information (e.g. departure/arrival times, routes, alternative platforms, timing points, dwell times, connections between runs) as well as safety conditions. The variation of each attribute leads to the creation of a new node and hence necessarily of a new link. Such modelling of the infrastructure can be used for operational needs such as calculating travel times, drawing up timetables, detecting probable train conflicts, addressing disruption conditions and testing rescheduling strategies. Hence, they provide very accurate results, albeit requiring the collection of a large amount of data and considerable computational effort.
Mesoscopic rail models represent an intermediate approach between macroscopic and microscopic models. They simulate the performance of the network at an aggregate level, by using aggregate variables such as capacity, flow and density. Traffic, therefore, is represented by convoy packets with identical characteristics (destination, routing behaviour, etc.) which propagate on the network. The main advantage of such models concerns the minimisation of the effort required to represent complex problems. Indeed, they allow only the effectively relevant elements to be analysed and neglect factors which, on the contrary, are not pertinent to the true aim of the study. This permits a simplified simulation of articulated contexts in order to respond to both strategic and tactical needs.
Hereafter, different software packages and tools implementing the above-mentioned kinds of models are described. A first example of macro-simulation model is NEMO—Network Evaluation MOdel (Fig. 2), which was developed by [2] for supporting the planning phase. Indeed, it can compute costs and earnings for different scenarios, thus allowing a comparison among them on the basis of an economic evaluation. Another macro-simulation model is SIMONE—SImulation of MOdel NEtwork (Fig. 3), developed by [3], whose possible applications regard strategic planning decisions (e.g. the possibility to build a new railway infrastructure or the allocation of network capacity to train operating companies) and the assessment of the stability and robustness of timetables. Among macro-simulation software packages, it is worth also citing TransCAD which is a commercial GIS (geographic information system) software specifically developed for transportation analysis. In particular, railway lines are treated by the software as transit lines and their representation is carried out by means of the Route System Toolbox (Fig. 4). It is thereby possible to model the line with its route and stops, as well as its relevant features (such as headway and capacity) which are stored in the associated database. Network representation can then be completed with additional links (e.g. pedestrian links, connectors) or nodes (e.g. centroids), characterising them with the related attributes which are saved in the associated dataview. After the implementation of the transit network, a matrix of passenger flows between origin and destination locations can be uploaded and transit assignment can be performed. The output is a specific database (i.e. transit flows) which provides link levels and aggregates ridership statistics at every stop along each route such as, boarding and alighting counts, stop-to-stop flows and route-to-route transfers. An example of a transit network representation by means of TransCAD is shown in Fig. 5.
On the other hand, among the micro-simulation models, it is worth mentioning the software RailySis, developed by [5]. It is essentially aimed at simulating different operational scenarios and comparing them in terms of timetable performance. For this purpose, very detailed modelling of delays is performed by appropriately taking into account their stochastic nature. The architecture of the model is shown in Fig. 6.
The structures of two other micro-simulation software packages, namely OpenTrack [6, 7] and EGTRAIN—Environment for the design and simulaTion of RAIlway Networks [8, 9], are depicted, respectively, in Figs. 7 and 8. As can be seen, they are built on a very similar architecture which is based on: different modules providing input data, a simulation core and several possible outputs. The input modules provide data concerning infrastructure, signalling systems, stations, rolling stock and planned timetables which are modelled with a high degree of detail.
In order to represent the motion of rail convoys in the most realistic way, OpenTrack adopts the so-called column graph or double-vertex graph. In such a graph, each node can be crossed if and only if both vertexes of the node are crossed and this allows a valid representation of the network to be obtained, especially in the case of points. Moreover, OpenTrack follows a hierarchical structure which requires that specific elements be carried out in a given order, that is block sections, routes connecting, contaguous sections, itineraries connecting contiguous routes, runs combining an itinerary with a specific kind of train and a specific departure/arrival time and, finally, the planned timetable made up of all runs on duty. Regarding the simulation core, this software performs a mixed discrete/continuous simulation process which calculates both the continuous numerical solution of the differential motion equations for the trains, by means of Euler’s method [10], and the discrete processes of signal box states and delay distributions. Furthermore, it presents a very user-friendly GUI (graphical user interface) which displays the infrastructure as a double-vertex graph, together with the animation of trains along their route, and offers the possibility of visualising interactive messages and measurement tools during the simulation. EGTRAIN, by contrast, does not provide any GUI (the interface with the user consists of a simple Win-32 Console window) and performs a time-discrete simulation (i.e. the clock goes ahead with discrete time where each time instant t is obtained as the sum of the previous time instant t − 1 and the defined time step Δt: t = t − 1+ Δt).
Finally, both simulation tools provide similar outputs: train motion diagrams (speed–distance, speed–time, distance–time trajectories); occupation times of rail sections (in both numerical and graphical format); track conflicts; statistics, such as the percentage of delayed trains at a certain station and overall train punctuality (fixing a certain delay threshold); energy consumption diagrams (electrical or mechanical power–time diagrams, electrical or mechanical energy–space diagrams). However, these software packages are aimed only at simulating train services, without considering its interactions with travel demand, whose influence has an impact on estimating dwell times to be implemented in the simulated timetable. Moreover, it is worth noting that, while OpenTrack is a commercial software whose code is clearly unknown, since it works as a black box, EGTRAIN is software developed for research purposes in C++ language, hence offering the possibility of developing new functions and performing interactions with other models in a very simple way.
Finally, for the sake of completeness, it is worth mentioning two other micro-simulation engines, namely Arena [11] and AnyLogic [12], which, although not specifically developed for transportation applications, but more generally for decision-making tasks, are widely used for modelling railway systems. They are especially widely adopted for simulating the interaction between rail systems and passenger flows (see, for instance, [13] and [14]). However, such tools do not perform the integration of train motion equations and therefore consider virtual (i.e. non-real) train movement features. By way of illustration, Figs. 9 and 10 show rail systems modelling, respectively, in Arena and AnyLogic environments.
Moving onto the class of mesoscopic models, it is worth citing the contribution of [16], concerning the development of an event-driven multi-train simulation model which was implemented by means of Stochastic Activity Networks (SANs) formalism [17, 18]. Specifically, as shown by [19], SANs can be considered a stochastic variant of Petri nets developed for dealing with non-functional properties of a system such as its performability. Indeed, this mesoscopic model aims to perform a RAMS analysis [20], so as to assess global effects of breakdowns on rail services and simulate strategic operations for re-establishing ordinary service conditions (e.g. moving a broken train to the depot and substituting it with a spare). The computational efficiency of this model is due to the fact that only main events, such as modifications in signal aspects or train arrivals/departures from sections, joints and stations, are taken into account, while events relative to train acceleration/deceleration phases are neglected.
Moreover, [21] developed a mesoscopic model for simulating freight train operations in a rail network by means of the event-based simulation computer package Simul8 which adopts a decomposition approach. It consists in separating the whole system into its components (i.e. rail lines, rail yards, rail stations, rail terminals and junctions) and capturing the interactions existing among them by modelling the network as an interconnected queuing system, so as to preserve the global perspective in operating performance estimation.
Finally, [22] proposed a mesoscopic network model for addressing the timetabling design problem. In particular, this model is implemented in the tool TTPSW which is able to iteratively generate different timetables, in a reasonable time, so as to perform the cyclic optimisation procedure depicted in Fig. 11.
Approaches aimed at transforming a micro-model into a macro one and vice versa are possible. In particular, as shown by [23], the derivation of a macroscopic model from a microscopic framework is known as a bottom-up approach, while the top-down approach can be used for generating artificial microscopic infrastructure whose level of detail depends on the problem addressed and the perspective analysed.
Clearly, the bottom-up approach is the most widely used, since it is straightforward to implement inasmuch as the final model requires less information than the starting one. In this context, [24] developed a particular interface enabling data migration between Railsys and NEMO models with the aim of supporting the generation of a conflict-free timetable. Moreover, [25] derived a macroscopic framework starting from a microscopic model, implemented in OpenTrack, for determining conflict-free track allocations. In particular, the transformation occurs by means of the aggregation of block sections and station areas, together with the introduction of ‘pseudo-nodes’ which replicate the interactions among different convoys. In addition, after deriving the macroscopic from the microscopic model, the proposed procedure combines them with each other in order to validate the solutions provided.
Indeed, several contributions in the literature arranged frameworks based on the combination of two different approaches, so as to be able to exploit the advantages of both of them and overcome their drawbacks. Macro- and micro-approaches are generally merged or combined in an iterative manner. In this context, [26] developed a micro–macro framework for timetabling design which consists in performing an iterative adjustment of trains running and minimum headway times, so as to determine a feasible timetable and, in addition, analyse its stability and robustness features. Moreover, [27] illustrated the tool ROBERTO based on a microscopic representation of the network, whose outputs (i.e. running and headway times) are used as inputs for the macroscopic timetabling model DONS [28].
In the meanwhile, a first attempt in combining mesoscopic and microscopic models was made by [16] with the aim of carrying out stochastic analysis in a rescheduling framework. The idea consists in exploiting the major computational efficiency of a mesoscopic model for performing millions of ordinary service simulations and, only when a failure occurs, bringing into play the microscopic simulator (i.e. EGTRAIN) so as to derive a more accurate and focused analysis.
Another classification criterion is dictated by the processing technique implemented, according to which it is possible to distinguish between synchronous and asynchronous simulation models. Synchronous approaches simulate events as they occur in reality. Therefore, a chronological progression is followed, with no chance of returning to previous states. Hence, this kind of simulation follows an event-driven approach and is generally applied to evaluate network performance, taking into account interactions among trains. By contrast, in asynchronous models, the convoys are simulated according to their class of priority, which means that the simulation is divided into several steps on the basis of a particular principle which is related to the category the trains belong to: the trains belonging to the higher categories are first simulated and are therefore unaffected by interactions with other convoys. Progressively, trains belonging to other categories are then processed until the service is completely simulated. A typical application of such a hierarchical procedure is the construction of a timetable in the planning phase. Examples of synchronous commercial simulation tools are: VISION [29] developed in the UK, FALKO [30] distributed by Siemens and RAILSIM X [31] commercialised by the Systra Group. On the other hand, examples of asynchronous models are BABSI [32] and STRESI [33], both developed at the RWTH Aachen University in Germany.
Finally, according to the assumptions on the distribution of the parameters involved, a distinction may be drawn between deterministic and stochastic simulation models. The deterministic case deals with parameters characterised by a steady value equal to their average, which means that factors such as departure/arrival times, dwell times and travel times are processed as constant quantities. On the other hand, in the case of stochastic simulations, parameters involved are considered as random variables and are therefore modelled by means of their probability density function (pdf), as well as the mean and the standard deviation of the pdf itself. Deterministic models are generally implemented in design phases, while stochastic models are more suitable for evaluating network performance (e.g. robustness of timetables, stability against disturbance, impacts of operational strategies), since they better reflect the actual conditions. Many types of software, such as the above-mentioned OpenTrack and EGTRAIN, can be used to perform both deterministic and stochastic simulations. Specifically, EGTRAIN allows stochastic delays and failures to be simulated, while OpenTrack is able to take into account stochasticity of train performance, dwell time and delays, performing a set of simulations by randomly changing input parameters.
In Table 1, a comprehensive classification of the analysed simulation tools is provided. Clearly, given the relevance of randomness disturbances for a realistic and reliable evaluation of rail system performance, most of the analysed software is able to perform both deterministic and stochastic simulations. Moreover, in many cases, the possibility of performing asynchronous simulations coexists with the option of adopting a synchronous approach.
3 Rail Optimisation Models
The issue of managing and optimising railway operations is addressed in the literature as dispatching and rescheduling problems, which consist in monitoring and controlling to ensure smooth running of rail services, as well as re-establishing ordinary conditions, in response to any kind of system failure, by adjusting the planned service to the actual situations.
In particular, there are two dimensions of interest: an offline design phase and a real-time operational phase [34]. The first stage concerns the design of the railway timetable and the analysis of its stability, while the second stage is related to the management of the service in real time so as to properly react to system failure and provide an effective solution as rapidly as possible. Table 2 shows the main differences between the two phases.
A further distinction, shown in Table 3, was proposed by [35] according to which rescheduling tasks can be performed statically or dynamically on the basis of the input information used, as opposed to the timetabling phase which is intrinsically an offline and static process. In static methods, input data are processed only once with a fixed value, while in dynamic approaches the values of input parameters change over time. Moreover, dynamic rescheduling approaches can be distinguished into reactive, if they neglect a view of the future, and proactive, if they consider future conditions in a probabilistic and time-dependent way.
The close relationship between the two above-mentioned management dimensions is evident: a well-designed timetable, with a high degree of stability and robustness, makes the rescheduling process easier and smoother.
3.1 The Timetabling Phase
The timetabling process for a railway line consists in establishing the departure and arrival times of each convoy at each station being served, respecting the limits imposed by safety, law, the infrastructure, signalling system and the need to guarantee a certain number of transfers. The process is crucial for the entire railway operation as it influences, directly or indirectly, system performance, the degree of use of the infrastructure capacity, service quality, the management of rolling stock and crew scheduling.
This section is structured as follows. First, a literary review focusing on the main issues related to the timetabling process is provided. Specifically, the adopted criteria are: (1) features of cyclic timetable structures; (2) timetable performance measures; (3) implemented methodological approach; and (4) adopted objective function. Then, the interactions between the timetable and energy domain on the one hand, and the timetable and passenger flows on the other, are briefly recalled in the light of the treatment provided in Sects. 4 and 5.
Generally, timetables are characterised by the adoption of cyclic structures, which can include particular properties, namely periodicity, synchronisation and symmetry. Periodicity consists in setting regular intervals between trains during the whole service; synchronisation regards the coordination of departure and arrival times of the planned runs in order to provide feasible transfers for passengers; symmetry concerns the adoption of the same timetable features in both directions and, as shown by [36], it makes sense only if travel times and dwell times are the same in both ways and travel demand is symmetrical as well.
Periodic timetables are usually modelled by means of a Periodic Event Scheduling Problem (PESP), introduced by [37]. This approach is widely adopted [38,39,40,41]. Moreover, [42] described a stochastic variant of the PESP which takes into account random disturbances to rail services; [43, 44] proposed a synchronisation model which minimises waiting times for passengers. Similarly, [45] developed a timetable optimisation framework implementing particle swarm optimisation and simulated annealing for enhancing the performance of transfer synchronisation between different rail lines. Finally, an example of an optimisation framework for symmetrical timetables can be found in [46], whose approach duly takes account of modal split and travel demand.
Timetable performance measures are reliability, punctuality and robustness. Reliability is the ability of a system or a component to perform its required functions under stated conditions for a specified period of time [47]; punctuality is usually defined as the probability of a train arriving less than x minutes late [48]; and robustness refers to the capability of avoiding delay propagation as much as possible [49]. A robust timetable is generally designed by suitably introducing buffer times for absorbing potential delays. However, it is necessary to strike the right balance between the use of railway capacity and the robustness of the timetable [50,51,52,53]: with an increase in buffer times, the timetable presents greater flexibility and thus an increased chance of absorbing delays, avoiding their spread. However, this could lead to an under-usage of system capacity.
In [54], we can find an interesting design methodology for railway timetables, featured in Fig. 12, where two feedback cycles are proposed: one on the stability of the timetable (ex ante analysis) and the other on the punctuality of the system (ex-post analysis). As regards stability analysis, the contribution extends to the railway case of the methodology proposed by [55, 56], based on max-plus algebra, introducing constraints dictated by the infrastructure and the signalling system. With regard to ex-post analysis, which requires the acquisition of measurements relative to the service actually performed, the author proposed a tool called TNV-Prepare.
Moreover, [57] provided a two-stage model for carrying out robust timetables in which, after obtaining a stable timetable structure (i.e. a structure which minimises the trade-off between capacity utilisation and travel times), the optimal allocation of time supplements and buffer times is derived. In addition, a delay propagation model is implemented for validating the obtained timetable. Similarly, [58] developed a three-stage framework aimed at identifying robust timetable structures by means of a combination of linear programming with stochastic programming and robust optimisation techniques. In particular, first the train timetabling problem (TTP) is modelled neglecting robustness; in the second step, different training methods, which essentially test the impact on the system of the occurrence of delays, are implemented and, finally, a validation phase is performed. Furthermore, [59] proposed an optimisation methodology for maximising timetable robustness in which the variability of dwell and travel times, as well as the possibility of overtaking, are considered. In addition, [60] improved the approach developed by [61], proposing a method for generating periodic timetables aimed at maximising timetable stability indirectly, i.e. by optimising the cycle time. Indeed, as shown by [62], a timetable can be stable only if the nominal timetable period is higher than the minimum cycle time. Moreover, the degree of stability grows with the increase in the gap between these two quantities. Furthermore, [63] developed a stochastic delay propagation model which evaluates timetable robustness by means of individual and collective measures, related, respectively, to primary and knock delays, and tested it on a portion of the Indian railway network. As to timetable performance addressed in the literature, it is worth citing the following contributions: [64] which proposed an integrated timetabling/delay management framework by introducing a new concept of robustness, known as recoverable robustness, and [65] which derived a method for comparing different timetable structures in terms of attractiveness for passengers, computing the so-called time displacement between what travellers desire and the scheduled service, whose formulation takes into account frequency and travellers’ time adaptability.
Simulation-based approaches for performing the timetabling phase can be found in [66, 67]. In particular, the former proposed an integrated framework which combines a micro- and a macro-network representation. The timetable structure is carried out at the microscopic level, thanks to a very precise adjustment of running times and minimum headways, while, at the macroscopic level, the trade-off between travel times and degree of robustness is performed. By contrast, [67] proposed a design approach aimed at generating a robust and energy-efficient timetable by means of a three-stage process which combines different levels of analysis: microscopic, macroscopic and a corridor fine-tuning level. The basic idea is to optimise each performance indicator at an appropriate level so as to obtain a more reliable evaluation.
Clearly, bearing in mind the importance of the above-mentioned issues related to the stability and robustness of a timetable, different objective functions can be considered, according to the examined contexts: [68] proposed a methodology to optimise the timetabling process so as to find the right balance between the quality of service and operational costs; [69] introduced an optimisation problem in which the objective function to be maximised is the degree of use of the railway infrastructure; [70,71,72,73] proposed demand-oriented timetabling methodologies. Moreover, [74, 75] modelled the timetabling phase as a constrained job-scheduling problem, in which the objective function to be minimised is the total delay. In particular, the introduced restrictions are relative to travel demand and to the connections between runs, in order to guarantee a minimum number of transfers. Furthermore, the optimisation of the timetabling phase in an energy-efficient perspective can be found in [76, 77]. The close relationship between timetable, eco-driving profiles and energy-saving strategies will be explored in Sect. 5.
Moreover, it is worth noting that a crucial factor of the timetabling process is the estimation of dwell times, above all in the case of congested lines, given their nature of flow-dependent factors. Indeed, during the boarding/alighting process rail operations are directly affected by passenger flows and this implies a twofold impact. On the one hand, there arises the need to perform a reliable estimation of the flows involved (i.e. boarding, alighting and on-board flows); on the other, the implementation of proper estimation techniques for computing dwell times proves imperative in order to ensure a high degree of timetable robustness, thus making the service more reliable and attractive. Specifically, estimation techniques of travel demand flows are addressed in Sect. 4, while an extensive overview of the dwell time estimation methods can be found in [78].
3.2 The Rescheduling Problem
The rescheduling problem covers much of rail operations research, since the advantages offered by rail transport, in terms of high travel speed and low headway values (due to exclusive lanes, constrained driving and signalling systems), are counterbalanced by intrinsic vulnerability to failure. This means that, during the management of disruption conditions, dispatchers cannot be forced to count only on their experience (e.g. by presuming the amount of recovery times or the most successful intervention strategy), but they must be able to rely on suitable decision support systems which enable them to act suitably and effectively.
Generally, recovery strategies are implemented according to three consecutive phases: timetable rescheduling, rolling stock rescheduling and crew rescheduling. However, what follows is essentially focused on timetable rescheduling.
As shown by [23], the rescheduling process consists in two successive steps. The initial phase concerns identification of potential conflicts on the basis of the current state of the infrastructure, the characteristics of operational times, the availability of rolling stock and the position and travel speed of each convoy. This is followed by a problem-solving phase which, according to the results of the previous step and the delays actually occurring, identifies the most appropriate strategies for re-establishing normal operating conditions.
The rescheduling methodologies proposed in the literature, according to different factors, are classified below. Specifically, the criteria considered are the following: (1) methodological approach performed; (2) level of detail adopted; (3) established workflow; (4) embedded level of randomness; (5) implemented degree of interaction with travel demand; (6) types of networks analysed; (7) severity of failures modelled; and (8) perspective adopted.
Rescheduling problems are frequently addressed by means of simulation-based methods and therefore railway optimisation models, like their simulation counterparts, can be classified into macroscopic and microscopic, according to the degree of detail implemented. Moreover, two main modelling approaches are generally adopted which are based on the implementation, respectively, of the so-called Alternative Graph (AG) and Mixed-Integer Linear Programming (MILP) formulations.
The Alternative Graph model was proposed by [79] as a generalisation of the disjunctive graph formulation of [80]. Essentially, it allows railway operations to be simulated as a job-shop scheduling problem, i.e. the problem of allocating machines to competing jobs over time, subject to the constraint that each machine can handle at most one job at a time. Therefore, each operation denotes the traversal of a resource (block/track section or station platform) by a job (train route). In particular, [79] introduced additional constraints, known as blocking and no-wait constraints, modelling, respectively, the absence of storage capacity among machines and the condition in which two consecutive operations in a job must be processed without any interruption. Several rescheduling methodologies based on the implementation of the alternative graph, together with blocking time theory [23], have been proposed in the literature for dealing with different dispatching problems. One of the first disruption management methods based on this approach can be found in [81] which developed a decision support system for real-time traffic management, called ROMA (Railway traffic Optimisation by Means of Alternative graphs). The tool in question solves the real-time train dispatching problem by subdividing it into four sub-problems:
-
data loading and exchange of information with the field;
-
assigning a passable route to each train in order to avoid blocked tracks;
-
defining optimal train routes, ordering and specifying exact arrival and departure times at stations and at a set of key points in the network;
-
ensuring a minimum distance headway between trains while maintaining acceptable speed profiles.
In [82], ROMA was integrated with the microscopic traffic simulator EGTRAIN so as to incorporate the dynamic evolution of traffic conditions into the dispatching procedure.
Other rescheduling approaches based on the adoption of the alternative graph concern: delay management problems [83], re-routing recovery actions [84,85,86] and conflict resolution tasks [87]. Also, large network contexts and very severe disruption conditions can be addressed by means of such an approach [88]. Moreover, formulations of alternative graph targeting for dealing with disruption conditions in rail lines with moving-block signalling systems (i.e. headway is computed as a minimum time lag on each section for two consecutive trains) were developed by [89,90,91].
While rescheduling methods based on the alternative graph generally adopt a microscopic approach, works implementing mixed-integer linear programming (MILP) formulations proposed in the literature deal with both microscopic [92,93,94] and macroscopic [95,96,97,98,99,100,101] frameworks.
Further, [102] proposed a real-time recovery management model, for dealing with multiple disruptions, which adopts heuristic dispatching rules and integrates different intervention strategies such as reordering, retiming, speed control and dwell time adjustment; [103] developed an integer programming model with an innovative formulation with network-based cumulative flow variables for addressing a simultaneous train re-routing and rescheduling problem; [104] formulated a mixed-integer programming model, for handling a complete blockage disruption on high-speed lines, whose aim is to minimise the total weighted train delay and the number of cancelled trains, in accordance with headway and station capacity constraints; [105] addressed the timetable rescheduling problem by developing a binary mixed-integer programming model aimed at minimising the time difference between the planned timetable and the rescheduling one which is expressed in terms of train-order-entropy.
The main advantage offered by macro-approaches lies in their lower computational effort which, for example, allows the operator to deal with complex objective functions, as in [106], where a macroscopic multi-objective framework, taking into account passenger satisfaction, operational costs and deviations from the undisrupted timetable, is proposed. On the other hand, by using micro-simulation approaches, as already pointed out, the interactions among system components (i.e. infrastructure, signalling system, rolling stock, timetable and travel demand) can be explicitly modelled and the quantities involved accurately computed (e.g. running times, dwell times, headways). Therefore, in order to benefit from the advantages of both approaches, also integrated frameworks which combine these two modelling techniques have been proposed in the literature. In this context, [107] proposed a rescheduling method including both a macroscopic and microscopic model of the network. In particular, the macroscopic representation is implemented in an optimisation framework, based on the model developed by [108], whose aim is to derive timetables and rolling stock schedules in the case of failure. On the other hand, microscopic representation is used for the simulation model, which is based on the proposal of [109], whose structure includes the service simulation model (SSM) and the on-platform model (OPM) for assigning travel demand to the rail network. Moreover, [110] developed an iterative optimisation framework in which a delay management problem is solved macroscopically and then validated microscopically by means of a train scheduling model taking into account the limited capacity of stations. Specifically, the original timetable and travel demand flows are given as initial input data, together with a set of delays computed on arrival. With this information, the algorithm solves the delay management problem by identifying the connections to be maintained and carrying out an expected macroscopic timetable. Thus, the output of the delay management problem becomes the input of the train scheduling problem, whose resolution consists in analysing potential conflicts around stations and estimating delay propagation. The fact that these delays are computed by means of a microscopic approach ensures an accurate degree of estimation. Hence, they are, in turn, implemented in the delay management problem which is run again and, at the end of the iterative process, a timetable minimising passenger delays is designed. Finally, [111] proposed a combined macro–micro approach for solving the delay management problem from an energy-saving perspective.
The above-mentioned works adopt a synchronous approach since the aim of the analysis is to address events like deviations from the planned service, propagation of delays and system failures. By contrast, the asynchronous approach is generally implemented for solving conflicts between trains belonging to different categories, by always giving priority to trains in a higher category [112]. However, clearly, asynchronous solving conflict algorithms cannot guarantee a global optimum as a solution.
Finally, although the literature contains some deterministic rescheduling methodologies [100, 113, 114], given the random nature of the factors involved the stochastic approach is the most accurate. The importance of taking into account the stochasticity of events lies in the fact that the stability of rail services is very sensitive to the presence of even small variations in the performance of convoys or dwell times, above all due to the risk of a knock-on effect of propagation of delays which would negatively affect the entire system. In this context, [115] described the influence on system performance of the stochasticity of design variables within the railway timetable; [116] proposed a probabilistic analytical model which makes a realistic estimate of delay propagation and provides an assessment of delay impact on the service punctuality; [117] developed a stochastic simplified graphical modelling approach, for identifying dependencies among delays, which is based on the so-called tri-graph (proposed by [118, 119]), allowing a compact representation of different kinds of delay: primary delays, secondary delays (due to the propagation of primary delays) and delays due to the restricted capacity of the railway infrastructure. The relevance of considering delays as time-dependent random variables is stated also by [120, 121] which modelled the uncertainty of train delays, respectively, by means of a Markov stochastic process and Bayesian networks. In addition to delays, also other randomnesses have been modelled. Within this framework, [122] introduced a stochastic disturbance on train performance, while stochasticity of arrival and recovery times is taken into account in the rescheduling models proposed by [123, 124]. Furthermore, [125] analysed the impact of considering uncertainty in the rescheduling framework by comparing the results of different algorithms, both in deterministic and in stochastic scenarios. In particular, train delays are modelled by means of a statistical distribution, while running and dwell times are perturbed with stochastic variations. Similarly, stochasticity of train performance and dwell times is modelled in [126]. In addition, the uncertainty of disruption information is addressed by [127] which developed a stochastic and dynamic rescheduling model aimed at minimising total train delay in the case of a single-track rail line. Further, the proposed approach is implemented in a rolling horizon framework: the robustness of rescheduling strategies is evaluated considering random segment running times and a segment capacity breakdown with an uncertain duration. Finally, [128] developed a metro rescheduling model which takes into account the stochasticity of travel demand: the arriving ratio of passengers at each station is modelled as a non-homogeneous Poisson distribution in which the intensity function is treated by means of time-varying origin–destination matrices.
In rescheduling problems, two fundamental, strictly related issues have to be taken into account: on the one hand, the interaction between rail operations and travel demand and, on the other, capacity constraints of the rail service. In particular, the interface between rail operation and passenger flows is represented by the boarding and alighting process which is obviously affected by the available capacity. For the sake of clarity, it is worth noting that taking into account the influence of travel demand on the service is aimed at making the simulation as realistic as possible, irrespective of the final purpose of the analysis (i.e. whether or not the final aim is to satisfy passenger needs). However, issues related to the impact of travel demand on rail service and the minimisation of passenger discomfort are generally addressed together due to their strict relationship. Indeed, boarding, alighting and on-board flows affect the performance of the rail service and, therefore, its attractiveness which, in turn, affects passenger satisfaction. Hence, realistic modelling of boarding and alighting allows more accurate estimation of passenger inconvenience, for example, in terms of waiting times for users on the platform or in terms of total travel times for on-board users. Rescheduling methodologies which fulfil these requirements can be found in [129], which dealt with post-disruption operations at the station platform level and [130] which introduced capacity constraints for taking into account the fact that, especially in crowded contexts, not all passengers waiting on the platform are actually able to board the first arriving train. Furthermore, [131] developed a rescheduling framework for minimising the delay time of alighting passengers, as well as the penalty time of stranded passengers, and [132] proposed a dynamic passenger assignment model which implements an event-based simulation technique for modelling alighting and boarding. In particular, in the latter, passengers’ en route travel decisions are considered and all phases occurring during a disruption event (i.e. the first transition phase from the planned timetable to the disruption timetable, the second phase where the disruption timetable is performed and the third recovery phase from the disruption timetable to the planned timetable) are modelled. This is a very important point, since passengers who start their trip in different phases are generally affected differently by disruption. Moreover, time variability of travel demand, disruption-induced service changes and capacity constraints of convoys are explicitly taken into account. In general, the dynamic interaction between rail service and travel demand is considered in the following contributions: [133] proposed a disruption management approach, in the case of a metro system, based on a skip-stop pattern, which involves the analysis of time-dependent passenger flows under conditions of limited train capacity; [134] developed a model for analysing short-turning and deadheading rescheduling solutions which takes into account the dynamic behaviour of travel demand along the considered planning horizon and aims to minimise passenger overload and improve service quality; [135] proposed a macroscopic rescheduling approach which combines rolling stock and timetable recovery strategies by considering adjustments of stopping patterns in a passenger-oriented perspective. In particular, in the latter, the adopted resolution method is a greedy technique based on the passenger flow simulation algorithm proposed by [136].
Moreover, disruption management problems may concern metro [137, 138], regional [139, 140] or high-speed services [141, 142]. Furthermore, different degrees of network complexity can be addressed. In particular, the level of complexity increases from a single-track case [127] to an N-track context [103] and from a single line [143] to a large network [144,145,146]. Also, networks with mixed traffic can be analysed, with a further increase in the degree of complexity tackled. For example, [147] developed an online rescheduling model for dealing with different types of train categories (both for passengers and for freight) and different priority rules.
Another classification criterion for rescheduling approaches is the severity of the failure analysed. Indeed, as shown by [148], it is possible to distinguish between disturbance and disruption: disturbances are generally considered as small perturbations influencing the system, while disruptions indicate large external incidents which can lead to the cancellation of runs within the timetable or even to the interruption of the whole service. Clearly, the greater the severity of the failure, the greater the impact of the corrective measures to be adopted. For instance, [149] dealt with the problem of connection and re-routing in the case of a delay occurrence; similarly, [150] developed a learning strategy for the online delay management problem. On the other hand, more severe perturbations are addressed by [151, 152]. In particular, [151] analysed a serious disruption where some block sections have a reduced maximum speed, together with others which are totally unavailable for traffic, by implementing the alternative graph, while [152] developed a macroscopic rescheduling approach for handling cyclic timetables, in the presence of large-scale disruptions, which is based on an integer linear programming (ILP) formulation taking into account infrastructure and rolling stock capacity constraints. Moreover, [153] presented a macroscopic rescheduling model to compute the disruption timetable for a complete blockage with a focus on short-turning trains. Partial and complete blockages are also addressed in [97], which developed integer programming formulations for maximising service quality and tested them on case studies from the Netherlands Railways.
Finally, different perspectives can be introduced in rescheduling models. First, as stated above, several works propose passenger-oriented methodologies. In addition to the already cited contributions, other passenger-centric approaches can be found in [154,155,156,157,158,159,160]. Typical measures of service quality used for determining passenger satisfaction resulting from rescheduling strategies are: cumulative delays, waiting times, user generalised costs, removed connections, a penalty time of stranded passengers. Obviously, passengers are not the only players in the rescheduling process. Indeed, the other parties involved are infrastructure managers and train operating companies. On the one hand, train operating companies are interested in minimising both passenger discomfort and operational costs associated with the rescheduling strategies implemented. On the other hand, infrastructure managers aim to reduce train delays, even if this means cancelling runs or suppressing connection services. Works which, in addition to passenger needs, considered the operational costs of train companies are those proposed by [106, 161]. In this context, it is also worth citing [162] which computed different measures of costs resulting from the disruption management process, such as total operational cost for passenger services, total operational cost for empty movements and total number of schedule changes (i.e. services, composition and inventory train changes), as indicators of the effort made by rail companies to put recovery strategies in place. The trade-off between the targets pursued by the two above-mentioned stakeholders (i.e. infrastructure managers and train operating companies) is addressed in [87, 163, 164]. In addition, since the reduction in energy consumption is one of the main goals of railway companies, as already touched upon, rescheduling methods which adopt an energy-saving perspective have also been proposed, confirming the close relationship among the analysed domains. Energy consumption and saving will be discussed in Sect. 5.
In the light of the above, it is understandable that rescheduling problems are strongly NP-hard and, therefore, for their resolution, it is necessary to rely on proper heuristic and metaheuristic methods which are able to find sub-optimal solutions within suitable computation times. Such techniques are adopted for solving transport problems of widely different kinds, as will be shown in Sect. 6.
4 Estimation Techniques for Travel Demand Flows
In order to obtain accurate results by means of simulation and optimisation frameworks, explicit modelling of travel demand has a fundamental role. Indeed, reconstruction, estimation and prediction of travel demand [166] represent key aspects to be addressed in any kind of assessment regarding transportation systems, so as to optimise both planning and management phases. Strictly speaking, the interaction between the rail service and passenger flows occurs at the train–platform interface. Indeed, during the boarding/alighting process, different kinds of passenger flows (i.e. waiting flows, on-board flows, boarding flows and alighting flows) interact with each other, influencing the dwell time at the station and hence the timetable as a whole. This happens from a strict operational point of view, regardless of whether the adopted approach is demand oriented. A further step in the decision-making process is then related to the importance of generating passenger-oriented dispatching strategies, such as demand-oriented timetables; passenger-centric rescheduling solutions; energy-saving scenarios which achieve a fair trade-off between the reduction in energy consumption and the increase in user travel time.
In the light of the above, what appears evident is the importance of relying on suitable estimation and forecasting techniques for travel demand, which have to correctly take into account the peculiarities of the railway system as well as be able to properly model the behaviour of passengers in the various phases of the trip (turnstile access, transfer from the turnstiles to the platform, waiting on the platform, boarding and alighting process, etc.). This is the motivation for which travel demand estimation techniques have been carefully investigated in the overview provided.
Three different methods can generally be adopted: direct estimation [167,168,169], disaggregated estimation [170,171,172,173,174] and aggregate estimation [175,176,177,178].
Direct estimation enables the reconstruction exclusively of the present demand, without any capacity for future prediction. Strictly speaking, the O–D matrix is not directly observable in its entirety. Indeed, given the huge quantity of data to be collected, carrying out a census would not be economically doable even if, in certain instances, technically feasible. Thus, direct estimation actually consists in making use of sampling techniques together with inferential statistics methods for extending the information content of a sample to the whole analysed system. Different kinds of surveys may be carried out such as on-board surveys (also called cordon surveys if aimed at estimating the crossing demand), household surveys, destination surveys and (e)mail surveys. Additionally, in recent years, given the exponential growth in the field of Information and Communications Technology (ICT), further survey methods have been developed, namely CAPI (computer-assisted personal interviewing), CATI (computer-assisted telephone interviewing) and CAWI (computer-assisted web interviewing). However, whatever the approach adopted, as shown by [179], a preparatory design phase of the survey is required. Such a phase consists in first defining the sampling unit and the sampling strategy, which could generally be simple random sampling, stratified random sampling or cluster sampling. Then, according to the sampling method adopted, it is necessary to set up the sample size and the estimator to be applied.
However, should a certain predictive capacity be required, it is necessary to make use of a disaggregate estimation of the O–D matrix which consists in specifying (i.e. providing the functional form and related variables), calibrating (i.e. determining numerical values of model parameters) and validating (i.e. verifying the ability of the model to reproduce original data), by means of proper information, a model which manages to reproduce the variations in travel demand as a result of modifications in transport system performance or socio-economic conditions. In this case, two different survey approaches can be implemented: the revealed preference (RP) approach [179], which is based on the use of data related to real traveller behaviour, and the stated preference (SP) approach [180, 181], based on the statements of travellers related to their potential choices in the case of a hypothetical scenario, which has to be appropriately described and illustrated in order to make user declarations as reliable as possible. With the use of the second approach, the predictive capabilities of calibrated demand models can be improved. Hence, once the functional formulation of the model, together with the types of attributes to be considered, has been specified, it is necessary to carry out the calibration phase by means of which a numerical value is associated with each parameter involved. Generally, in order to calibrate a disaggregate demand model, the Maximum Likelihood (ML) method is performed [179].
Finally, the aggregate estimation of travel demand indicates a correction procedure of the O–D matrix which consists in updating a previously known matrix, through aggregate type data, such as traffic counts, in order to improve its reliability and guarantee accurate assessment of the system status in the forecasting phase. In this context, it is worth noting that, in contrast to the sample surveys which are complex and expensive, counts incur lower costs and can be obtained automatically.
This approach is expressed by [177] in terms of an optimisation problem:
where \( {\mathbf{x}} \) is the unknown demand vector; \( {\hat{\mathbf{d}}} \) is a prior estimate demand vector which is considered the target demand vector; \( {\varvec{\upnu}}\left( {\mathbf{x}} \right) \) is the vector of link flows obtained by assigning the demand vector x to the network; \( {\hat{\mathbf{f}}} \) is the vector of detected link flows.
The aim is to obtain a matrix \( {\hat{\mathbf{d}}} \) which is as close as possible to the prior estimate, and which, once assigned to the network, is able to reproduce link flows as close as possible to those detected. Therefore, this procedure can be considered as the inverse assignment problem (Fig. 13). Indeed, in the assignment process, starting from the knowledge of supply, demand and the model which regulates path choice, link flows on the network are defined. Conversely, in the estimation of the O–D matrix, starting from the detected link flows, together with the knowledge of supply and path choice models, the computation of demand is performed. The importance of the presence of a prior estimate demand vector \( {\hat{\mathbf{d}}} \) lies in the fact that, since the number of O–D pairs is generally much higher than that of detected link flows, without such a vector the problem would be intrinsically undetermined.
In the case of congested networks, the estimation problem of the O–D matrix can be formulated as a fixed-point problem [182, 183] or, alternatively, by means of a bi-level optimisation framework. In the latter, the upper level represents the estimation problem, while the lower level addresses the network assignment problem. Contributions related to the above approach are [184, 185], and, more recently, [186, 187] addressing a deterministic user equilibrium (DUE) assignment and [188,189,190] dealing with a stochastic user equilibrium (SUE) approach.
At this point, it is worth addressing the definition of functions \( z_{1} \left( \cdot \right) \) and \( z_{2} \left( \cdot \right) \) in Eq. (1), which represent the goodness of fit measures and can be expressed by means of different estimators. In particular, for the static approach, we can have the maximum likelihood [177, 191, 192], the generalised least squares [193] and/or the Bayesian [192]. A complete overview of the features and statistical principles of such estimators can be found in [179].
Moving onto within-day dynamic contexts, where travel demand varies within the time period analysed, the matrix representation consists in a certain number of matrices: they are as many as the temporal intervals into which the reference period has been subdivided. The introduction of a time dimension leads to two different estimation approaches, namely sequential and simultaneous, as shown by [194]. In order to describe such approaches, let the total study period \( H \) be divided into \( n_{h} \) intervals \( h \) (with \( h = 1 \, \cdots \, n_{h} \)) of equal length \( T \), such that \( H = n_{h} \cdot T \).
In particular, the simultaneous estimation can be specified as follows:
The aim is to identify matrices \( {\mathbf{d}}_{1}^{*} \cdots \, {\mathbf{d}}_{{n_{h} }}^{*} \), for each interval \( h \) into which the reference time period \( H \) is split, which minimise the ‘distance’, on the one hand, between the unknown demand vectors \( {\mathbf{x}}_{1} \cdots \, {\mathbf{x}}_{{n_{h} }} \) and the previously estimated demand vectors \( {\hat{\mathbf{d}}}_{1}^{{}} \cdots \, {\hat{\mathbf{d}}}_{{n_{h} }}^{{}} \); and, on the other, between the flow vectors \( {\mathbf{v}}_{1} \cdots \, {\mathbf{v}}_{{n_{h} }} \) (obtained by assigning demand vectors \( {\mathbf{x}}_{1} \cdots \, {\mathbf{x}}_{{n_{h} }} \) to the network) and the traffic count vectors \( \hat{\varvec{f}}_{\varvec{1}} \cdots \, \hat{\varvec{f}}_{{n_{h} }} \).
By contrast, in the case of sequential estimation, the following occurs:
In this context, one matrix at a time is identified, starting from the first temporal interval and proceeding until the last, maintaining the previously calculated matrices fixed time after time.
Generally, conversely to a simultaneous approach which is usually adopted for offline estimates, the sequential approach can be used for online applications. Indeed, it provides lower computational complexity, splitting the problem in question into different sub-problems which are easier to analyse. Thus, the matrix estimated for each time slice can be used as estimation input for the following time period. However, it presents the drawback of considering, for each demand vector \( {\mathbf{d}}_{h}^{*} \), limited information, i.e. traffic counts \( \hat{\varvec{f}}_{h} \), associated exclusively with the time interval to which demand vector refers. Therefore, in order to rectify this aspect, different contributions based on the adoption of Kalman filtering methodologies have been proposed [195, 196].
However, with the adoption of an assignment matrix, as shown by [197,198,199], the simultaneous approach assumes a prohibitive computational complexity, even in the case of medium-size networks. Therefore, in order to deal with more feasible computational times and, at the same time, adopt a simultaneous approach which is the most suitable from a conceptual point of view, several non-assignment based methods for dynamic O–D matrix estimation have been developed. Within this framework, after pioneering works by [200,201,202,203,204], more recent contributions proposed the adoption of evolutionary methods [205,206,207,208,209,210], simulating annealing techniques [211], bee colony optimisation [212], probe vehicle data [213] and artificial intelligence approaches [214,215,216]. Other major contributions are provided by [217, 218] which addressed the simultaneous adjustment of a dynamic traffic demand matrix by means of a gradient approximation approach representing a variant of the simultaneous perturbation stochastic approximation (SPSA) path search optimisation method proposed by [219, 220]. Further variants of the SPSA approach are W-SPSA proposed by [221, 222] and c-SPSA presented by [223]. Similarly, [224] proposed a method based on the use of linear approximations of the assignment matrix in optimisation iterations and tested several specific solution algorithms which differ in the search direction.
On completion of the above-mentioned contributions, regarding both static and dynamic frameworks, it is worth citing the work by [225] proposing a GLS-based within-day dynamic estimator which provides room for significant improvements in the unknowns/equations ratio, thanks to a quasi-dynamic approach based on the intuitive assumption of considering distribution rates as constant within a wider time interval compared to the within-day variation of the generation rates.
Another point strictly related to the above-mentioned aggregated estimation techniques is the Network Sensor Location Problem (NSLP) which addresses the relationship between survey costs and estimation accuracy [226,227,228,229,230,231,232]. Basically, it consists in identifying the optimal location (i.e. the location which maximises the information content) under a budget constraint (i.e. a given number of count sections). With the advances in the field of ICT, in addition to traffic counts, also other kinds of data sources have been implemented to carry out reliable estimation of O–D matrices, such as GPS data [233], video recordings [234], mobile phone data [235], e-ticketing and automatic fare collection systems [236,237,238,239,240,241,242,243,244].
5 Energy Issues Related to Rail Systems
In recent years, beyond improving the performance of rail systems so as to drive the modal split towards such a sustainable transport mode, thus reducing pollution and congestion effects due to private vehicle use, considerable attention has been focused on energy issues for reducing the energy consumption of systems based on rail technology. Therefore, dispatching and rescheduling decision support systems, based on an energy-saving perspective, are being increasingly used in rail transport research. On the one hand, the energy domain is linked to operational aspects of rail services (e.g. the need to synchronise train movements and proper planning of extra time resources for implementing eco-driving profiles), as will be extensively illustrated below. On the other, the goal is to reduce energy consumption without penalising passenger needs. In the light of the above, the strict correlation among rail services, travel demand and energy domain appears obvious. Hence, to complete the picture, this section provides an overview of the energy-saving approaches proposed in the literature.
The following strategies may be considered elements of energy-saving approaches: adoption of eco-driving profiles, regenerative braking, the introduction of timetable adjustments, exploitation of on-board and wayside storage systems, and the use of reversible substations. Clearly, they are strictly interrelated: the design of energy-efficient speed profiles consists in identifying the pattern which minimises tractive energy consumption, given a running time to be respected [245, 246], while strategies based on exploiting of regenerative braking aim to reuse the amount of kinetic energy produced during the braking phase by converting it back to electrical energy. In this case, the traction motor also acts as a generator and the recovered energy can be used at the same time or stored for later use by means of energy storage devices. For instance, an on-board storage device allows temporary accumulation of the excess energy regenerated and its release for the next acceleration phase of the same train [247, 248], while the aim of a wayside storage device is to release it when required for the acceleration of other convoys [249, 250]. In this context, timetable optimisation, aimed at synchronising acceleration and deceleration phases of convoys operating in the network, represents a key task for maximising the receptivity of the line [251,252,253,254]. Additionally, the role of an energy-efficient timetabling phase lies in the suitable design of all operational times involved, such as running times, buffer times, dwell times and reserve times [165, 255, 256]. Moreover, by means of reversible or active substations, the energy regenerated can also be fed back into the medium voltage distribution network [257,258,259]. An extensive overview of regenerative braking issues and energy storage systems, together with the above-mentioned related concerns, can be found, respectively, in [260, 261]. This work, instead, focuses on strategies involving the design of suitable speed profiles and optimisation of operational times within timetables from an energy-saving perspective.
With regard to eco-driving profiles, first of all it is necessary to introduce the reference scenario, indicated as the Time Optimal (TO) scenario, which consists in considering the movement of the convoy in the event of maximum performance. In the first phase, the train adopts maximum acceleration in order to reach the maximum speed (acceleration phase), in the second phase a constant speed is maintained (cruising phase) and, finally, there is a braking phase until the convoy draws to a halt (deceleration phase). For the sake of simplicity, we refer to a motion diagram of the trapezium type (jerk value equals + ∞), represented in Fig. 14.
This condition of maximum performance corresponds to the minimum travel time and the maximum energy consumption. In this context, two different eco-driving strategies can be adopted, which consist, respectively, in:
-
1.
inserting, between the cruising and the braking phases, a further stage, which is the so-called coasting phase, during which the convoy moves by inertia (Fig. 15);
-
2.
reducing the maximum speed (Fig. 16).
The first strategy requires transmitting to the train information related to the switching points for the coasting phase, while the second is more straightforward to implement since it requires simply communicating a different speed limit. Therefore, the technological level of the rail system may affect the choice between these two approaches.
However, as shown by [255], the total travel time between two successive stops, in both cases, increases. Indeed, eco-driving policies are based on the adoption of speed profiles which are far from those at maximum performance and thus provide a longer travel time. This means that they are feasible only if there is an extra time availability on a given line service. This time is generally known as reserve time. In order to clarify this concept, it is worth analysing the different time rates concerning the timetable design phase. As stated above, this task involves the computation of running times between two stops, dwell times at stations for the boarding/alighting process, buffer times and layover times. Buffer times are generally set up during the design phase in order to address possible delays or, simply, eventual fluctuations which can occur during the service, given the stochasticity of the phenomenon being examined. Suffice it to think, for instance, that inevitably every train driver drives in his/her own way, but even the same train driver might drive in two different ways on two different days. Obviously, the lower the level of automation, the higher the relevance of the stochastic nature of the factors involved. The layover time is the time spent by the convoy at the terminus. The minimum layover time is represented by the inversion time and possibly by the time required for possible shunting. Moreover, there could be an additional time interval between when the convoy is physically ready to undertake the run in the opposite direction and when it can actually depart according to the timetable indications. However, in certain cases, the term layover time indicates only this further time rate, while the inversion time is computed in the cycle time. For the sake of completeness, also synchronisation times, for making transfer options available for passengers, can be taken into account. Hence, the above-mentioned extra time availability could involve running time reserve, dwell time reserve, buffer time, and time exceeding the layover time at the terminus, if any. These times are properly scheduled during the timetable design phase by increasing the minimum times required for the service. For example, as for travel time, the International Union of Railways (UIC) suggested increasing the minimum travel time by 3–8%. Obviously, the possibility of exploiting these extra times, for implementing such energy-saving strategies, is subject to the preservation of timetable stability and service quality. Therefore, the identification of an analytical framework for reliably quantifying the timetable rates involved in implementing energy-saving strategies, as well as defining optimisation models taking into account the trade-off between eco-driving profiles and passenger needs, proves fundamental [262]. Moreover, in a rail context, ES strategies are commonly implemented between two successive stops, while in a metro context the most suitable approach consists in examining the whole outward and return trip, given the fact that the service is frequency based, which means that the parameter to be respected is the headway between two successive convoys, rather than a timetable, generally unknown to users. Therefore, in the case of metro systems, the energy-saving strategies are generally implemented by considering arrival and departure times at the terminus, rather than at each station [255].
However, according to the literature, the above-mentioned techniques can be applied separately by addressing individually the design of energy-efficient driving profiles [263, 264] and the optimisation of operational times within the timetable [265, 266] or, more frequently, in an integrated framework. In this context, [267] proposed a train control approach, based on an optimisation model, which combines energy-efficient timetables and speed profiles. In particular, the procedure is characterised by a dynamic layout, since it provides a dynamic adjustment of the cycle time on the basis of travel demand changes, in order to minimise energy consumption. Moreover, a linear approximation method is implemented with the aim of dealing with a convex optimisation problem, whose resolution is performed by means of Kuhn–Tucker conditions. Moreover, [268] developed a nested optimisation framework in which, starting from the planned total running time, energy-efficient speed profiles are derived: the optimal cruising speed is defined by means of the outer loop of the Fibonacci algorithm [269, 270], while, in the inner loop, the bisection method computes, for the given cruising speed, the optimal switching points of the coasting phase. In addition, different distributions of running time supplements are tested and compared in terms of service punctuality and energy consumption. Furthermore, [271] devised a simulation-based optimisation procedure in which the simulation model provides the most energy-efficient driving profile, computing energy consumption Pareto curves for each stretch, and the optimisation tool allocates the total running reserve time available in the most efficient way among the different stretches. The proposed simulation technique deals with a manual driving mode and specifically allows a large variety of manual driving strategies to be performed by combining different sections of holding speed with different coasting windows. Finally, [272] enriched the common optimisation framework, which combined energy control strategies with a suitable design of operational times, by performing the estimation of dwell times at stations as a function of the number of passengers involved in the boarding/alighting process. By considering dwell time as a flow-dependent factor, rather than a fixed value, a more realistic computation of dwell time itself can clearly be carried out. Yet most importantly, dwell time margin, which plays a key role within the implementation of energy-saving strategies, can be derived with a high degree of accuracy. It is worth noting that both manual [273,274,275] and automatic [276,277,278] driving systems have been investigated in the literature.
As already touched upon, the most common methodologies for analysing such strategies are based on integrated simulation–optimisation techniques. In this context, [279] developed a multi-train simulator and incorporated it into an optimisation framework aimed at minimising the trade-off between energy consumption and the delay penalty. Additionally, both exhaustive and metaheuristic approaches are compared to optimise train operations such as enhanced brute force, ant colony optimisation and genetic algorithm. Moreover, [280] developed an offline eco-driving design model based on simulation tasks, whose aim is to define manual energy-efficient profiles, in terms of easily interpretable and executable commands for the driver, and implemented a genetic algorithm as an optimisation search technique. In particular, the proposed approach takes into account also passenger satisfaction and considers very detailed parameters such as the maximum number of commands, the minimum separation between commands and minimum speed of arrival at stations. Finally, [281, 282] merged a speed profile optimisation tool, based on a genetic algorithm as a subroutine, with a micro-simulation model which reproduces the interactions among infrastructure, signalling system, rolling stock and timetable. Further, the proposed methodology can be implemented for real-time rescheduling tasks by updating the timetable database information time after time. Other real-time approaches can be found in [283,284,285,286,287,288]. Nevertheless, also analytical approaches for modelling the implementation of ES strategies have been proposed [245, 289,290,291].
From the above-mentioned contributions, it appears that the majority of approaches proposed in the literature implement metaheuristic techniques, as will be shown more extensively in the following section.
As already mentioned, several works incorporate the energy-saving perspective in a multi-objective framework. Indeed, eco-driving speed profiles generally imply an increase in train running times and, therefore, in passenger travel times. For this reason, several authors focused on the trade-off between energy saving and passenger satisfaction [292,293,294,295,296,297,298]. In general, [299,300,301] analysed the relation between energy-efficient strategies and stability of the planned timetable, while [302] analysed also the utilisation rate of train capacity resulting from the implementation of energy-saving strategies. Finally, [76] compared the minimum-energy timetable with those obtained by taking into account also rolling stock and other operational costs.
6 Metaheuristic Optimisation Algorithms
The simplest technique conceptually for identifying the optimal solution in a combinatorial optimisation problem is based on enumeration methods which evaluate all candidate solutions (exhaustive approach or brute force search), or select a set of efficient solutions (implicit enumeration approach), and choose the one which optimises specific criteria expressed by an objective function, to be minimised or maximised according to the specific target pursued. Their computational cost depends on the number of candidate solutions, and they are therefore typically used in small-size problems. On the other hand, in the case of real-scale networks where, generally speaking, the number of feasible solutions to be analysed is very high and the objective functions are not convex, it is necessary to rely on suitable metaheuristic techniques which afford the possibility of finding near-to-optimal solutions within reasonable computation times. What follows, far from any claim to be exhaustive, provides some basic principles of the most frequently used metaheuristic algorithms in the field of rail transport, ranging from design problems to those of scheduling and routing.
Let us begin with the analysis of a series of algorithms belonging to the class of Local Search (LS) methods, whose common framework consists in starting from an initial feasible solution, trying iteratively to improve the current solution by means of more or less complex modifications (e.g. the exchange of elements belonging, or otherwise, to the solution) and drawing to a close when no further improvements can be made. Specifically, the following techniques will be described:
-
Neighbourhood search
-
Heuristic local search
-
Tabu search
-
Simulating annealing
The Neighbourhood Search Algorithm (NSA) is a heuristic algorithm for solving discrete optimisation problems. Each vector \( {\mathbf{y}} \) has an associated set of vectors \( N\left( {\mathbf{y}} \right) \subseteq S_{y} \), called neighbourhood of \( {\mathbf{y}} \), where the generic element \( {\mathbf{y}}' \in N\left( {\mathbf{y}} \right) \) is obtained from solution \( {\mathbf{y}} \) by an operation consisting in modifying only one component of vector \( {\mathbf{y}} \). This algorithm can be implemented according to two different approaches: the Steepest Descent Method (SDM), consisting in examining all elements of the neighbourhood and identifying the best solution (i.e. the solution with the best objective function value), and the Random Descent Method (RDM) consisting in randomly extracting a solution from the neighbourhood and comparing it with the current one. In particular, if the new solution is better than the current one, it then becomes the current solution; otherwise, another solution is randomly extracted until the neighbourhood runs out, since all solutions inside have been explored. This algorithm is relatively simple, but its importance lies in the fact that, in many cases, it is implemented as a subroutine in more complex techniques, such as the Heuristic Local Search (HLS) approach, set out below.
The HLS is made up of five phases which combine unconstrained with constrained optimisation steps. As shown by [303], it can be outlined in the following steps:
-
1.
Unconstrained mono-dimensional optimisation (UMDO);
-
2.
Unconstrained starting solution definition (USS);
-
3.
Unconstrained neighbourhood search optimisation (UNSO);
-
4.
Constrained starting solution definition (CSS);
-
5.
Constrained neighbourhood search optimisation (CNSO).
In the first phase, each component of vector \( {\mathbf{y}} \) is optimised, assuming the values of other components as constant. This phase may be addressed according to an exhaustive or a mono-dimensional NSA approach which is carried out by neglecting the constraints involved. The second phase entails determining the first starting solution by setting each component of vector \( {\mathbf{y}} \) at the optimal value obtained by the previous phase. In the third phase, the constraints involved are neglected as well and an NSA approach is performed. In this phase, it is possible to rely on both SDM and RDM techniques. The fourth phase analyses all the solutions generated in the previous phases, selecting the one which optimises the objective function and jointly satisfies constraints. Finally, the last phase performs the NSA by considering the constraints involved. In this case, the NSA technique is implemented by means of an SDM approach.
Similarly to the NSA, this algorithm, in many cases, is performed as a subroutine of more articulate metaheuristic procedures, as we will shortly see. Within this framework, [304, 305] developed metaheuristic procedures for solving the network design problem, respectively, in urban and regional contexts. Moreover, [306] proposed a multimodal approach for bus frequency design and then improved in the case of rail frequencies in [303]. In addition, [307] proposed a Variable Neighbourhood Search (VNS) algorithm for minimising the average passenger waiting time in the case of a partial line blockage and [86] implemented the same optimisation technique for addressing the problem of train scheduling and routing under disruption conditions. Moreover, [308] developed an Adaptive Large Neighbourhood Search (ALNS) algorithm as a resolution method for a complex problem which involves both network design and line planning issues. Finally, [309] addressed a frequency optimisation problem, in a cost-oriented perspective, by comparing a heuristic local search algorithm with three different optimisation techniques: a mixed-integer linear programming (MILP) model, a MIP-based iterative algorithm and a shortest-path-based algorithm. In particular, travel demand and competition among modes are taken into account and numerical results, both on test networks and over a real context, show that heuristic local search provides the best compromise between computational effort and solution quality.
Tabu Search (TS) algorithm is a deterministic method proposed by [310] and formalised in [311, 312]. Basically, it is a search approach whose peculiar feature, as the name itself implies, consists in making prohibited, namely tabu, the opposite of the ultimate move carried out in order to avoid going back to previously visited solutions. In particular, this method is based on the use of a memory structure, known as tabu list, which can adopt a short-, intermediate- or long-term memory criterion. However, in order to prevent the search getting trapped at a local minimum, an aspiration criterion, generally based on the objective function values, is set up. It states that the solution accessible by means of a forbidden move can be accepted if no improving moves are available outside the tabu list. Clearly, at each iteration, it is necessary to update the tabu list, generally by means of a FIFO approach: the entering move is the opposite of the last action carried out and the exiting move is the one which has remained on the list for longest. Obviously, there are many variations which enrich this basic version, for instance, considering the frequency with which certain types of solution have been analysed or introducing random elements. In this context, [114] addressed the problem of train conflict detection and resolution in real time by performing a TS optimisation and comparing its performance with those of other heuristic methods with different neighbourhood definitions. Further, [151] dealt with the same problem by implementing a TS technique in the real-time traffic management system ROMA which is based on the alternative graph model [79]. Moreover, in [151], similarly to the previously cited contribution, different neighbourhood structures are assessed and the results are compared with those obtained by [81, 313] which implemented, respectively, a branch-and-bound algorithm and a local search method. Additionally, [314] proposed a methodology for solving a particular vehicle routing problem which deals with vehicles with multiple compartments. The suggested procedure can be considered as an iterative local search method where the implemented local search technique is a TS algorithm. The starting point is a local minimum obtained by applying any local search. Then, at each iteration, the current local minimum is randomly perturbed and the TS is implemented in order to move on to another local minimum. The stopping criterion is based on the number of consecutive iterations which provide an improvement on the incumbent solution. Finally, [315] described an optimisation procedure for increasing the robustness around large railway stations, which may represent a bottleneck for the whole system, based on investigation of the interaction between the routing and scheduling of trains in the vicinity of the area in question. Therefore, a route choice module and a timetabling module are implemented and the timetabling problem is addressed by means of a TS algorithm, whose aim is to increase the smallest minimum time span between two trains so as to improve the reliability of railway operations. Moreover, a simulation module is introduced to evaluate the achieved performance in the examined region.
Conversely, Simulating Annealing (SA) is a stochastic metaheuristic method proposed as an optimisation technique for the first time by [316]. It is inspired by the process of annealing in metallurgy, i.e. a process by which a solid is first brought to the fluid state by means of heating to high temperatures and then brought back to a solid or crystalline form by gradually reducing the temperature. At a high temperature, as the atoms are in a highly disordered state there is a high level of energy in the system. In order to bring such atoms to a highly ordered (statistically) crystalline state, the temperature must be lowered. However, a swift reduction can cause flaws in the crystalline grid with consequent fissuring and fracturing of the grid itself (thermal stress). Annealing proceeds to a gradual cooling of the system, precisely in order to avoid such a phenomenon. Although, in general, the solid is inclined to turn into states with a lower level of energy, there is a slight chance that it increases its energy. This probability depends on the temperature and the variations of energy level associated with the transformation between the two states. In particular, it is regulated by the Metropolis criterion [317] according to which the probability of transformation increases with the increase in the temperature and the decrease in the energy gap. It is this very criterion which determines whether or not the solution being studied can become the new current solution. To be more precise, the analogy between the physical system and the optimisation method is based on the following correspondences: the states of the physical system correspond to the solutions of the problem; the position of the particles corresponds to the value of decisional variables; the energy level related to a certain state corresponds to the value of the objective function which is associated with a certain solution. While the temperature has no direct analogy, it represents a control parameter which implicitly defines the region of the state space being explored by the algorithm in a particular phase. At high temperatures, since bad solutions are easily accepted, the SA algorithm can cross almost all the state space. Following on, by lowering the value of the control parameter, the algorithm is confined to increasingly restricted regions of the state space. Therefore, it can be stated that, at high temperatures, the algorithm behaves more or less as a random search, while at low temperatures, the SA is similar to the steepest descent methods. The algorithm stops when the temperature needed to terminate the annealing process is reached, and hence there are no further possibilities for improvement in terms of objective function. This method has been implemented for solving many different transportation problems such as minimising the timetable cycle time [318], finding the optimum stop-skipping patterns in urban railway systems under uncertainty [319], solving conflicts in railway traffic under disruption conditions [101] and optimising energy consumption in train operations [320]. Moreover, the method was adopted in the case of a railcar fleet sizing problem [321], railway crew scheduling problem [322], track allocation problem at railway stations [323], train platform problem [324], train transfer problem [325], transit network optimisation problem [326] and location routing problem with simultaneous pickup and delivery [327].
Regarding the evolutionary techniques, Scatter Search (SS) methods [328,329,330] and the Genetic Algorithm (GA) [331, 332] are addressed below. Unlike the case of local search which is characterised by a neighbourhood-based approach, evolutionary procedures are population-based problem solvers and are inspired by principles of biological evolution.
As shown by [333], the basic framework of the SS can be described as the sum of the following five methods.
-
1.
Diversification Generation Method aimed at generating a collection of diverse trial solutions starting off from a seed solution. It is important that the generated trial set has a great variety of different solutions so as to cover different parts of the solution space.
-
2.
An Improvement Method represented by an algorithmic subroutine (e.g. NSA or HLSA) aimed at transforming a trial solution into one or more enhanced trial solutions. However, there is no guarantee of improvements. Hence, if no enhancing is possible, the improved solutions are considered to be the same which have been generated in the previous phase.
-
3.
A Reference Set Update Method aimed at carrying out a reference set by selecting all the enhanced solutions or only part of them, taking into account their quality, according to objective function values (good solutions), and their diversity in terms of distance from the best solution (scattered solutions). By including scattered solutions in the reference set, the algorithm is empowered to explore regions which would otherwise remain unexplored.
-
4.
A Subset Generation Method aimed at manipulating the reference set, in order to produce a subset of its solutions as a basis for creating combined solutions.
-
5.
A Solution Combination Method aimed at obtaining one or more combined solution vectors from the subset of solutions generated in the previous phase.
The output of the fifth phase is then improved, as described in the second step, so as to create a new reference set and so on. The procedure stops when the reference sets in two successive iterations are equal or when a pre-fixed number of iterations are reached.
Moving on to the GA, the evolutionary rationale is more evident, starting from the terminology adopted: each solution is indicated as a chromosome and each solution component as a gene. This method can be summarised in the following phases: initialisation, selection, reproduction and termination. The first phase is aimed at generating a set of initial solutions which represents the initial population. In the second phase, two fundamental tasks are carried out. First of all, for each chromosome, the objective function and the related fitness function are calculated and then, on the basis of these values, the parent selection is performed. It consists in extracting the best solutions from a population so as to enable them to successfully pass on their genes to the next generation. This step can make use of many different techniques such as roulette wheel selection, fitness proportionate selection, rank selection, random selection, tournament selection and stochastic universal sampling. Therefore, once two elements have been selected as parents, the reproduction phase is performed by means of two processes: crossover and mutation. The former produces offspring by combining two different solutions (i.e. parents), and the latter by producing random variations to a single parent. The best solution in the previous population is then enriched by the generated offspring, and the procedure carries on from the selection phase, until the maximum number of iterations is achieved or the optimal values of the objective function are the same in two successive iterations.
Contributions related to the implementation of such evolutionary techniques in transportation optimisation problems concern several issues: network design, routing and scheduling problems, timetabling and rescheduling tasks and energy consumption optimisation, as set out below. Specifically, [334] addressed different network design problems, related to urban and extra-urban (i.e. rural) contexts as well as road and transit transport modes, by implementing SS and comparing the results with those obtained by means of other metaheuristic techniques such as GA and LS methods. Moreover, [335] proposed a mixed network design problem with the aim of maximising the reserve capacity of the whole system and solved it by means of a hybrid SS method which incorporates the golden section search, while [336] implemented both SS and GA to tackle a stochastic travel time vehicle routing problem with simultaneous pickups and deliveries. Similarly, [337] proposed a genetic technique for solving a train routing problem combined with train schedules, taking into account average travel time, energy consumption and passenger satisfaction. In addition, [338] proposed an automated timetable design method, with a demand-oriented perspective, in which optimal departure times are computed by means of a GA. Likewise, [339] implemented a GA, based on a binary coding approach, for solving a timetable optimisation problem in an urban rail line, by considering the time variability of travel demand and a multiple origin-to-destination demand pattern. Furthermore, [96] addressed a train rescheduling problem by implementing a GA for minimising delays in conflict resolutions, together with an artificial neural network approach for simulating the decision-making process of dispatchers during the failure management phase. Finally, the GA is extensively used also for solving problems from an energy-saving perspective [340,341,342]. In this context, evolutionary techniques have also been combined with fuzzy logic [343, 344] as well as with artificial neural network approaches [263, 273].
Lastly, it is worth mentioning the Ant Colony Optimisation (ACO) method, belonging to the family of swarm intelligence methodologies, based on modelling the collective behaviours of social insects, such as colonies of ants and termites or flocks of birds, which adopt decentralized control and self-organisation. The ACO was introduced by [345,346,347] and its basic principles are described below. The idea was inspired by the exploitation of food resources by ants. These insects, albeit within the limits of cognitive capacities of the single ant, are able to collectively find the shortest path between a source of food and their nest. This is because they leave a trail of pheromones which attracts other ants. Specifically, when an ant is exploring an area in search of food, it leaves a trace. If it finds food, it returns and thus reinforces the trace. Hence, since pheromones are subject to evaporation, the shortest path will continuously be reinforced and will become the most attractive, while the longest path will end up by disappearing. As a result, all the ants will end up taking the shortest path (Fig. 17).
The mathematical formulation adopted by the algorithm to model this phenomenon is set out below. The probability \( P_{i,j}^{k} \left( t \right) \) with which the kth ant, at instant t, moves from state i to state j belonging to set \( N_{i}^{k} \) is expressed as follows:
with
where τi,j is the trail level of pheromone on link (i, j), i.e. a posteriori desirability of the move; ηi,j is the attractiveness of the move, i.e. a priori desirability of the move; α is the control parameter for the trail level (α \( \ge \) 0); β is the control parameter for the attractiveness (β \( \ge \) 1); and di,j is the distance between nodes i and j.
The trail level of pheromone on the link (i, j) is updated as follows:
with
where ρ is the pheromone evaporation coefficient (0 < ρ < 1), n is the number of ants, \( L_{k} \left( t \right) \) is the cost, generally in terms of path length, of kth ant at instant t; and \( Q \) is a constant.
Many different variants of the above method are presented in the literature: ant system, elitist ant system, rank-based ant system, MAX–MIN ant system and ant colony system. An extended overview of ant-based algorithms can be found in [348]. Several transportation issues are addressed by means of ACO techniques such as assignment problems, optimal control theory and energy-saving tasks, vehicle routing problems and rescheduling approaches. In detail, [349] integrated ACO into an MSA framework in order to solve a stochastic user equilibrium assignment and demonstrated the convergence of the proposed approach from a theoretical point of view by means of Blum’s theorem [350]; [351, 352] applied the so-called MAX–MIN ant system (MMAS) in order to optimise speed profiles of convoys between two stations, thus providing a support tool for implementing strategies aimed at reducing energy consumption; [353] formulated a distance-based train trajectory searching model for optimising train speed trajectory and found that the ACO algorithm was the best resolution method. Moreover, thanks to its efficiency in terms of calculation time, the ACO is often implemented for real-time management approaches. In this context, [354] proposed an ACO technique for implementing real-time energy-saving policies in the case of high-speed trains. In particular, the heuristic information parameter is designed according to the system status, in terms of delays, in order to adjust the trajectory planning procedure and allow the convoy to reduce its energy consumption by exploiting trip time redundancy. Likewise, [355] implemented ACO in order to deal with the real-time problem of routing trains in a railway, which consists in re-optimising the routing of convoys under disruption conditions by identifying the potential best routing alternatives for each train and deciding which to implement with the purpose of re-establishing ordinary conditions as soon as possible. In addition, [356] implemented ACO for the same problem (i.e. train routing selection problem) by comparing its application, and the relative issues, in the case of two different dimensions, namely the tactical level and the operational stage. Furthermore, ACO techniques were implemented to address a railway junction rescheduling problem when a delay occurs, both in dynamic and in static environments, respectively, by [357, 358]. The latter also provides an interesting comparison between ACO and other seven optimisation approaches, including GA, TS and SA. Obviously, the above-mentioned contributions cannot in any way be considered exhaustive with regard to the copious number of applications of these techniques in the field of rail service management. However, they may make the reader aware of the extensive potential of such metaheuristic approaches in the field of rail transport.
7 Discussion
The presented discussion is intended to give a comprehensive picture of the key factors involved in reliable modelling of rail services and related issues. The underlying idea is that, ideally, a fully demand-oriented transport system, optimised for a full match between demand and vehicle capacity, can provide the best service with the minimum energy expenditure [359]. For this reason, dispatching tasks were reviewed together with travel demand estimation and energy issues. Great attention was paid to rail simulation and optimisation models. Moreover, the importance of interactions between rail services and passenger flows was pointed out and the estimation and forecasting techniques for travel demand, proposed in the literature, were described. In particular, some crucial issues about the customisation of such techniques to the railway case were addressed. Furthermore, the environmental issues relative to rail systems and their impact on user satisfaction were discussed, with particular attention to energy-saving strategies involving the design of eco-driving profiles and the adjustment of operational times within the planned timetable. Finally, the most commonly used metaheuristic algorithms for solving dispatching and rescheduling problems were illustrated. Clearly, given the variety of the addressed topics, the overview provided is far from exhaustive for each specific matter investigated. Instead, it is aimed at providing a basic reference framework for allowing a well-rounded approach concerning such systems which are environmentally friendly, smart, safe and represent a key factor for a sustainable development of urban and metropolitan areas. Therefore, by properly combining the above-mentioned approaches, according to the specific context addressed and the target pursued, it is possible to obtain a robust modelling framework which is able to take into account constraints of real-world applications. However, many challenges still remain open. In the following, a discussion about such issues still under debate is provided, so as to give the reader an interpretation in a critical prospective of the resulting picture.
First, in the case of both simulation and optimisation approaches, multi-level methods for handling the different granularity of factors involved (such as speed control and the timetabling process) need to be further validated. Moreover, data-driven procedures for estimating passenger flows are increasingly taking hold, for instance, by means of e-ticketing and automatic collection fares. However, in the case of rail systems, it is fundamental to take into account some specific issues due to the intrinsic features of the context addressed. First of all, the flows of concern are related to the number of passengers, rather than the number of vehicles. This gives rise to the first issue to be faced, concerning the kind of passenger flows to be considered, such as flows at turnstiles, boarding or alighting flows, waiting flows and on-board flows. This results in a spatial problem related to ‘where’ to detect passengers. Should counting at turnstiles be selected, the measurement would be affected by an uncertainty concerning trip direction. Alternatively, data could be acquired from a single gate, but, in such circumstances, it might not be possible to know how many passengers are unable to board the train due to overcrowding. Conversely, such information could be obtained by carrying out counts on platforms. In addition to this, a temporal problem should be taken into account which lies in the difficulty of identifying a proper reference time interval, given the fact that rail services are scheduled services. It is this very discontinuity which makes counting at the turnstiles susceptible to a certain degree of uncertainty due to the gap between the time of registering the users’ passage and the moment they reach the platform. Therefore, it appears clear that it is necessary to design the data acquisition phase appropriately according to the target. As already stated, unlike the sample surveys which are complex and expensive, counts are cheaper to carry out and can be obtained automatically. The use of automatic devices makes the detection task easier and more efficient; however, it is not immune to incidents. First of all, it might happen that, because of a device failure, there could be effects on the entire measurement. A typical situation in which this could happen is if the target is to reconstruct the distribution of the passengers on the platform by carrying out counts at each gate. Indeed, in this case, if a detector at a single gate was damaged, this would also make the counts at the other gates useless, invalidating the measurement for the whole platform. Other issues to be taken into account are the presence of exchange points between two lines and, in some contexts, also the possibility of fare evasion. However, to the best of our knowledge, in the literature, there are no contributions which fully meet such requirements.
In addition, both infotainment tasks and calibration procedures for train motion models in an online framework represent an important challenge. This is related to the dynamic nature of the process involved. Indeed, when users receive some information, they may then change their behaviour, thus altering current conditions. This means that the utility and reliability of the same information change for the rest of passengers. Therefore, online passenger flow estimation methods need to be improved. As stated above, one of the main goals related to the inclusion of demand analysis in dispatching evaluations concerns demand-oriented optimisation of rail services. This may include an optimisation of fleet management which leads to changes in loads and train configurations which, in turn, entail different resistance values to be addressed and therefore a different calibration speed profile process. An accurate estimation of energy consumption for different trains in different conditions may also lead to an important turning point in regulating train path allocation on the part of infrastructure managers. Indeed, currently, the only factor considered concerns the degree of track utilisation. However, in the future, also a consumption criterion could be introduced.
Finally, the most challenging issues still concern the need to bridge the gap between theory and practice. In view of this, dispatching and rescheduling decision support systems should be able to automatically generate intervention plans by taking account of all relevant factors involved. Currently, we are still far from this. However, some noteworthy initiatives within this framework are listed below. Among others, there are some enterprises (e.g. Transport for London) which release their data in an open-source mode, so as to encourage practitioners to develop suitable techniques, and others (e.g. Swiss Federal Railways and NS Railway Operator in the Netherlands) which make their own-built APIs available. Another relevant initiative is the RAS problem solving competition established by the Netherlands Railways and ProRail so as to develop advanced techniques for obtaining accurate forecasts of train performance and delays [360]. Finally, it is worth mentioning two promising programmes. The first, namely ONTIME [361], is a European project established to provide a step change in railway capacity by reducing delays and improving traffic fluidity. Moreover, a joint initiative has been set by the Alstom Ferroviaria SpA company and Roma Tre University, with the aim of integrating the railway traffic controller ICONIS RM6 (Integrated CONtrol and Information System) with the optimisation system AGLIBRARY (Alternative Graph LIBRARY) [362]. However, a transition from test bed activities to pilot site stages is strongly desired.
References
Montella B, Gallo M, D’Acierno L (1999) Multimodal network design problems. WIT Trans Built Environ 91:405–414
Sewcyk B, Kettner M (2001) Network evaluation model NEMO. In: Proceedings of the 5th world congress on rail research—WCRR 2001, Cologne, Nov 2001
Middelkoop D, Bouwman M (2001) SIMONE: large scale train network simulations. In: Proceedings of the 2001 winter simulation conference, Piscataway, Dec 2001
TransCAD Transportation Planning Software. Web site: www.caliper.com/tcovu.htm. Accessed Oct 2018
Radtke A, Bendfeldt J (2001) Handling of railway operation problems with RailSys. In: Proceedings of the 5th world congress on rail research—WCRR 2001, Cologne, Nov 2001
Huerlimann D (2001) Objektorientierte Modellierung von Infrastrukturelementen und Betriebsvorgängen im Eisenbahnwesen. Ph.D. dissertation, University ETH Zürich
Nash A, Huerlimann D (2004) Railroad simulation using OpenTrack. WIT Trans Built Environ 74:45–54
Quaglietta E (2011) A Microscopic Simulation Model for supporting the design of railway systems: development and applications. Ph.D. dissertation, University of Naples Federico II
Quaglietta E, Punzo V (2013) Supporting the design of railway systems by means of a Sobol variance-based sensitivity analysis. Transp Res Part C 34:38–54
Butcher JC (1987) The numerical analysis of ordinary differential equations: Runge-Kutta and general linear methods. Wiley, New York
Kelton WD, Sadowski RP, Sturrock DT (2007) Simulation with arena, 4th edn. McGraw-Hill, New York
AnyLogic Simulation Software. Web site: www.anylogic.com. Accessed Oct 2018
Bilong W, Zuoyi L, Bin L (2013) The model and simulation of utilization optimization of railway passenger waiting compartment based on arena. In: Proceedings of 2013 international conference on computational and information sciences—ICCIS 2013, Hubai, June 2013
Yang Y, Li J, Zhao Q (2014) Study on passenger flow simulation in urban subway station based on any logic. J Softw 9(1):140–146
Logiciel Arena Rockwell (2011) Simulation de flux arena: petits trains distribution. www.youtube.com/watch?v=WEcsZctWrFw. Accessed Oct 2018
Quaglietta E, Punzo V, Montella B, Nardone R, Mazzocca N (2011) Towards a hybrid mesoscopic–microscopic railway simulation model. In: Proceedings of the 2nd IEEE international conference on models and technologies for intelligent transportation systems—IEEE MT-ITS 2011, Leuven, June 2011
Meyer JF, Movaghar A, Sanders WH (1985) Stochastic activity networks: structure, behavior and application. In: Proceedings of international workshop on timed petri nets, Turin, July 1985
Movaghar A, Meyer JF (1984) Performability modeling with stochastic activity networks. In: Proceedings of real-time systems symposium—RTSS 1984, Austin, Dec 1984
Sanders WH, Meyer JF (2001) Stochastic activity networks: formal definitions and concepts. In: Brinksma E, Hermanns H, Katoen JP (eds) Formal methods and performance analysis, vol 2090. Lecture notes in computer science. Springer, Berlin, pp 315–343
Cenelec (1999) EN50126: railway applications—specification and demonstration of reliability, availability, maintainability and safety (RAMS). https://standards.globalspec.com/std/10262901/cenelec-en-50126-1. Accessed July 2018
Marinov M, Viegas J (2011) A mesoscopic simulation modelling methodology for analyzing and evaluating freight train operations in a rail network. Simul Model Pract Theory 19:516–539
De Fabris S, Longo G, Medeossi G, Pesenti R (2014) Automatic generation of railway timetables based on a mesoscopic infrastructure model. J Rail Transp Plan Manag 4:2–13
Hansen IA, Pachl J (2008) Railway timetable and traffic: analysis–modelling–simulation. Eurail Press, Hamburg
Eickmann C, Kettner M, Sewcyk B (2003) Integrating microscopic and macroscopic models for railway network evaluation. In: Proceedings of the European transport conference—ETC 2003, Strasbourg, Oct 2003
Schlechte T, Borndörfer R, Erol B, Graffagnino T, Swarat E (2011) Micro–macro transformation of railway networks. J Rail Transp Plan Manag 1:38–48
Bešinović N, Roberti R, Quaglietta E, Cacchiani V, Toth P, Goverde RMP (2015) Micro–macro approach to robust timetabling. In: Proceedings of the 6th international conference on railway operations modelling and analysis—RailTokyo2015, Narashino, Mar 2015
Middelkoop AD (2010) Headway generation with ROBERTO. WIT Trans Built Environ 114:431–439
Kroon LG, Huisman D, Abbink E, Fioole PJ, Fischetti M, Maroti G, Schrijver A, Steenbeek A, Ybema R (2009) The new dutch timetable: the OR revolution. Interfaces 39(1):6–17
McGuire M, Linder D (1994) Train simulation on British rail. WIT Trans Built Environ 6:437–444
FALKO: design and validation of timetable (2007) Siemens Corporation. https://www.mobility.siemens.com/mobility/global/SiteCollectionDocuments/en/rail-solutions/rail-automation/operations-control-systems/falko-en.pdf. Accessed Oct 2018
RAILSIM X Software Suite. Systra Group. https://www.systracanada.com/en/services-expertise/tools/article/railsim-x-r. Accessed Oct 2018
Gröger T (2002) Simulation der Fahrplanerstellung auf der Basis eines hierarchischen Trassenmanagements und Nachweis der Stabilität der Betriebsabwicklung. Ph.D. dissertation, RWTH Aachen University
Shultze K (1985) Modell für die asynchrone Simulation des Betriebes. In Teilen des Eisenbahnnetzes. Ph.D. dissertation, RWTH Aachen University
D’Ariano A (2008) Improving real-time train dispatching: models, algorithms and applications. Ph.D. dissertation, Delft University of Technology
Corman F, Meng L (2015) A review of online dynamic models and algorithms for railway traffic management. IEEE Trans Intell Transp Syst 16(3):1274–1284
Liebchen C (2004) Symmetry for periodic railway timetables. Electron Notes Theor Comput Sci 92:34–51
Serafini P, Ukovich W (1989) A mathematical model for periodic event scheduling problems. SIAM J Discrete Math 2:550–581
Liebchen C (2008) The first optimized railway timetable in practice. Transp Sci 42(4):420–435
Liebchen C, Möhring RH (2002) A case study in periodic timetabling. Electron Notes Theor Comput Sci 66(6):1–14
Nachtigall K (1996) Periodic network optimization with different arc frequencies. Discrete Appl Math 69(1):1–17
Peeters L (2003) Cyclic railway timetable optimization. Ph.D. dissertation, Erasmus University Rotterdam
Kroon LG, Dekker R, Vromans MJCM (2007) Cyclic railway timetabling: a stochastic optimization approach. In: Geraets F, Kroon LG, Shoebel A, Wagner D, Zaroliagis CD (eds) Algorithmic methods for railway optimization, vol 4359. Lecture notes in computer science. Springer, Berlin, pp 41–66
Wong RCW, Leung JMY (2004) Timetable synchronization for mass transit railway. In: Proceedings of the 9th international conference on computer-aided scheduling of public transport—CASPT 2004, San Diego, Aug 2004
Wong RCW, Yuen TWY, Fung KW, Leung JMY (2008) Optimizing timetable synchronization for rail mass transit. Transp Sci 42(1):57–69
Guo X, Sun H, Wu J, Jin J, Zhou J, Gao Z (2017) Multiperiod–based timetable optimization for metro transit networks. Transp Res Part B 96:46–67
Bruglieri M, Maja R, Tolentino S (2017) Optimizing regular symmetric timetables: a method to reach the best modal split for railway. Optimisation online. http://www.optimization-online.org/DB_HTML/2017/05/5991.html. Accessed Oct 2018
Rausand M, Høyland A (2004) System reliability theory: models, statistical methods, and applications. Wiley, Hoboken
Ceder AA, Hassold S (2015) Applied analysis for improving rail-network operations. J Rail Transp Plan Manag 5:50–63
Cacchiani V, Toth P (2012) Nominal and robust train timetabling problems. Eur J Oper Res 219(3):727–737
Barter W (2004) Forecasting robustness of timetables. WIT Trans Built Environ 74:563–572
Carey M, Kwiecinski A (1995) Properties of expected costs and performance measures in stochastic models of scheduled transport. Eur J Oper Res 83:182–199
Landex A, Kaas AH, Hansen S (2006) Railway operation. Technical report no. 4, Centre for Traffic and Transport, Technical University of Denmark
Wendler E (2001) Quality management in the operation planning process by means of harmonized modelling. In: Proceedings of the 5th world congress on rail research—WCRR 2001, Cologne, Nov 2001
Goverde RMP (2005) punctuality of railway operations and timetable stability analysis. Ph.D. dissertation, Delft University of Technology
Braker JG (1993) Algorithms and applications in timed discrete event systems. Ph.D. dissertation, Delft University of Technology
Subiono (2000) On classes of min–max–plus systems and their applications. Ph.D. dissertation, Delft University of Technology
Bešinović N, Goverde RMP (2016) Improving robustness of railway timetables: a new two–stage approach. In: Proceedings of the 9th triennial symposium on transportation analysis—TRISTAN IX, Oranjestad, Aruba island, June 2016
Fischetti M, Salvagnin D, Zanette A (2009) Fast approaches to improve the robustness of a railway timetable. Transp Sci 43:321–335
Yan F, Goverde RMP (2017) Railway timetable optimization considering robustness and overtakings. In: Proceedings of the 5th IEEE international conference on models and technologies for intelligent transportation systems—IEEE MT-ITS 2017, Naples, June 2017
Sparing D, Goverde RMP (2017) A cycle time optimization model for generating stable periodic railway timetables. Transp Res Part B 98:198–223
Sparing D, Goverde RMP (2013) An optimization model for periodic timetable generation with dynamic frequencies. In: Proceedings of the 16th international IEEE conference on intelligent transportation systems—IEEE ITSC 2013, The Hague, Oct 2013
Goverde RMP (2007) Railway timetable stability analysis using max-plus system theory. Transp Res Part B 41(2):179–201
Khadilkar H (2017) Data-enabled stochastic modelling for evaluating schedule robustness of railway networks. Transp Sci 51(4):1161–1176
Liebchen C, Lübbecke M, Möhring RH, Stiller S (2009) The concept of recoverable robustness, linear programming recovery, and railway applications. In: Ahuja RK, Möhring RF, Zaroliagis CD (eds) Robust and online large-scale optimization, vol 5868. Lecture notes in computer science. Springer, Berlin, pp 1–27
Ciuffini F (2014) A method for evaluating the frequency effect on the overall travel time. Ingegneria Ferroviaria 69(10):803–821
Bešinović N, Goverde RMP, Quaglietta E, Roberti R (2016) An integrated micro-macro approach to robust railway timetabling. Transp Res Part B 87:14–32
Goverde RMP, Bešinovic N, Binder A, Cacchiani V, Quaglietta E, Roberti R, Toth P (2016) A three-level framework for performance-based railway timetabling. Transp Res Part C 67:62–83
Canca D, Zarzo A, Algaba E, Barrena E (2011) Confrontation of different objectives in the determination of train scheduling. Proc Soc Behav Sci 20:302–312
Brännlund U, Lindberg PO, Nõu A, Nilsson JE (1998) Railway timetabling using lagrangian relaxation. Transp Sci 32:358–369
Barrena E, Canca D, Coelho LC, Laporte G (2014) Exact formulations and algorithm for the train timetabling problem with dynamic demand. Comput Oper Res 44:66–74
Barrena E, Canca D, Coelho LC, Laporte G (2014) Single-line rail rapid transit timetabling under dynamic passenger demand. Transp Res Part B 70:134–150
Cai Z, Pang B, Diao H (2017) Optimization of urban rail transit timetable with dynamic demand. Railw Transp Econ 1:95–100
Shi J, Yang L, Yang J, Gao Z (2018) Service-oriented train timetabling with collaborative passenger flow control on an oversaturated metro line: an integer linear optimization approach. Transp Res Part B 110:26–59
Oliveira E, Smith BM (2000) A job-shop scheduling model for the single-track railway scheduling problem. Technical Report No. 21, School of Computing, University of Leeds
Oliveira E (2001) Solving single-track railway scheduling problem using constraint programming. Ph.D. dissertation, Delft University of Technology
Canca D (2017) Analysis of the energy-efficient design of railway rapid transit timetables. In: Proceedings of workshop on mathematical models of optimization for transportation planning, Seville, March 2017
Su S, Li X, Tang T, Gao Z (2013) A subway train timetable optimization approach based on energy-efficient operation strategy. IEEE Trans Intell Transp Syst 14(2):883–893
D’Acierno L, Botte M, Placido A, Caropreso C, Montella B (2017) Methodology for determining dwell times consistent with passenger flows in the case of metro services. Urb Rail Transit 3(2):73–89
Mascis A, Pacciarelli D (2002) Job shop scheduling with blocking and no-wait constraints. Eur J Oper Res 143(3):498–517
Roy B, Sussmann B (1964) Les Problèmes d’ordonnancement avec contraintes disjonctives. Note DS n.9 bis. SEMA, Montrouge
D’Ariano A, Corman F, Pacciarelli D, Pranzo M (2008) Reordering and local rerouting strategies to manage train traffic in real-time. Transp Sci 42(4):405–419
Quaglietta E, Corman F, Goverde RMP (2013) Impact of a stochastic and dynamic setting on the stability of railway dispatching solutions. In: Proceedings of the 16th international IEEE conference on intelligent transportation systems—IEEE ITSC 2013, The Hague, Oct 2016
D’Ariano A, Pranzo M (2009) An advanced real-time train dispatching system for minimizing the propagation of delays in a dispatching area under severe disturbances. Netw Spat Econ 9(1):63–84
Corman F, D’Ariano A, Pranzo M, Hansen IA (2011) Effectiveness of dynamic reordering and rerouting of trains in a complicated and densely occupied station area. Transp Plan Technol 34(4):341–362
Flamini M, Pacciarelli D (2008) Real time management of a metro rail terminus. Eur J Oper Res 189(3):746–761
Samà M, D’Ariano A, Corman F, Pacciarelli D (2017) A variable neighbourhood search for fast train scheduling and routing during disturbed railway traffic situations. Comput Oper Res 78(1):480–499
Corman F, D’Ariano A, Pacciarelli D, Pranzo M (2012) Bi-objective conflict detection and resolution in railway traffic management. Transp Res Part C 20(1):79–94
Corman F, D’Ariano A, Hansen IA, Pacciarelli D, Pranzo M (2011) Dispatching trains during seriously disrupted traffic situations. In: Proceedings of the IEEE international conference on networking, sensing and control—IEEE ICNSC 2011, Delft, April 2011
Mazzarello M, Ottaviani E (2007) A traffic management system for real-time traffic optimization in railways. Transp Res Part B 41(2):246–274
Xu P, Corman F, Peng Q, Luan X (2017) A Timetable rescheduling approach and transition phases for high speed railway traffic during disruptions. In: Proceedings of the 96th TRB annual meeting, Washington, Jan 2017
Xu P, Corman F, Peng Q, Luan X (2017) A train rescheduling model integrating speed management during disruptions of high-speed traffic under a quasi-moving block system. Transp Res Part B 104:638–666
Boccia M, Mannino C, Vasilyev I (2013) The dispatching problem on multitrack territories: heuristic approaches based on mixed integer linear programming. Networks 62(4):315–326
Hirai C, Kunimatsu T, Tomii N, Kondou S, Takaba M (2009) A train stop deployment planning algorithm using a petri-net-based modelling approach. Q Rep RTRI 50(1):8–13
Pellegrini P, Marlière G, Rodriguez J (2012) Real time railway traffic management modeling track-circuits. In: Delling D, Liberti L (eds) Proceedings of the 12th workshop on algorithmic approaches for transportation modelling, optimization, and systems—ATMOS 2012. OpenAccess series in informatics (OASIcs), vol 25. Schloss Dagstuhl–Leibniz–Zentrum für Informatik, Dagstuhl, pp 23–34
Acuna-Agost R, Michelon P, Feillet D, Gueye S (2011) A MIP-based local search method for the railway rescheduling problem. Networks 57(1):69–86
Dündar S, Şahin I (2013) Train re-scheduling with genetic algorithms and artificial neural networks for single-track railways. Transp Res Part C 27:1–15
Louwerse I, Huisman D (2014) Adjusting a railway timetable in case of partial or complete blockades. Eur J Oper Res 235(3):583–593
Min YH, Park MJ, Hong SP, Hong SH (2011) An appraisal of a column generation-based algorithm for centralized train-conflict resolution on a metropolitan railway network. Transp Res Part B 45:409–429
Narayanaswami S, Rangaraj N (2013) Modelling disruptions and resolving conflicts optimally in a railway schedule. Comput Ind Eng 64(1):469–481
Schöbel A (2007) Integer programming approaches for solving the delay management problem. In: Geraets F, Kroon LG, Shoebel A, Wagner D, Zaroliagis CD (eds) Robust and online large-scale optimization, vol 4359. Lecture notes in computer science. Springer, Berlin, pp 145–170
Törnquist J, Persson JA (2005) Train traffic deviation handling using Tabu Search and Simulated Annealings. In: Proceedings of the 38th Hawaii international conference on system sciences, Big Island, Jan 2005
Shakibayifar M, Sheikholeslami A, Corman F, Hassannayebi E (2017) An integrated rescheduling model for minimizing train delays in the case of line blockage. Oper Res Int J. https://doi.org/10.1007/s12351-017-0316-7
Meng L, Zhou X (2014) Simultaneous train rerouting and rescheduling on an N-track network: a model reformulation with network-based cumulative flow variables. Transp Res Part B 67:208–234
Zhan S, Kroon LG, Veelenturf LP, Wagenaar JC (2015) Real-time high-speed train rescheduling in case of a complete blockage. Transp Res Part B 78:182–201
Huo J, Wu J, Kang L, Wang B (2016) Railway timetable rescheduling based on priority and train order entropy. J Comput Civ Eng 30(5):04016006
Binder S, Maknoon Y, Bierlaire M (2017) The multi-objective railway timetable rescheduling problem. Transp Res Part C 78:78–94
Placido A, Cadarso L, D’Acierno L (2014) Benefits of a combined micro–macro approach for managing rail systems in case of disruptions. Transp Res Proc 3:195–204
Cadarso L, Marín A, Maróti G (2013) Recovery of disruptions in rapid transit networks. Transp Res Part E 53:15–33
D’Acierno L, Gallo M, Montella B, Placido A (2013) Evaluation of travel demand impacts in the case of rail system failure. Proc Soc Behav Sci 87:75–84
Dollevoet T, Corman F, D’Ariano A, Huisman D (2014) An iterative optimization framework for delay management and train scheduling. Flex Serv Manuf 26(4):490–515
Umiliacchi S, Nicholson G, Zhao N, Schmid F, Roberts C (2016) Delay management and energy consumption minimisation on a single-track railway. IET Intel Transp Syst 10(1):50–57
Jacobs J (2004) Reducing delays by means of computer-aided ‘on-the-spot’ rescheduling. WIT Trans Built Environ 74:603–612
D’Acierno L, Gallo M, Montella B, Placido A (2013) The definition of a model framework for managing rail systems in the case of breakdowns. In: Proceedings of 16th international IEEE conference on intelligent transport systems—IEEE ITSC 2013, The Hague, Oct 2013
Ho TK, Yeung TH (2001) Railway junction traffic control by heuristic methods. IEE Proc Electr Power Appl 148(1):77–84
Hansen IA (2006) State-of-the-art of railway operations research. WIT Trans Built Environ 88:565–577
Yuan J (2006) Stochastic modelling of train delays and delay propagation in stations. Ph.D. dissertation, Delft University of Technology
Conte C, Shöbel A (2007) Identifying dependencies among delays. In: Proceedings of the 2nd international seminar on railway operations modelling and analysis—RailHannover 2007, Hanover, March 2007
Wille A, Bühlmann P (2004) Tri-graph: a novel graphical model with application to genetic regulatory network. Technical report, University ETH Zürich
Wille A, Bühlmann P (2006) Low-order conditional independence graphs for inferring genetic networks. Stat Appl Genet Mol Biol 5(1):1–34
Kecman P, Corman F, Meng L (2015) Train delay evolution as a stochastic process. In: Proceedings of the 6th international conference on railway operations modelling and analysis—RailTokyo2015, Narashino, Mar 2015
Kecman P, Corman F, Peterson A, Joborn M (2015) Stochastic prediction of train delays in real-time using Bayesian networks. In: Proceedings of conference on advanced systems in public transport—CASPT 2015, Rotterdam, July 2015
Botte M, D’Acierno L, Montella B, Placido A (2015) A stochastic approach for assessing intervention strategies in the case of metro system failures. In: Proceedings of 2015 AEIT annual conference—AEIT 2015, Naples, Oct 2015
Davydov B, Chebotarev V, Kablukova K (2017) Stochastic model for the real-time train rescheduling. Int Transp Dev Integr 1:307–317
Li X, Shou B, Ralescu D (2014) Train rescheduling with stochastic recovery time: a new track-backup approach. IEEE Trans Syst Man Cybern Syst 44(9):1216–1233
Larsen R, Pranzo M, D’Ariano A, Corman F, Pacciarelly D (2014) Susceptibility of optimal train schedules to stochastic disturbances of process times. Flex Serv Manuf 26:466–489
D’Acierno L, Placido A, Botte M, Gallo M, Montella B (2016) Defining robust recovery solutions for preserving service quality during rail/metro systems failure. Int J Supply Oper Manag 3(3):1351–1372
Meng L, Zhou X (2011) Robust single–track train dispatching model under a dynamic and stochastic environment: a scenario–based rolling horizon approach. Transp Res Part B 45(7):1080–1102
Yin J, Tang T, Yang L, Gao Z, Ran B (2016) Energy-efficient metro train rescheduling with uncertain time-variant passenger demands: an approximate dynamic programming approach. Transp Res Part B 91:178–210
Kepaptsoglou K, Karlaftis MG (2010) A model for analyzing metro station platform conditions following a service disruption. In: Proceedings of the 13th international IEEE annual conference on intelligent transportation systems—IEEE ITSC 2010, Funchal, Sept 2010
D’Acierno L, Gallo M, Montella B, Placido A (2012) Analysis of the interaction between travel demand and rail capacity constraints. WIT Trans Built Environ 128:197–207
Xu W, Zhao P, Ning L (2017) A passenger-oriented model for train rescheduling on an urban rail transit line considering train capacity constraint. Math Probl Eng 2017:1010745
Zhu Y, Goverde RMP (2017) Dynamic passenger assignment during Disruptions in Railway Systems. In: Proceedings of the 5th IEEE international conference on models and technologies for intelligent transportation systems—IEEE MT-ITS 2017, Naples, June 2017
Gao Y, Kroon LG, Schmidt M, Yang L (2016) Rescheduling a metro line in an over-crowded situation after disruptions. Transp Res Part B 93:425–449
Canca D, Barrena E, Zarzo A, Ortega F, Algaba E (2012) Optimal train reallocation strategies under service disruptions. Proc Soc Behav Sci 54:402–413
Veelenturf LP, Kroon LG, Maróti G (2017) Passenger oriented railway disruption management by adapting timetables and rolling stock schedules. Transp Res Part C 80:133–147
Kroon LG, Maróti G, Nielsen LK (2015) Rescheduling of railway rolling stock with dynamic passenger flows. Transp Sci 49:165–184
Bizhan M, Mohammad K (2015) Real-time rescheduling for a subway network using model predictive controller by considering actual constraints. J Transp Eng 7(1):141–166
Gao Y, Yang L, Gao Z (2017) Real–time automatic rescheduling strategy for an urban rail line by integrating the information of fault handling. Transp Res Part C 81:246–267
Adenso-Díaz B, Oliva González M, González-Torre P (1999) On-line timetable re-scheduling in regional train services. Transp Res Part B 33(6):387–398
Botte M, Puca D, Montella B, D’Acierno L (2017) An innovative methodology for managing service disruptions on regional rail lines. In: Proceedings of the 10th international conference environmental engineering—ENVIRO 2017, Vilnius, April 2017
Wang L, Qin Y, Xu J, Jial L (2012) A fuzzy optimization model for high-speed railway timetable rescheduling. Discrete Dyn Nat Soc 2012:827073
Zhan S, Zhao J, Peng Q (2016) Real-time train rescheduling on high-speed railway under partial segment blockages. J China Railw Soc 38(10):1–13
Xu X, Li K, Yang L (2016) Rescheduling subway trains by a discrete event model considering service balance performance. Appl Math Model 40:1446–1466
Corman F, D’Ariano A, Hansen IA (2010) Disruption handling in large railway networks. WIT Trans Built Environ 114:629–640
D’Ariano A, Nucci D, Pacciarelli D, Rosti M (2016) Intelligent real–time traffic management system for complex and busy railway networks. In: Proceedings of the 11th world congress on railway research—WCRR 2016, Milan, Jan 2016
Kecman P, Corman F, D’Ariano A, Goverde RMP (2013) Rescheduling models for railway traffic management in large-scale networks. Public Transp 5(1):95–123
Corman F, D’Ariano A, Hansen IA, Pacciarelli D (2011) Optimal multi-class rescheduling of railway traffic. J Rail Transp Plan Manag 1:14–24
Cacchiani V, Huisman D, Kidd M, Kroon LG, Toth P, Veelenturf LP, Wagenaar J (2014) An overview of recovery models and algorithms for real-time railway rescheduling. Transp Res Part B 63:15–37
Dollevoet T, Huisman D, Schmidt M, Schöbel A (2012) Delay management with rerouting of passengers. Transp Sci 46(1):74–89
Bauer R, Schöbel A (2014) Rules of thumb: practical online-strategies for delay management. Public Transp 6(1):85–105
Corman F, D’Ariano A, Pacciarelli D, Pranzo M (2010) A tabu search algorithm for rerouting trains during rail operations. Transp Res Part B 44(1):175–192
Veelenturf LP, Kidd MP, Cacchiani V, Kroon LG, Toth P (2016) A railway timetable rescheduling approach for handling large scale disruptions. Transp Sci 50(3):841–862
Ghaemi N, Goverde RMP, Cats O (2016) Railway disruption timetable: Short-turnings in case of complete blockage. In: Proceedings of IEEE international conference on intelligent rail transportation—IEEE ICIRT 2016, Birmingham, Aug 2016
Binder S, Maknoon Y, Bierlaire M (2015) Passenger-oriented railway disposition timetables in case of severe disruptions. In: Proceedings of the 15th Swiss transport research conference—STRC 2015, Ascona, Apr 2015
Kanai S, Shiina K, Harada S, Tomii N (2011) An optimal delay management algorithm from passengers’ viewpoints considering the whole railway network. J Rail Transp Plan Manag 1:25–37
Kumazawa K, Hara K, Koseki T (2010) A novel train rescheduling algorithm for correcting disrupted train operations in a dense urban environment. WIT Trans Built Environ 103:565–574
Placido A, De Martinis V, Montella B, Gallo M, D’Acierno L (2014) Effects of travel demand levels on optimal strategies for metro system management in failure contexts. Proc Soc Behav Sci 111:819–828
Sato K, Tamura K, Tomii N (2013) A MIP–based timetable rescheduling formulation and algorithm minimizing further inconvenience to passengers. J Rail Transp Plan Manag 3:38–53
Tanaka S, Kumazawa K, Koseki T (2009) Passenger flow analysis for train rescheduling and its evaluation. In: Proceedings of international symposium on speed–up, safety and service technology for railway and maglev systems 2009—STECH’09, Niigata, June 2009
Toletti A, Weidman U (2016) Modelling customer inconvenience in train rescheduling. In: Proceedings of the 16th Swiss transport research conference—STRC 2016, Ascona, May 2016
D’Acierno L, Placido A, Botte M, Montella B (2016) A methodological approach for managing rail disruptions with different perspectives. Math Models Methods Appl Sci 10:80–86
Cadarso L, Maróti G, Marín A (2015) Smooth and controlled recovery planning of disruptions in rapid transit networks. IEEE Trans Intell Transp Syst 16(4):2192–2202
Corman F, Pacciarelli D, D’Ariano A, Samà M (2015) Rescheduling railway traffic taking into account minimization of passengers’ discomfort. In: Proceedings of international conference on computational logistics—ICCL 2015, Delft, Sept 2015
D’Ariano A, Pacciarelli D, Samà M, Corman F (2017) Microscopic delay management: minimizing train delays and passenger travel times during real-time railway traffic control. In: Proceedings of the 5th IEEE international conference on models and technologies for intelligent transportation systems—IEEE MT-ITS 2017, Naples, June 2017
Canca D, Zarzo A (2017) Design of energy-efficient timetables in two-way railway rapid transit lines. Transp Res Part B 102:142–161
Hazelton ML (2001) Inference for origin–destination matrices: estimation, prediction and reconstruction. Transp Res Part B 35:667–676
Brog W, Ampt E (1982) State of the art in the collection of travel behaviour data. Travel behaviour for the 1980’s. Special report 201, National Research Council, Washington
Ortuzar JdD, Willumsen LG (2011) Modelling transport, 4th edn. Wiley, Chichester
Smith MJ (1979) The existence, uniqueness and stability of traffic equilibria. Transp Res Part B 13(4):295–304
Ben-Akiva M, Lerman SR (1985) Discrete choice analysis: theory and application to travel demand. The MIT Press, Cambridge
Domencich TA, McFadden D (1975) Urban travel demand: a behavioural analysis. American Elsevier, New York
Horowitz JL (1981) Identification and diagnosis of specification errors in the multinomial logit model. Transp Res Part B 15(5):345–360
Manski CF, McFadden D (1981) Structural analysis of discrete data with econometric applications. The MIT Press, Cambridge
Novačko L, Šimunović L, Krasić D (2014) Estimation of origin–destination trip matrices for small cities. Promet Traffic Transp 26(5):419–428
Bera S, Rao KVK (2011) Estimation of origin–destination matrix from traffic counts: the state of the art. Eur Transp 49:3–23
Barcelò J, Montero L (2015) A robust framework for the estimation of dynamic OD trip matrices for reliable traffic management. Transp Res Proc 10:134–144
Cascetta E, Nguyen S (1988) A unified framework for estimating or updating origin/destination matrices from traffic counts. Transp Res Part B 22(6):437–455
Cipriani E, Nigro M, Fusco G, Colombaroni C (2014) Effectiveness of link and path information on simultaneous adjustment of dynamic O–D demand matrix. Eur Transp Res Rev 6(2):139–148
Cascetta E (2009) Transportation systems analysis: models and applications. Springer, New York
Ben-Akiva M, Morikawa T (1990) Estimation of switching models from revealed preference and stated intention. Transp Res Part A 24(6):485–495
Ortuzar JDD (1992) Stated Preference in travel demand modelling. In: Proceedings of the 6th world conference on transportation research—WCTR 1992, Lyon, July 1992
Cascetta E, Postorino MN (2001) Fixed point models for the estimation of O–D matrices using traffic counts on congested networks. Transp Sci 35(2):134–147
Caggiani L, Ottomanelli M, Sassanelli D (2013) A fixed point approach to origin–destination matrices estimation using uncertain data and fuzzy programming on congested networks. Transp Res Part C 28:130–141
Florian M, Chen Y (1995) A coordinate descendent method for the bi-level O–D matrix adjustment problem. Transp Oper Res 2:165–179
Yang H, Yagar S (1995) Traffic assignment and signal control in saturated road networks. Transp Res Part A 29(2):125–139
Lu CC, Zhou X, Zhang K (2013) Dynamic origin–destination demand flow estimation under congested traffic conditions. Transp Res Part C 34:16–37
Walpena J, Macinelli EM, Lotito PA (2015) A heuristic for the OD matrix adjustment problem in a congested transport network. Eur J Oper Res 242:807–819
Lo HP, Chan CP (2003) Simultaneous estimation of an origin–destination matrix and link choice proportions using traffic counts. Transp Res Part A 37(9):771–788
Wang Y, Ma X, Liu Y, Gong K, Henrickson KC, Xu M, Wang Y (2016) A two-stage algorithm for origin destination matrices estimation considering dynamic dispersion parameter for route choice. PLoS ONE 11(2):e0149827. https://doi.org/10.1371/journal.pone.0149827
Yang H, Meng Q, Bell MGH (2001) Simultaneous estimation of the origin destination matrices and travel-cost coefficient for congested networks in a stochastic user equilibrium. Transp Sci 35(2):107–123
Bell MGH (1983) The estimation of origin–destination matrix from traffic counts. Transp Sci 17(2):198–217
Maher M (1983) Inferences on trip matrices from observations on link volumes: a Bayesian statistical approach. Transp Res Part B 17(6):435–447
Cascetta E (1984) Estimation of trip matrices from traffic counts and survey data: a generalized least squares estimator. Transp Res Part B 18(4–5):289–299
Cascetta E, Inaudi D, Marquis G (1993) Dynamic estimators of origin–destination matrices using traffic counts. Transp Sci 27(4):363–373
Ashok K, Ben–Akiva M (1993) Dynamic origin–destination matrix estimation and prediction for real time-traffic management systems. In: Proceedings of the 12th international symposium on the theory of traffic flow and transportation, Berkeley, July 1993
Okutani I, Stephanedes Y (1984) Dynamic prediction of traffic volume through Kalman filtering theory. Transp Res Part B 18:1–11
Bierlaire M, Crittin F (2004) An efficient algorithm for real-time estimation and prediction of dynamic OD tables. Oper Res 52(1):116–127
Cascetta E, Russo F (1997) Calibrating aggregate travel demand models with traffic counts: estimators and statistical performance. Transportation 24:271–293
Toledo T, Koutsopoulos HN, Davol A, Ben-Akiva M, Burghout W, Andreasson I, Johansson T, Lundin C (2003) Calibration and validation of microscopic traffic simulation tools: Stockholm case study. Transp Res Rec 1831:65–75
Cremer M, Keller H (1981) Dynamic identification of O–D flows from traffic counts at complex intersections. In: Proceedings of the 8th international symposium on transportation and traffic theory—ISTTT 1981, Toronto, June 1981
Cremer M, Keller H (1984) A systems dynamics approach to the estimation of entry and exit O–D flows. In: Proceedings of the 9th international symposium on transportation and traffic theory—ISTTT 1984, Delft, June 1984
Cremer M, Keller H (1987) A new class of dynamic methods for the identification of origin–destination flows. Transp Res Part B 21:117–132
Nihan NL, Davis GA (1987) Recursive estimation of origin–destination matrices from input–output counts. Transp Res Part B 21:149–163
Nihan NL, Davis GA (1989) Application of prediction-error minimization and maximum likelihood to estimate intersection O–D matrices from traffic counts. Transp Sci 23:77–90
Appiah J, Rilett L (2010) Joint estimation of dynamic origin–destination matrices and calibration of microsimulation models using aggregate intersection turn count data. In: Proceedings of the 89th TRB annual meeting, Washington, January 2010
Kattan L, Abdulhai B (2011) Comparative analysis of evolutionary, local search, and hybrid approaches to O/D traffic estimation. J Transp Eng 137(1):46–56
Kattan L, Abdulhai B (2012) Sensitivity analysis of an evolutionary-based time-dependent origin/destination estimation framework. IEEE Trans Intell Transp Syst 13(2):1442–1453
Kim H, Baek S, Lim Y (2001) O–D matrices estimation using genetic algorithms from traffic counts. Transp Res Rec 1771:156–163
Park B, Zhu K (2007) Time-dependent origin–destination estimation: genetic algorithm-based optimization with updated assignment matrix. KSCE J Civ Eng 11(4):199–207
Tsekeris T, Dimitriou L, Stathopoulos A (2007) Simultaneous origin–destination matrix estimation in dynamic traffic networks with Evolutionary Computing. In: Giacobini M (ed) Applications of evolutionary computing, vol 4448. Lecture notes in computer science. Springer, Berlin, pp 668–677
Stathopoulos A, Tsekeris T (2004) Hybrid meta-heuristic algorithm for the simultaneous optimization of the O–D trip matrix estimation. Comput Aided Civ Infrastruct Eng 19(6):421–435
Caggiani L, Dell’Orco M, Marinelli M, Ottomanelli M (2012) A metaheuristic dynamic traffic assignment model for O–D matrix estimation using aggregate data. Proc Soc Behav Sci 54:685–695
D’Acierno L, Cartenì A, Montella B (2009) Estimation of urban traffic conditions using an Automatic Vehicle Location(AVL) System. Eur J Oper Res 196:719–736
De Luca G, Gallo M (2017) Artificial Neural Networks for forecasting user flows in transportation networks: literature review, limits, potentialities and open challenges. In: Proceedings of the 5th IEEE international conference on models and technologies for intelligent transportation systems—IEEE MT-ITS 2017, Naples, June 2017
Huang S, Sadek AW, Guo L (2013) A computational-based approach to estimating travel demand in large-scale microscopic traffic simulation models. J Comput Civ Eng 27(1):78–86
Kattan L, Abdulhai B (2006) Non iterative approach to dynamic traffic origin/destination estimation using parallel evolutionary algorithms. Transp Res Rec 1964:201–210
Balakrishna R, Ben-Akiva M, Koutsopoulos HN (2008) Time-dependent origin–destination estimation without assignment matrices. In: Chung E, Dumont AG (eds) Transport simulation: beyond traditional approaches. EPFL Press, Lausanne, pp 201–213
Cipriani E, Florian M, Mahut M, Nigro M (2011) A gradient approximation approach for adjusting temporal origin–destination matrices. Transp Res Part C 19:270–282
Spall JC (1992) Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Trans Automat Control 37(3):332–341
Spall JC (1998) Implementation of the simultaneous perturbation algorithm for stochastic optimization. IEEE Trans Aerosp Electron Syst 34:817–823
Lu L, Xu Y, Antoniou C, Ben-Akiva M (2015) An enhanced SPSA algorithm for the calibration of Dynamic Traffic Assignment models. Transp Res Part C 51:149–166
Antoniou C, Azevedo CL, Lu L, Pereira F, Ben-Akiva M (2015) W-SPSA in practice: approximation of weight matrices and calibration of traffic simulation models. Transp Res Part C 59:129–146
Tympakianaki A, Koutsopoulos HN, Jenelius E (2015) c-SPSA: cluster-wise simultaneous perturbation stochastic approximation algorithm and its application to dynamic origin–destination matrix estimation. Transp Res Part C 55:231–245
Toledo T, Kolechkina T (2013) Estimation of dynamic origin–destination matrices using linear assignment matrix approximations. IEEE Trans Intell Transp Syst 14(2):618–626
Cascetta E, Papola A, Marzano V, Simonelli F, Vitiello I (2013) Quasi-dynamic estimation of o–d flows from traffic counts: formulation, statistical validation and performance analysis on real data. Transp Res Part B 55:171–187
Bao X, Li H, Qin L, Xu D, Ran B, Rong J (2016) Sensor location problem optimization for traffic network with different spatial distributions of traffic information. Sensors 16(11):1790
Chung IH (2001) An optimum sampling framework for estimating trip matrices from day-to-day traffic counts. Ph.D. dissertation, University of Leeds
Ehlert A, Bell MGH, Grosso S (2006) The optimization of traffic count locations in road networks. Transp Res Part B 40:460–479
Fei X, Eisenman SM, Mahmassani HS (2007) Sensor coverage and location for real-time prediction in large-scale networks. In: Proceedings of the 86th TRB annual meeting, Washington, Jan 2007
Shao M, Sun L, Shao X (2016) Sensor location problem for network traffic flow derivation based on turning ratios at intersection. Math Probl Eng 2016:9012724
Simonelli F, Marzano V, Papola A, Vitiello I (2012) A network sensor location procedure accounting for o–d matrix estimate variability. Transp Res Part B 46:1624–1638
Yang H, Zhou J (1998) Optimal traffic counting locations for origin–destination matrix estimation. Transp Res Part B 32(2):109–126
Moreira-Matias L, Gama J, Ferreira M, Mendes-Moreira J, Damas L (2016) Time-evolving O–D matrix estimation using high-speed GPS data streams. Expert Syst Appl 44:275–288
Savrasovs M, Pticina I (2017) Methodology of OD matrix estimation based on video recordings and traffic counts. Proc Eng 178:289–297
Tolouei R, Psarras S, Prince R (2016) Origin–destination trip matrix development: conventional methods vs. use of mobile phone data. In: Proceedings of the European transport conference—ETC 2016, Barcelona, Oct 2016
Sun Y, Shi J, Schonfeld PM (2016) Identifying passenger flow characteristics and evaluating travel time reliability by visualizing AFC data: a case study of Shanghai Metro. Public Transp 8(3):341–363
Kusakabe T, Asakura Y (2014) Behavioural data mining of transit smart card data: a data fusion approach. Transp Res Part C 46:179–191
Tao S, Corcoran J, Mateo-Babiano I, Rohde D (2014) Exploring bus rapid transit passenger travel behaviour using big data. Appl Geogr 53:90–104
Sun Y, Schonfeld PM (2015) Schedule-based rail transit path choice estimation using automatic fare collection data. J Transp Eng 142(1):04015037
Nassir N, Hickman M, Ma ZL (2015) Activity detection and transfer identification for public transit fare card data. Transportation 42(4):683–705
Gavriilidou A, Cats O, Leffler D, Corman F, Hoogendoorn SP (2017) Real–time transfer synchronization of public transport services 1 using passenger data. In: Proceedings of the 96th TRB annual meeting, Washington, Jan 2017
Nagy V (2016) Theoretical method for building OD matrix from AFC data. Transp Res Proc 14:802–1808
Tavassoli A, Mesbah M, Hickman M (2017) Quantifying error in transit assignment using smart card data in a large-scale multimodal transit network. In: Proceedings of the 96th TRB annual meeting, Washington, Jan 2017
Zhao J, Rahbee A (2007) Estimating a rail passenger trip origin–destination matrix using automatic data collection systems. Comput Aided Civ Infrastruct Eng 22:376–387
Albrecht A, Howlett P, Pudney P, Vu X (2013) Energy-efficient train control: from local convexity to global optimization and uniqueness. Automatica 49(10):3072–3078
Miyatake M, Ko H (2010) Optimization of train speed profile for minimum energy consumption. IEEJ Trans Electr Electron Eng 5:263–269
Miyatake M, Matsuda K (2009) Energy saving speed and charge/discharge control of a railway vehicle with on-board energy storage by means of an optimization model. IEEJ Trans Electr Electron Eng 4:771–778
Steiner R, Klohr M, Pagiela S (2007) Energy storage system with UltraCaps on Board of Railway Vehicles. In: Proceedings of European conference on power electronics and applications, Aalborg, Sept 2007
Romo L, Turner D, Ng LSB (2005) Cutting traction power costs with wayside energy storage systems in rail transit systems. In: Proceedings of joint rail conference—JRC2005, Pueblo, Mar 2005
Teymourfar R, Asaei B, Iman-Eini H, Nejati fard R (2012) Stationary super-capacitor energy storage system to save regenerative braking energy in a metro line. Energy Convers Manag 56:206–214
Kim KM, Kim KT, Han MS (2011) A model and approaches for synchronized energy saving in timetabling. In: Proceedings of the 9th world congress on railway research—WCRR 2011, Lille, May 2011
Nasri A, Fekri Moghadam M, Mokhtari H (2010) Timetable optimization for maximum usage of regenerative energy of braking in electrical railway systems. In: Proceedings of the international symposium on power electronics, electrical drives, automation and motion—SPEEDAM 2010, Pisa, June 2010
Ramos A, Pena M, Fernndez–Cardador A, Cucala AP (2007) Mathematical programming approach to underground timetabling problem for maximizing time synchronization. In: Proceedings of the international conference on industrial engineering and industrial management, Madrid, Dec 2007
Yang X, Li X, Gao Z, Wang H, Tang T (2013) A cooperative scheduling model for timetable optimization in subway systems. IEEE Trans Intell Transp Syst 14(1):438–447
D’Acierno L, Botte M, Gallo M, Montella B (2018) Defining reserve times for metro systems: an analytical approach. J Adv Transp 2018, art. no. 5983250
Wong KK, Ho TK (2007) Dwell-time and run-time control for DC mass rapid transit railways. IET Electr Power App 1(6):956–966
Cornic D (2010) Efficient recovery of braking energy through a reversible dc substation. In: Proceedings of electrical systems for aircraft, railway and ship propulsion—ESARS 2010, Bologna, Oct 2010
Ibaiondo H, Romo A (2010) Kinetic energy recovery on railway systems with feedback to the grid. In: Proceedings of the 14th international power electronics and motion control conference—EPE-PEMC 2010, Ohrid, Sept 2010
Tian Z, Weston P, Zhao N, Hillmansen S, Roberts C, Chen L (2017) System energy optimisation strategies for metros with regeneration. Transp Res Part C 75:120–135
Ghavihaa N, Campilloa J, Bohlinb M, Dahlquista E (2017) Review of application of energy storage devices in railway transportation. Energy Procedia 105:4561–4568
Gonzalez-Gil A, Palacin R, Batty P (2013) Sustainable urban rail systems: strategies and technologies for optimal management of regenerative braking energy. Energy Convers Manag 75:374–388
D’Acierno L, Botte M, Montella B (2017) An analytical approach for determining reserve times on metro systems. In: Proceedings of the 17th IEEE international conference on environment and electrical engineering—IEEE EEEIC 2017 and 1st industrial and commercial power systems Europe—I&CPS 2017, Milano, June 2017
Chuang HJ, Chen CS, Lin CH, Hsieh CH, Ho CY (2008) Design of optimal coasting speed for saving social cost in mass rapid transit systems. In: Proceedings of 3rd international conference on deregulation and restructuring and power technologies—DRPT 2008, Nianjing, Apr 2008
Yang L, Li K, Gao Z, Li X (2012) Optimizing trains movement on a railway network. Omega 40:619–633
Albrecht T, Oettich S (2002) A new integrated approach to dynamic schedule synchronization and energy-saving train control. WIT Trans Built Environ 61:847–856
Lancien D, Fontaine M (1981) Computing train schedules to save energy. Revue General des Chemins de Fer 100:679–692
Li X, Lo HK (2014) Energy minimization in dynamic train scheduling and control for metro rail operations. Transp Res Part B 70:269–284
Scheepmaker GM, Goverde RMP (2015) The interplay between energy-efficient train control and scheduled running time supplements. J Rail Transp Plan Manag 5:225–239
Mathews JH, Fink KD (2004) Numerical methods using MATLAB. Pearson Prentice Hall, Upper Saddle River
Siegler LE (1987) Leonardo Pisano Fibonacci, The book of squares, an annotated translation into modern English. Academic Press Incorporated, Orlando
Sicre C, Cucala P, Fernández A, Jiménez JA, Ribera I, Serrano A (2010) A method to optimise train energy consumption combining manual energy efficient driving and scheduling. WIT Trans Built Environ 114:549–560
Feng J, Li X, Liu H, Gao X, Mao B (2017) Optimizing the energy-efficient metro train timetable and control strategy in off-peak hour with uncertain passenger demands. Energies 10(4):436
Acikbas S, Soylemez MT (2008) Coasting point optimisation for mass rail transit lines using artificial neural networks and genetic algorithms. IET Electr Power Appl 2(3):172–182
Lukaszewicz P (2000) Driving techniques and strategies for freight trains. WIT Trans Built Environ 50:1065–1073
Wong KK, Ho TK (2004) Coast control for mass rapid transit railways with searching methods. IEE Proc Electr Power Appl 151(3):365–376
Carreno WC (2017) Efficient driving of CBTC ATO operated trains. Ph.D. Dissertation, Universidad Pontificia Comillas, Madrid
De Cuadra F, Fernandez A, de Juan J, Herrero MA (1996) Energy-saving automatic optimisation of train speed commands using direct search techniques. WIT Trans Built Environ 20:337–346
Domínguez M, Fernández-Cardador A, Cucala AP, Pecharromán RR (2012) Energy savings in metropolitan railway substations through regenerative energy recovery and optimal design of ATO speed profiles. IEEE Trans Autom Sci Eng 9:496–504
Zhao N, Roberts C, Hillmansen S, Nicholson G (2015) A multiple train trajectory optimization to minimize energy consumption and delay. IEEE Trans Intell Transp Syst 16(5):2363–2372
Sicre C, Cucala AP, Fernandez A, Lukaszewicz P (2012) Modeling and optimizing energy-efficient manual driving on high-speed lines. IEEJ Trans Electr Electron Eng 7:633–640
De Martinis V, Weidmann UA, Gallo M (2014) Towards a simulation-based framework for evaluating energy-efficient solutions in train operation. WIT Trans Built Environ 135:721–732
De Martinis V, Weidmann UA (2015) Definition of energy-efficient speed profiles within rail traffic by means of supply design models. Res Transp Econ 54:41–50
Corman F, D’Ariano A, Pacciarelli D, Pranzo M (2009) Evaluation of green wave policy in real-time railway traffic management. Transp Res Part C 17(6):607–616
Chang SC, Chung YC (2005) From timetabling to train regulation—a new train operation model. Inf Softw Technol 47:575–585
D’Ariano A, Albrecht T (2006) Running time re-optimization during real-time timetable perturbations. WIT Trans Built Environ 88:531–540
Sheu JW, Lin WS (2011) Automatic train regulation with energy saving using dual heuristic programming. IET Electr Syst Transp 1(2):80–89
Huang H, Li K, Schonfeld P (2018) Real-time energy-saving metro train rescheduling with primary delay identification. PLoS ONE 13(2):e0192792. https://doi.org/10.1371/journal.pone.0192792
Zhang H, Li S, Yang L (2018) Real-time optimal train regulation design for metro lines with energy-saving. Comput Ind Eng. https://doi.org/10.1016/j.cie.2018.02.019 Article in press
Howlett P, Pudney P, Vu X (2009) Local energy minimization in optimal train control. Automatica 45(11):2692–2698
Khmelnitsky E (2000) On an optimal control problem of train operation. IEEE Trans Autom Control 45(7):1257–1266
Liu R, Golovitcher I (2003) Energy-efficient operation of rail vehicles. Transp Res Part A 37(10):917–932
Chevrier R, Pellegrini P, Rodriguez J (2013) Energy saving in railway timetabling: a bi-objective evolutionary approach for computing alternative running times. Transp Res Part C 37:20–41
Corapi G, De Martinis V, Placido A, De Luca G (2014) Impacts of energy saving strategies (ESSs) on rail services and related effects on travel demand. WIT Trans Built Environ 135:709–720
Yin J, Yang L, Tang T, Gao Z, Ran B (2017) Dynamic passenger demand oriented metro train scheduling with energy-efficiency and waiting time minimization: mixed-integer linear programming approaches. Transp Res Part B 97:182–213
Ghoseiri K, Szidarovszky F, Asgharpour MJ (2004) A multi-objective train scheduling model and solution. Transp Res Part B 38:927–952
Xu X, Li K, Li X (2016) A multi-objective subway timetable optimization approach with minimum passenger time and energy consumption. J Adv Transp 50:69–95
D’Acierno L, Botte M (2018) Passengers’ satisfaction in the case of energy-saving strategies: a rail system application. In: Proceedings of the 18th IEEE international conference on environment and electrical engineering—IEEE EEEIC 2018 and 2nd industrial and commercial power systems Europe—I&CPS 2018, Palermo, June 2018
D’Acierno L, Botte M, Gallo M, Montella B (2018) Defining reserve times for metro systems: an analytical approach. J Adv Transp 2018, ID 5983250
Cucala AP, Fernández A, Sicre C, Domínguez M (2012) Fuzzy optimal schedule of high speed train operation to minimize energy consumption with uncertain delays and driver’s behavioral response. Eng Appl Artif Intell 25(8):1548–1557
Toletti A, De Martinis V, Weidmann U (2016) Energy savings in mixed rail traffic rescheduling: an RCG approach. In: Proceedings of the 19th IEEE international conference on intelligent transportation systems—IEEE ITSC 2016, Rio de Janeiro, Nov 2016
Tonosaki Y, Koizumi Y, Tajima M, Miyoshi M, Takeba T, Miyatake M (2016) Punctual train operation with energy-saving driving advisory system in dense traffic railway. In: Proceedings of the IEEE international conference on intelligent rail transportation—IEEE ICIRT 2016, Birmingham, Aug 2016
Feng X, Wang Q, Liu Y, Xu B, Liu H, Sun Q (2014) Ensuring a reasonable passenger capacity utilization rate of a train for its sustainably efficient transport. J Appl Res Technol 12(2):279–288
Gallo M, Montella B, D’Acierno L (2011) The transit network design problem with elastic demand and internalisation of external costs: an application to rail frequency optimisation. Transp Res Part C 19(6):1276–1305
Gallo M, D’Acierno L, Montella B (2010) A meta-heuristic approach for solving the urban network design problem. Eur J Oper Res 201:144–157
Gallo M, D’Acierno L, Montella B (2012) A meta-heuristic algorithm for solving the road network design problem in regional contexts. Proc Soc Behav Sci 54:84–95
Gallo M, D’Acierno L, Montella B (2011) A multimodal approach to bus frequency design. WIT Trans Built Environ 116:193–204
Hassannayebi E, Sajedinejad A, Mardani S (2016) Disruption management in urban rail transit system: a simulation based optimization approach. Handbook of research on emerging innovations in rail transportation engineering. IgI-Global, Hershey, pp 420–450
Canca D, De-Los-Santos A, Mesa JA, Laporte G (2017) The railway network design, line planning and capacity problem: an adaptive large neighbourhood search metaheuristic. In: Żak J, Hadas Y, Rossi R (eds) advances in intelligent systems and computing, vol 572. Springer, Cham, pp 198–219
De-Los-Santos A, Laporte G, Mesa JM, Perea F (2017) The railway line frequency and size setting problem. Public Transp 9:33–53
Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13:533–549
Glover F (1989) Tabu search, part I. ORSA J Comput 1(3):190–206
Glover F (1990) Tabu search, part II. ORSA J Comput 2(1):4–32
D’Ariano A, Pacciarelli D, Pranzo M (2007) A branch and bound algorithm for scheduling trains in a railway network. Eur J Oper Res 183(2):643–657
Silvestrin PV, Ritt M (2017) An iterated tabu search for the multi-compartment vehicle routing problem. Comput Oper Res 81:192–202
Dewildea T, Selsa P, Cattryssea D, Vansteenwegena P (2014) Improving the robustness in railway station areas. Eur J Oper Res 235:276–286
Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680
Metropolis N, Rosenbluth A, Rosenbluth M, Teller A, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21:1087–1092
Burkolter DM (2005) Capacity of railways in station areas using petri nets. Ph.D. dissertation, Swiss Federal Institute of Technology, Zurich
Jamili A, Pourseyed Aghaee M (2015) Robust stop-skipping patterns in urban railway operations under traffic alteration situation. Transp Res Part C 61:63–74
Kim K, Chien SIJ (2011) Optimal train operation for minimum energy consumption considering track alignment, speed limit, and schedule adherence. J Transp Eng 137(9):665–674
Sayarshad HR, Ghoseiri K (2009) A simulated annealing approach for the multi-periodic rail-car fleet sizing problem. Comput Oper Res 36:1789–1799
Hanafi R, Kozan E (2014) A hybrid constructive heuristic and simulated annealing for railway crew scheduling. Comput Ind Eng 70:11–19
Wu J, Kang L, Sun H, Jia X (2013) Track allocation optimization in railway station: mean-variance model and case study. J Transp Eng 139(5):540–547
Kang L, Wu J, Sun H (2012) Using simulated annealing in a bottleneck optimization model at railway stations. J Transp Eng 138(11):1396–1402
Kang L, Zhu X (2016) A simulated annealing algorithm for first train transfer problem in urban railway networks. Appl Math Model 40:419–435
Zhao F, Zeng XG (2006) Simulated annealing genetic algorithm for transit network optimization. J Comput Civ Eng 20(1):57–68
Yu VF, Lin SW (2014) Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery. Appl Soft Comput 24:284–290
Goldberg DE (1989) Genetic algorithms in search. Optimization and machine learning. Kluwer Academic Publishers, Boston
Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor
Srinivas M, Patnaik LM (1994) Genetic algorithms: a survey. Computer 27(6):17–26
Glover F, Laguna M, Martì R (2003) Scatter search. In: Ghosh A, Tsutsui S (eds) Advances in evolutionary computation: theory and applications. Springer, New York, pp 519–537
Laguna M (2002) Scatter search. In: Pardalos PM, Resende MGC (eds) Handbook of applied optimization. University Press, Oxford, pp 183–193
Martì R, Laguna M, Glover F (2003) Principles of scatter search. Eur J Oper Res 169:359–372
D’Acierno L, Gallo M, Montella B (2014) Application of metaheuristics to large-scale transportation problems. In: Lirkov I, Margenov S, Wasniewski J (eds) Large-scale scientific computing, vol 8353. Lecture notes in computer science. Springer, Berlin, pp 215–222
Khooban Z, Farahani RZ, Miandoabchi E, Szeto WY (2015) Mixed network design using hybrid scatter search. Eur J Oper Res 247:699–710
Zhang T, Chaovalitwongse WA, Zhang Y (2012) Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries. Comput Oper Res 39:2277–2290
Sun Y, Cao C, Wu C (2014) Multi-objective optimization of train routing problem combined with train scheduling on a high-speed railway network. Transp Res Part C 44:1–20
Albrecht T (2009) Automated timetable design for demand-oriented service on suburban railways. Public Transp 1:5–20
Niu H, Zhou X (2013) Optimizing urban rail timetable under time-dependent demand and oversaturated conditions. Transp Res Part C 36:212–230
Ding Y, Liu H, Bai Y, Zhou F (2011) A two-level optimization model and algorithm for energy-efficient urban train operation. J Transp Syst Eng Inf Technol 11:96–101
Huang Y, Ma X, Su S, Tang T (2015) Optimization of Train operation in multiple interstations with multi-population genetic algorithm. Energies 8:14311–14329
Keskin K, Karamancioglu A (2015) Optimal rail vehicle operation with multiple speed constraints. In: Proceedings of international congress on advanced railway engineering, Istanbul, Mar 2015
Bocharnikov YV, Tobias AM, Roberts C, Hillmansen S, Goodman CJ (2007) Optimal driving strategy for traction energy saving on DC suburban railways. IET Electr Power Appl 1(5):675–682
Sicre C, Cucala AP, Fernández-Cardador A (2014) Real time regulation of efficient driving of high speed trains based on a genetic algorithm and a fuzzy model of manual driving. Eng Appl Artif Intell 29:79–92
Colorni A, Dorigo M, Maniezzo V (1991) Distributed optimization by ant colonies. In: Proceedings of the first European conference on artificial life—ECAL 1991, Paris, Dec 1991
Colorni A, Dorigo M, Maniezzo V (1992) An investigation of some properties of an ant algorithm. In: Proceedings of the parallel problem solving from nature—PPSN 1992, Brussels, Sept 1992
Dorigo M (1992) Optimization, learning and natural algorithms (in Italian). Ph.D. dissertation, Polytechnic of Milan
Dorigo M, Stützle T (2004) Ant colony optimization. The MIT Press, Cambridge
D’Acierno L, Montella B, De Lucia F (2006) A stochastic traffic assignment algorithm based on Ant Colony Optimisation. In: Dorigo M, Gambardella LM, Bittari M, Martinoli A, Poli R, Stützle T (eds) Ant colony optimization and swarm intelligence, vol 4150. Lecture notes in computer science. Springer, Berlin, pp 25–36
Blum JR (1954) Multidimensional stochastic approximation methods. Ann Math Stat 25:737–744
Ke B, Chen M, Lin C (2009) Block-layout design using max–min ant system for saving energy on mass rapid transit systems. IEEE Trans Intell Transp Syst 10(2):226–235
Ke BR, Lin CL, Lai CW (2011) Optimization of train-speed trajectory and control for mass rapid transit systems. Control Eng Pract 19:675–687
Lu SF, Hillmansen S, Ho TK, Roberts C (2013) Single-train trajectory optimization. IEEE Trans Intell Transp Syst 14(2):743–750
Yan X, Cai B, Ning B, ShangGuan W (2016) Online distributed cooperative model predictive control of energy-saving trajectory planning for multiple high-speed train movements. Transp Res Part C 69:60–78
Samà M, Pellegrini P, D’Ariano A, Rodriguez J, Pacciarelli D (2016) Ant colony optimization for the real-time train routing selection problem. Transp Res Part B 85:89–108
Samà M, D’Ariano A, Pacciarelli D, Pellegrini P, Rodriguez J (2017) Ant Colony Optimization for train routing selection: operational vs tactical application. In: Proceedings of the 5th IEEE international conference on models and technologies for intelligent transportation systems—IEEE MT-ITS 2017, Naples, June 2017
Eaton J, Yang S (2014) Dynamic railway junction rescheduling using population based Ant Colony Optimisation. In: Proceedings of the 14th UK workshop on computational intelligence, Bradford, Sept 2014
Fan B, Roberts C, Weston P (2012) A comparison of algorithms for minimising delay costs in disturbed railway traffic scenarios. J Rail Transp Plan Manag 2:23–33
De Martinis V, Corman F (2018) Data-driven perspectives for energy efficient operations in railway systems: current practices and future opportunities. Transp Res Part C 95:679–697
RAS Problem Solving Competition (2018) Link: http://connect.informs.org/railway-applications/awards/problem-solving-competition. Accessed Oct 2018
ONTIME European project. Web site: www.ontime-project.eu. Accessed Oct 2018
D’Ariano A, D’Ariano P, Samà M, Pacciarelli D (2013) Real-time train scheduling from theory to practice. Technical report. http://www.dia.uniroma3.it/~sezione/wordpress/wp-content/uploads/2015/02/2013-207.pdf. Accessed Oct 2018
Open Access
This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no competing interests.
Additional information
Editor: Xuesong Zhou.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made.
The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
To view a copy of this licence, visit https://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Botte, M., D’Acierno, L. Dispatching and Rescheduling Tasks and Their Interactions with Travel Demand and the Energy Domain: Models and Algorithms. Urban Rail Transit 4, 163–197 (2018). https://doi.org/10.1007/s40864-018-0090-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40864-018-0090-8