Integrating robust timetabling in line plan optimization for railway systems

We propose a heuristic algorithm to build a railway line plan from scratch that minimizes passenger travel time and operator cost and for which a feasible and robust timetable exists. A line planning module and a timetabling module work iteratively and interactively. The line planning module creates an initial line plan. The timetabling module evaluates the line plan and identifies a critical line based on minimum buffer times between train pairs. The line planning module proposes a new line plan in which the time length of the critical line is modified in order to provide more flexibility in the schedule. This flexibility is used during timetabling to improve the robustness of the railway system. The algorithm is validated on the DSB S-tog network of Copenhagen, which is a high frequency railway system, where overtakings are not allowed. This network has a rather simple structure, but is constrained by limited shunt capacity. While the operator and passenger cost remain close to those of the initially and (for these costs) optimally built line plan, the timetable corresponding to the finally developed robust line plan significantly improves the minimum buffer time, and thus the robustness, in eight out of ten studied cases.     

Timetable optimization models and methods for minimizing passenger waiting time at public transit terminals

This paper focuses on developing mathematical optimization models for the train timetabling problem with respect to dynamic travel demand and capacity constraints. The train scheduling models presented in this paper aim to minimize passenger waiting times at public transit terminals. Linear and non-linear formulations of the problem are presented. The non-linear formulation is then improved through introducing service frequency variables. Heuristic rules are suggested and embedded in the improved non-linear formulation to reduce the computational time effort needed to find the upper bound. The effectiveness of the proposed train timetabling models is illustrated through the application to an underground urban rail line in the city of Tehran. The results demonstrate the effectiveness of the proposed demand-oriented train timetabling models, in terms of decreasing passenger waiting times. Compared to the baseline and regular timetables, total waiting time is reduced by 6.36% and 10.55% respectively, through the proposed mathematical optimization models.     

Improving recovery-to-optimality robustness through efficiency-balanced design of timetable structure

To improve the service quality of the railway system (e.g., punctuality and travel times) and to enhance the robust timetabling methods further, this paper proposes an integrated two-stage approach to consider the recovery-to-optimality robustness into the optimized timetable design without predefined structure information (defined as flexible structure) such as initial departure times, overtaking stations, train order and buffer time. The first-stage timetabling model performs an iterative adjustment of all departure and arrival times to generate an optimal timetable with balanced efficiency and recovery-to-optimality robustness. The second-stage dispatching model evaluates the recovery-to-optimality robustness by simulating how each timetable generated from the first-stage could recover under a set of restricted scenarios of disturbances using the proposed dispatching algorithm. The concept of recovery-to-optimality is examined carefully for each timetable by selecting a set of optimally refined dispatching schedules with minimum recovery cost under each scenario of disturbance. The robustness evaluation process enables an updating of the timetable by using the generated dispatching schedules. Case studies were conducted in a railway corridor as a special case of a simple railway network to verify the effectiveness of the proposed approach. The results show that the proposed approach can effectively attain a good trade-off between the timetable efficiency and obtainable robustness for practical applications.     

Train routing and timetabling problem for heterogeneous train traffic with switchable scheduling rules

This paper proposes a mathematical model for the train routing and timetabling problem that allows a train to occasionally switch to the opposite track when it is not occupied, which we define it as switchable scheduling rule. The layouts of stations are taken into account in the proposed mathematical model to avoid head-on and rear-end collisions in stations. In this paper, train timetable could be scheduled by three different scheduling rules, i.e., no switchable scheduling rule (No-SSR) which allows trains switching track neither at stations and segments, incomplete switchable scheduling rule (In-SSR) which allows trains switching track at stations but not at segments, and complete switchable scheduling rule (Co-SSR) which allows trains switching track both at stations and segments. Numerical experiments are carried out on a small-scale railway corridor and a large-scale railway corridor based on Beijing–Shanghai high-speed railway (HSR) corridor respectively. The results of case studies indicate that Co-SSR outperforms the other two scheduling rules. It is also found that the proposed model can improve train operational efficiency.     

A multiobjective planning model for intercity train seat allocation

This paper presents a multiobjective planning model for generating optimal train seat allocation plans on an intercity rail line serving passengers with many‐to‐many origin‐destination pairs. Two planning objectives of the model are to maximise the operator's total passenger revenue and to minimise the passenger's total discomfort level. For a given set of travel demand, train capacity, and train stop‐schedules, the model is solved by fuzzy mathematical programming to generate a best‐compromise train seat allocation plan. The plan determines how many reserved and non‐reserved seats are to be allocated at each origin station for all subsequent destination stations on each train run operated within a specified operating period. An empirical study on the to‐be‐built Taiwan's high‐speed rail system is conducted to demonstrate the effectiveness of the model. The model can be used for any setting of travel demand and stop‐schedules with various train seating capacities.     

Including passengers’ response to crowding in the Dutch national train passenger assignment model

Transit passengers’ response to crowded conditions has been studied empirically, yet is limitedly included in transport models currently used in the design of policy and infrastructure investments. This has consequences for the practical applicability of these models in studies on, for instance, timetabling, train capacity management strategies, project appraisal, and passenger satisfaction. Here we propose four methods to include the effect of crowding, based on existing studies on passengers’ perception and response as well as often-used crowding indicators. These four alternative methods are implemented in the train passenger assignment procedure of the Dutch national transport model, and evaluated with respect to their impacts on the model results for the Dutch railway network. The four methods relate to four different ways in which an additive trip penalty and/or time-multiplier can be incorporated in the train utility function for different travel purposes, to capture the disutility of crowding as measured by the load factor. The analyses of the test case favor the hybrid method using both a boarding penalty (capturing seat availability upon boarding) and a time-multiplier (capturing physical comfort and safety throughout the trip). This method produces consistent results, while the additional computational effort that it imposes is acceptable. Further empirical underpinning is needed to conclusively show which of these methods best captures passengers’ response behavior quantitatively (for different travel purposes and conditions).     

Optimizing train operational plan in an urban rail corridor based on the maximum headway function

The train operational plan (TOP) plays a crucial role in the efficient and effective operation of an urban rail system. We optimize the train operational plan in a special network layout, an urban rail corridor with one terminal yard, by decomposing it into two sub-problems, i.e., the train departure profile optimization and the rolling stock circulation optimization. The first sub-problem synthetically optimizes frequency setting, timetabling and the rolling stock circulation at the terminal without a yard. The maximum headway function is generated to ensure the service of the train operational plan without considering travel demand, then we present a model to minimize the number of train trips, and design a heuristic algorithm to maximize the train headway. On the basis of a given timetable, the rolling stock circulation optimization only involves the terminal with a yard. We propose a model to minimize the number of trains and yard–station runs, and an algorithm to find the optimal assignment of train-trip pair connections is designed. The computational complexities of the two algorithms are both linear. Finally, a real case study shows that the train operational plan developed by our approach enables a better match of train headway and travel demand, and reduces the operational cost while satisfying the requirement of the level of service.     

Scheduling heterogeneous train traffic on double tracks with efficient dispatching rules

To further improve the utilization rate of railway tracks and reduce train delays, this paper focuses on developing a high-efficiency train routing and timetabling approach for double-track railway corridors in condition that trains are allowable to travel on reverse direction tracks. We first design an improved switchable policy which is rooted in the approaches by Mu and Dessouky (2013), with the analysis of possible delays caused by different path choices. Then, three novel integrated train routing and timetabling approaches are proposed on the basis of a discrete event model and different dispatching rules, including no switchable policy (No-SP), Mu and Dessouky (2013)’s switchable policy (Original-SP) and improved switchable policy (Improved-SP). To demonstrate the performance of the proposed approaches, the heterogeneous trains on Beijing–Shanghai high speed railway are scheduled by aforementioned approaches. The case studies indicate that in comparison to No-SP and Original-SP approaches, respectively, the Improved-SP approach can reduce the total delay of trains up to 44.44% and 73.53% within a short computational time. Moreover, all of the performance criteria of the Improved-SP approach are usually better than those of other two approaches.     

Single track line capacity model

The objective of the research described in this paper was to develop a model for computation of an ultimate capacity of a single track line and to provide a sensitivity analysis of this capacity to the parameters which influence it. The model is based in a concept of mathematical expectation of capacity and can be applied under saturation conditions i.e. a constant demand for service. It can serve for planning purposes, computation of single track line capacity on the base of which estimations are possible concerning a single track line performance under given conditions, as well as commercial time‐tables planning, decisions about a partial or complete construction of the second parallel track along the line in service, intermediate stations locations planning and the necessary facilities along the line under construction.

In the sensitivity analysis, the model allows a change of parameters upon which the capacity depends. These are: the length of the line segment which is considered to be bottleneck for calculation of capacity, traffic distributions per directions, train mix, train velocities and train spacing rules applied by the dispatching service when regulating the traffic on a line.     

A hierarchical line planning approach for a large-scale high speed rail network: The China case

Planning a set of train lines in a large-scale high speed rail (HSR) network is typically influenced by issues of longer travel distance, high transport demand, track capacity constraints, and a non-periodic timetable. In this paper, we describe an integrated hierarchical approach to determine line plans by defining the stations and trains according to two classes. Based on a bi-level programming model, heuristics are developed for two consecutive stages corresponding to each classification. The approach determines day-period based train line frequencies as well as a combination of various stopping patterns for a mix of fast trunk line services between major stations and a variety of slower body lines that offer service to intermediate stations, so as to satisfy the predicted passenger transport demand. Efficiencies of the line plans described herein concern passenger travel times, train capacity occupancy, and the number of transfers. Moreover, our heuristics allow for combining many additional conflicting demand–supply factors to design a line plan with predominantly cost-oriented and/or customer-oriented objectives. A range of scenarios are developed to generate three line plans for a real-world example of the HSR network in China using a decision support system. The performance of potential train schedules is evaluated to further examine the feasibility of the obtained line plans through graphical timetables.     

Challenges raised by freight for the operations planning of a shared-use rail network. A French perspective

Operating rail infrastructures that are shared among different uses is complex. In Western Europe, the predominance of passenger traffic over freight has traditionally led to thorough scheduling of capacity use, with an increasing tendency to anticipate through the design of regular-interval timetables. The paper discusses the specific challenges posed by fitting freight into the timetabling process for a mixed-use rail network, based on current French experience. The analysis is carried out from the perspective of the infrastructure manager. It is mainly supported by the results of a series of about 30 interviews, carried out in 2012 and 2013 with the parties involved in the timetabling process. The paper provides a comprehensive understanding of the process in terms of organization, rules and practices, with an emphasis on the characteristics of freight traffic compared with passenger traffic. The author highlights three key management issues for the French infrastructure manager when dealing with freight: (1) the uncertainty surrounding the mid-long term development of the rail freight market at the national level; (2) the heterogeneity resulting from the diversity of commodities, convoys and profiles and behaviors of the capacity applicants; (3) the volatility of some freight traffic resulting in a great amount of activity in the later stages of the timetabling process. If uncertainty about the future appears to be a highly sensitive issue in the French context, heterogeneity and volatility of freight traffic can be perceived as management challenges that may be experienced, to a greater or lesser degree, on other rail networks.     

Analyzing the theoretical capacity of railway networks with a radial-backbone topology

In this work we propose a mechanism to optimize the capacity of the main corridor within a railway network with a radial-backbone or X-tree structure. The radial-backbone (or X-tree) structure is composed of two types of lines: the primary lines that travel exclusively on the common backbone (main corridor) and radial lines which, starting from the common backbone, branch out to individual locations. We define possible line configurations as binary strings and propose operators on them for their analysis, yielding an effective algorithm for generating an optimal design and train frequencies. We test our algorithm on real data for the high speed line Madrid–Seville. A frequency plan consistent with the optimal capacity is then proposed in order to eliminate the number of transfers between lines as well as to minimize the network fleet size, determining the minimum number of vehicles needed to serve all travel demand at maximum occupancy.     

Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: Nonlinear integer programming models with linear constraints

This paper focuses on how to minimize the total passenger waiting time at stations by computing and adjusting train timetables for a rail corridor with given time-varying origin-to-destination passenger demand matrices. Given predetermined train skip-stop patterns, a unified quadratic integer programming model with linear constraints is developed to jointly synchronize effective passenger loading time windows and train arrival and departure times at each station. A set of quadratic and quasi-quadratic objective functions are proposed to precisely formulate the total waiting time under both minute-dependent demand and hour-dependent demand volumes from different origin–destination pairs. We construct mathematically rigorous and algorithmically tractable nonlinear mixed integer programming models for both real-time scheduling and medium-term planning applications. The proposed models are implemented using general purpose high-level optimization solvers, and the model effectiveness is further examined through numerical experiments of real-world rail train timetabling test cases.     

A heuristic for the train pathing and timetabling problem

In a railroad system, train pathing is concerned with the assignment of trains to links and tracks, and train timetabling allocates time slots to trains. These important tasks were traditionally done manually, but there is an increasing move toward automated software based on mathematical models and algorithms. Most published models in the literature either focus on train timetabling only, or are too complicated to solve when facing large instances. In this paper, we present an optimization heuristic that includes both train pathing and train timetabling, and has the ability to solve real-sized instances. This heuristic allows the operation time of trains to depend on the assigned track, and also lets the minimum headway between the trains to depend on the trains’ relative status. It generates an initial solution with a simple rule, and then uses a four-step process to derive the solution iteratively. Each iteration starts by altering the order the trains travel between stations, then it assigns the services to the tracks in the stations with a binary integer program, determines the order they pass through the stations with a linear program, and uses another linear program to produce a timetable. After these four steps, the heuristic accepts or rejects the new solution according to a Threshold Accepting rule. By decomposing the original complex problem into four parts, and by attacking each part with simpler neighborhood-search processes or mathematical programs, the heuristic is able to solve realistic instances. When tested with two real-world examples, one from a 159.3 km, 29-station railroad that offers 44 daily services, and another from a 345 km, eight-station high-speed rail with 128 services, the heuristic obtained timetables that are at least as good as real schedules.     

Train rescheduling model with train delay and passenger impatience time in urban subway network

This paper considers the train rescheduling problem with train delay in urban subway network. With the objective of minimizing the negative effect of train delay to passengers, which is quantified with a weighted combination of travel time cost and the cost of giving up the planned trips, train rescheduling model is proposed to jointly synchronize both train delay operation constraints and passenger behavior choices. Space–time network is proposed to describe passenger schedule‐based path choices and obtain the shortest travel times. Impatience time is defined to describe the intolerance of passengers to train delay. By comparing the increased travel time due to train delay with the passenger impatience time, a binary variable is defined to represent whether the passenger will give up their planned trips or not. The proposed train rescheduling model is implemented using genetic algorithm, and the model effectiveness is further examined through numerical experiments of real‐world urban subway train timetabling test. Duration effects of the train delay to the optimization results are analyzed. Copyright © 2017 John Wiley & Sons, Ltd.     

A new approach for improving the performance of freight train timetabling of a single-track railway system

A new approach for improving the performance of freight train timetabling for single-track railways is proposed. Using the idea of a fixed-block signaling system, we develop a matrix representation to express the occupation of inter- and intra-station tracks by trains illustrating the train blocking time diagram in its entirety. Train departure times, dwell times, and unnecessary stopping are adjusted to reduce average train travel time and single train travel time. Conflicts between successive stations and within stations are identified and solved. A fuzzy logic system is further used to adjust the range of train departure times and checks are made to determine whether dwell times and time intervals can be adjusted for passenger and freight trains at congested stations to minimize train waiting times. By combining manual scheduling expertise with the fuzzy inference method, timetable efficiency is significantly improved and becomes more flexible.     

A branch-and-price approach for solving the train unit scheduling problem

We propose a branch-and-price approach for solving the integer multicommodity flow model for the network-level train unit scheduling problem (TUSP). Given a train operator’s fixed timetable and a fleet of train units of different types, the TUSP aims at determining an assignment plan such that each train trip in the timetable is appropriately covered by a single or coupled train units. The TUSP is challenging due to its complex nature. Our branch-and-price approach includes a branching system with multiple branching rules for satisfying real-world requirements that are difficult to realize by linear constraints, such as unit type coupling compatibility relations and locations banned for coupling/decoupling. The approach also benefits from an adaptive node selection method, a column inheritance strategy and a feature of estimated upper bounds with node reservation functions. The branch-and-price solver designed for TUSP is capable of handling instances of up to about 500 train trips. Computational experiments were conducted based on real-world problem instances from First ScotRail. The results are satisfied by rail practitioners and are generally competitive or better than the manual ones.     

Energy-efficient operation of rail vehicles

This paper describes an analytical process that computes the optimal operating successions of a rail vehicle to minimize energy consumption. Rising energy prices and environmental concerns have made energy conservation a high priority for transportation operations. The cost of energy consumption makes up a large portion of the Operation and Maintenance (O&M) costs of transit especially rail transit systems. Energy conservation or reduction in energy cost may be one of the effective ways to reduce transit operating cost, therefore improve the efficiency of transit operations.From a theoretical point of view, the problem of energy efficient train control can be formulated as one of the functions of Optimal Control Theory. However, the classic numerical optimization methods such as discrete method of optimum programming are too slow to be used in an on-board computer even with the much improved computation power, today. The contribution of this particular research is the analytical solution that gives the sequence of optimal controls and equations to find the control change points. As a result, a calculation algorithm and a computer program for energy efficient train control has been developed. This program is also capable of developing energy efficient operating schedules by optimizing distributions of running time for an entire route or any part of rail systems.We see the major application of the proposed algorithms in fully or partially automated Train Control Systems. The modern train control systems, often referred as “positive” train control (PTC), have collected a large amount of information to ensure safety of train operations. The same data can be utilized to compute the optimum controls on-board to minimize energy consumption based on the algorithms proposed in this paper. Most of the input data, such as track plan, track profile, traction and braking characteristics, speed limits and required trip time are located in an on-board database and/or they can be transmitted via radio link to be processed by the proposed algorithm and program.     

Non-discriminatory train dispatching in a rail transport market with multiple competing and collaborative train operating companies

Train dispatching is vital for the punctuality of train services, which is critical for a train operating company (TOC) to maintain its competitiveness. Due to the introduction of competition in the railway transport market, the issue of discrimination is attracting more and more attention. This paper focuses on delivering non-discriminatory train dispatching solutions while multiple TOCs are competing in a rail transport market, and investigating impacting factors of the inequity of train dispatching solutions. A mixed integer linear programming (MILP) model is first proposed, in which the inequity of competitors (i.e., trains and TOCs) is formalized by a set of constraints. In order to provide a more flexible framework, a model is further reformulated where the inequity of competitors is formalized as the maximum individual deviation of competitors’ delay cost from average delay cost in the objective function. Complex infrastructure capacity constraints are considered and modelled through a big M-based approach. The proposed models are solved by a standard MILP solver. A set of comprehensive experiments is conducted on a real-world dataset adapted from the Dutch railway network to test the efficiency, effectiveness, and applicability of the proposed models, as well as determine the trade-off between train delays and delay equity.