•We propose a multi-objective periodic timetable optimization problem.•Multiple overtakings are allowed to improve infrastructure occupation and robustness.•The model optimizes a trade-off between ...journey times, regularity, vulnerability, and the number of overtakings.•We apply the epsilon-constraint method and explore the resulting 4-dimensional Pareto frontier.•The method is demonstrated on a real-world Dutch railway corridor.
This paper proposes a new multi-objective periodic railway timetabling (MOPRT) problem with four objectives to be minimized: train journey time, timetable regularity deviation, timetable vulnerability and the number of overtakings. The aim is to find an efficient, regular and robust timetable that utilizes the infrastructure capacity as good as possible. Based on the Periodic Event Scheduling Problem, we formulate the MOPRT problem as a Mixed Integer Linear Program (MILP). The ε-constraint method is applied to deal with the multi-objective property, and algorithms are designed to efficiently create the Pareto frontier. By solving the problem for different values of ε, the four-dimensional Pareto frontier is explored to uncover the trade-offs among the four objectives. The optimal solution is obtained from the Pareto-optimal set by using standardized Euclidean distance, while capacity utilization is used as an additional indicator to chose between close solutions. Computational experiments are performed on a theoretical instance and a real instance in one direction of a Dutch railway corridor, demonstrating the efficiency of the model and approach.
•A new timetable rescheduling model is proposed, which includes flexible stopping and flexible short-turning as well as retiming, reordering, and cancelling trains.•The model deals with all phases of ...a disruption.•Adjusted train running times due to saved (extra) decelerations and accelerations are explicitly considered when skipping (adding) stops.•Station capacity is considered by ensuring that each train corresponding to passenger boarding/alighting stops at a platform track while the minimum headway times are taken into account.•Rolling stock circulations at the short-turning and terminal stations of trains are included.•Dispatching decisions are optimized with the objective of minimizing passenger delays.
Railway operations are vulnerable to unexpected disruptions that should be handled in an efficient and passenger-friendly way. To this end, we propose a timetable rescheduling model where flexible stopping (i.e. skipping stops and adding stops) and flexible short-turning (i.e. full choice of short-turn stations) are innovatively integrated with three other dispatching measures: retiming, reordering, and cancelling. The Mixed Integer Linear Programming model also ensures that each train serving a station is ensured with a platform track. To consider the rescheduling impact on passengers, the weight of each decision is estimated individually according to the time-dependent passenger demand. The objective is minimizing passenger delays. A case study is carried out for hundreds of disruption scenarios on a subnetwork of the Dutch railways. It is found that (1) applying a mix of flexible stopping and flexible short-turning results in less passenger delays; (2) shortening the recovery duration mitigates the post-disruption consequence by less delay propagation but is at the expense of more cancelled train services during the disruption; and (3) the optimal rescheduling solution is sensitive to the disruption duration, but some steady behaviour is observed when the disruption duration increases by the timetable cycle time.
•We present a new planning phase for a passenger railway service.•The new phase integrates the demand (discrete choice theory) and supply (operations research) interaction during the planning.•We ...formulate the problem as a Mixed Integer Linear Programming problem.•One of the objectives (the demand) is incorporated as an epsilon constraint, the result being a Pareto frontier.•We solve the problem using CPLEX.•The applicability of the approach is shown on a case study of a Swiss railway company.•We present quantitative comparison between cyclic and non-cyclic timetable.
The aim of this paper is to analyze and to improve the current planning process of the passenger railway service in light of the recent railway market changes. In order to do so, we introduce the Passenger Centric Train Timetabling Problem. The originality of our approach is that we account for the passenger satisfaction in the design of the timetable. We consider both types of timetable(s): cyclic and non-cyclic. The problem is modeled as a Mixed Integer Linear Programming (MILP) problem with an objective of maximizing the train operating company’s profit while maintaining ε level of passenger satisfaction. The model does not take into account conflicts between trains and does not adjust dwell times at stopping stations among the lines. By solving the model for various values of ε, the approximated Pareto frontier is constructed. The analysis, based on an experiment using realistic data, shows that an improvement of passenger satisfaction while maintaining a low profit loss for the railway company can be achieved. A sensitivity analysis on passenger congestion illustrates a quantitative evidence that the non-cyclic timetables can account better for high density demand in comparison to cyclic timetables.
•We describe an integrated iterative micro–macro approach for computing an conflict-free, stable and robust railway timetable.•We provide bidirectional transformations between microscopic and ...macroscopic timetable models.•We define an automatic procedure to adapt macroscopic input by constraint relaxation and tightening methods.•The macroscopic timetable optimization model includes a post-processing Monte Carlo stochastic robustness evaluation.•The approach is demonstrated on a real network in the Netherlands.
With the increasing demand for railway transportation infrastructure managers need improved automatic timetabling tools that provide feasible timetables with enhanced performance in short computation times. This paper proposes a hierarchical framework for timetable design which combines a microscopic and a macroscopic model of the network. The framework performs an iterative adjustment of train running and minimum headway times until a feasible and stable timetable has been generated at the microscopic level. The macroscopic model optimizes a trade-off between minimal travel times and maximal robustness using an Integer Linear Programming formulation which includes a measure for delay recovery computed by an integrated delay propagation model in a Monte Carlo setting. The application to an area of the Dutch railway network shows the ability of the approach to automatically compute a feasible, stable and robust timetable. Practitioners can use this approach both for effective timetabling and post-evaluation of existing timetables.
•This paper formulates an analytical estimate of aggregate railway delay.•Analysis of the function demonstrates that timetable supplement and buffer are most effective within certain ...ratios.•Numerical analysis shows that the model provides insight even when the theoretical assumptions are violated.•This model can be adapted to heterogeneous traffic patterns and network boundaries.•The model may be scaled and calibrated to match simulation model output.
Railway service quality can be measured by the aggregate delay over a time horizon due to an event that delays a given train. Timetables for railway services may dampen delay propagations to subsequent trains by adding either supplement time or buffer time to the timetable. The evaluation of these variables is often performed by time consuming analysis with simulation software, or other complex, time-consuming calculations. This paper proposes instead an analytical closed form formulation of aggregate delay, which offers theoretical insights into railway delays and managerial insight into the properties of timetables at an aggregate level, and which may function as a fast sub-algorithm for timetable evaluations in larger optimization and transport models. Analysis of the function recommends a restraint in the utilization of timetable supplement and buffer, as their delay-damping effect decreases with their magnitude. Further, the effect of different threshold values in delay measurement is demonstrated, giving information valuable to the design of service contracts. Numerical analysis of a common suburban railway line shows that the polynomial function provides guidance and insight even when theoretical assumptions are violated.
•Consider the accessibility-based last-train timetable problem from the perspective of DNDP.•Formulate two 0–1 linear programming models under the space-time network.•Decompose the original models by ...Lagrangian relaxation.•Design a sub-gradient-based algorithm to iteratively minimize the gap.
To improve the accessibility of the metro network during night operations, this study aims to investigate a collaborative optimization for the last train timetable in an urban rail transit network. By using a space-time network framework, all the involved transportation activities are well characterized in an extended space-time network, in which the train space-time travel arcs, passenger travel arcs, transfer arcs, etc., are all taken into account. Two performance measures are proposed to evaluate the network-based timetable of the last trains. Through considering the route choice behaviors, the problem of interest is formulated as 0–1 linear programming models from the perspective of a space-time network design. To effectively solve the proposed models, we dualize the hard constraints into the objective function to produce the relaxed models by introducing a set of Lagrangian multipliers. Then, the sub-gradient algorithm is proposed to iteratively minimize the gap of the lower and upper bounds of the primal models. Finally, two sets of numerical experiments are implemented in an illustrative network and the Beijing metro network, respectively, and experimental results demonstrate the efficiency and performance of the proposed methods.
•Mechanismsof passenger assignment and energy allocation aredeveloped in an energy regenerative metro system.•Aparallelogram-based method is developed to generate random ...irregulartimetables.•Abi-objective optimization model is formulated foroptimizingregenerative energy use and passenger travel time.•An NSGA-IIbasedalgorithmisadoptedtosolve the bi-objective optimization model.•Operators based on domain knowledge are developed toexplore and exploit the solution space.
Complex passenger demand and electricity transmission processes in metro systems cause difficulties in formulating optimal timetables and train speed profiles, often leading to inefficiency in energy consumption and passenger service. Based on energy-regenerative technologies and smart-card data, this study formulates an optimization model incorporating energy allocation and passenger assignment to balance energy use and passenger travel time. The Non-Dominated Sorting Genetic Algorithm II (NSGA-II) is applied and the core components are redesigned to obtain an efficient Pareto frontier of irregular timetables for maximizing the use of regenerative energy and minimizing total travel time. Particularly, a parallelogram-based method is developed to generate random feasible timetables; crossover and local-search-driven mutation operators are proposed relying on the graphic representations of the domain knowledge. The suggested approach is illustrated using real-world data of a bi-directional metro line in Beijing. The results show that the approach significantly improves regenerative energy use and reduces total travel time compared to the fixed regular timetable.
•Models the scheduling problem as an optimization problem with congruence constraints.•Proposes a new graph representation of the problem.•Provides optimal inapproximability results for the ...optimization problem.•Exposes the close bounds that relate this problem with the MAX DICUT problem.•Customizes and applies approximation algorithms for MAX DICUT in real case studies.
This paper aims to synchronize timetables in a transit network so as to minimize the total passenger transfer waiting time. Assuming a fixed headway for each line, we first formulate the problem as an optimization problem with congruence constraints. We show that the problem is NP-hard, and investigate several special cases of the problem that are solvable in polynomial time. Furthermore, we show that the local search for the general problem is equivalent to the well-studied maximum directed cut problem. As such, we use an approximation algorithm for the maximum directed cut problem to solve the timetable synchronization problem. We assess the quality of the algorithm on a real-world case study, and show that our algorithm significantly outperforms the state-of-the-art in the literature. Lastly, we relax the fixed headway assumption, and propose an efficient recursive quasi-linear time algorithm to minimize the total transfer waiting time in this general setting.
•An exact mathematical model is proposed for railway timetable rescheduling.•We explore the Pareto frontier to understand the trade-offs among the objectives.•We are able to improve passenger ...satisfaction, with low additional operational cost.•Minimizing deviation from a timetable benefits the operator and the passengers.
Unexpected disruptions occur for many reasons in railway networks and cause delays, cancelations, and, eventually, passenger inconvenience. This research focuses on the railway timetable rescheduling problem from a macroscopic point of view in case of large disruptions. The originality of our approach is to integrate three objectives to generate a disposition timetable: the passenger satisfaction, the operational costs and the deviation from the undisrupted timetable. We formulate the problem as an Integer Linear Program that optimizes the first objective and includes ε-constraints for the two other ones. By solving the problem for different values of ε, the three-dimensional Pareto frontier can be explored to understand the trade-offs among the three objectives. The model includes measures such as canceling, delaying or rerouting the trains of the undisrupted timetable, as well as scheduling emergency trains. Furthermore, passenger flows are adapted dynamically to the new timetable. Computational experiments are performed on a realistic case study based on a heavily used part of the Dutch railway network. The model is able to find optimal solutions in reasonable computational times. The results provide evidence that adopting a demand-oriented approach for the management of disruptions not only is possible, but may lead to significant improvement in passenger satisfaction, associated with a low operational cost of the disposition timetable.
•We present three models to design demand-sensitive timetables for metro services.•We use smart card data to better understand spatial–temporal passenger demand.•The demand sensitive timetables are ...advantageous in reducing passenger cost.
Timetable design is crucial to the metro service reliability. A straightforward and commonly adopted strategy in daily operation is a peak/off-peak-based schedule. However, such a strategy may fail to meet dynamic temporal passenger demand, resulting in long passenger waiting time at platforms and over-crowding in trains. Thanks to the emergence of smart card-based automated fare collection systems, we can now better quantify spatial–temporal demand on a microscopic level. In this paper, we formulate three optimization models to design demand-sensitive timetables by demonstrating train operation using equivalent time (interval). The first model aims at making the timetable more dynamic; the second model is an extension allowing for capacity constraints. The third model aims at designing a capacitated demand-sensitive peak/off-peak timetable. We assessed the performance of these three models and conducted sensitivity analyzes on different parameters on a metro line in Singapore, finding that dynamical timetable built with capacity constraints is most advantageous. Finally, we conclude our study and discuss the implications of the three models: the capacitated model provides a timetable which shows best performance under fixed capacity constraints, while the uncapacitated model may offer optimal temporal train configuration. Although we imposed capacity constraints when designing the optimal peak/off-peak timetable, its performance is not as good as models with dynamical headways. However, it shows advantages such as being easier to operate and more understandable to the passengers.
PDF
