Hybrid cyclicity: Combining the benefits of cyclic and non-cyclic timetables

We propose a new type of timetable that would combine both the regularity of the cyclic timetables and the flexibility of the non-cyclic ones. In order to do so, several combinations of the two timetables are considered. The regularity is incorporated in their design and the flexibility is evaluated using the passenger satisfaction (in monetary units). Each of the tested timetables is constructed using the Passenger Centric Train Timetabling Problem (PCTTP), that is solved using a simulated annealing heuristic. Note that the PCTTP, unlike the traditional Train Timetabling Problem (TTP), does not take into account the conflicts among trains. The aim of the PCTTP is to design such timetables that the passengers’ satisfaction is maximized and it remains the aim of the TTP to remove any potential conflicts. The performance of each of the considered timetables is assessed on the real network of Israeli Railways. The results of the case study show that our proposed hybrid cyclic timetable can provide the benefits of the cyclic and the non-cyclic timetable simultaneously. This timetable consists of 75% of cyclic trains (securing the regularity of the service) and of 25% of non-cyclic trains (deployed as supplementary trains during the peak hours and capturing the demand fluctuation). The level of the passenger satisfaction of the hybrid cyclic timetable is similar to the level of the non-cyclic one, which has about 18.5% of improvement as compared to the purely cyclic one.     

The multi-objective railway timetable rescheduling problem

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 $\epsilon$-constraints for the two other ones. By solving the problem for different values of $\epsilon$, 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.     

Optimizing train stopping patterns and schedules for high-speed passenger rail corridors

High-speed railway (HSR) systems have been developing rapidly in China and various other countries throughout the past decade; as a result, the question of how to efficiently operate such large-scale systems is posing a new challenge to the railway industry. A high-quality train timetable should take full advantage of the system’s capacity to meet transportation demands. This paper presents a mathematical model for optimizing a train timetable for an HSR system. We propose an innovative methodology using a column-generation-based heuristic algorithm to simultaneously account for both passenger service demands and train scheduling. First, we transform a mathematical model into a simple linear programming problem using a Lagrangian relaxation method. Second, we search for the optimal solution by updating the restricted master problem (RMP) and the sub-problems in an iterative process using the column-generation-based algorithm. Finally, we consider the Beijing–Shanghai HSR line as a real-world application of the methodology; the results show that the optimization model and algorithm can improve the defined profit function by approximately 30% and increase the line capacity by approximately 27%. This methodology has the potential to improve the service level and capacity of HSR lines with no additional high-cost capital investment (e.g., the addition of new tracks, bridges and tunnels on the mainline and/or at stations).     

An activity-based approach for scheduling multimodal transit services

This paper proposes a new activity-based transit assignment model for investigating the scheduling (or timetabling) problem of transit services in multi-modal transit networks. The proposed model can be used to generate the short-term and long-term timetables of multimodal transit lines for transit operations and service planning purposes. The interaction between transit timetables and passenger activity-travel scheduling behaviors is captured by the proposed model, as the activity and travel choices of transit passengers are considered explicitly in terms of departure time choice, activity/trip chain choices, activity duration choice, transit line and mode choices. A heuristic solution algorithm which combines the Hooke–Jeeves method and an iterative supply–demand equilibrium approach is developed to solve the proposed model. Two numerical examples are presented to illustrate the differences between the activity-based approach and the traditional trip-based method, together with comparison on the effects of optimal timetables with even and uneven headways. It is shown that the passenger travel scheduling pattern derived from the activity-based approach is significantly different from that obtained by the trip-based method, and that a demand-sensitive (with uneven headway) timetable is more efficient than an even-headway timetable.     

Inter-city bus routing and timetable setting under stochastic demands

Vehicle fleet routing and timetable setting are essential to the enhancement of an inter-city bus carrier’s operating cost, profit, level of service and competitiveness in the market. In past research the average passenger demand has usually served as input in the production of the final fleet routes and timetables, meaning that stochastic disturbances arising from variations in daily passenger demand in actual operations are neglected. To incorporate the stochastic disturbances of daily passenger demands that occur in actual operations, in this research, we established a stochastic-demand scheduling model. We applied a simulation technique, coupled with link-based and path-based routing strategies, to develop two heuristic algorithms to solve the model. To evaluate the performance of the proposed model and the two solution algorithms, we developed an evaluation method. The test results, regarding a major Taiwan inter-city bus operation, were good, showing that the model and the solution algorithms could be useful in practice.     

An integrated micro–macro approach to robust railway timetabling

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.     

Passenger oriented railway disruption management by adapting timetables and rolling stock schedules

In passenger railway operations, unforeseen events require railway operators to adjust their timetable and their resource schedules. The passengers will also adapt their routes to their destinations. When determining the new timetable and rolling stock schedule, the railway operator has to take passenger behavior into account. The operator should increase the capacity of trains for which the operator expects more demand than on a regular day. Furthermore, the operator could increase the frequency of the trains that serve stations with an additional demand.This paper describes a real-time disruption management approach which integrates the rescheduling of the rolling stock and the timetable by taking the changed passenger demand into account. The timetable decisions are limited to additional stops of trains at stations at which they normally would not call. Several variants of the approach are suggested, with the difference in how to determine which additional stops should be executed.Real-time rescheduling requires fast solutions. Therefore a heuristic approach is used. We demonstrate the performance of the several variants of our algorithm on realistic instances of Netherlands Railways, the major railway operator in the Netherlands.     

Estimation method for railway passengers’ train choice behavior with smart card transaction data

Smart card systems have become the predominant method of collecting public transport fares in Japan. Transaction data obtained through smart cards have resulted in a large amount of archived information on how passengers use public transportation. The data have the potential to be used for modeling passenger behavior and demand for public transportation. This study focused on train choices made by railway passengers. If each passenger’s train choice can be identified over a long period of time, this information would be useful for improving the customer relationship management of the railway company and for improving train timetables. The aim of this study was to develop a methodology for estimating which train is boarded by each smart card holder. This paper presents a methodology and an algorithm for estimation using long-term transaction data. To validate the computation time and accuracy of the estimation, an empirical analysis is carried out using actual transaction data provided by a railway company in Japan. The results show that the proposed method is capable of estimating passenger usage patterns from smart card transaction data collected over a long time period.     

Reducing the passenger travel time in practice by the automated construction of a robust railway timetable

Automatically generating timetables has been an active research area for some time, but the application of this research in practice has been limited. We believe this is due to two reasons. Firstly, some of the models in the literature impose artificial upper bounds on time supplements. This causes a high risk of generating infeasibilities. Secondly, some models that leave out these upper bounds often generate solutions that contain some very large time supplements because these supplements are not penalised in the objective function. The reason is that these objective functions often do not completely correspond to the true goal of a timetable. We solve both problems by minimising our objective function: total passenger travel time, expected in practice. Since this function evaluates and indirectly steers all time related decision variables in the system, we do not need to further restrict the ranges of any of these variables. As a result, our model does not suffer from infeasibilities generated by such artificial upper bounds for supplements.Furthermore, some measures are taken to significantly speed up the solver times of our model. These combined features result in our model being solved more quickly than previous models. As a result, our method can be used for timetabling in practice. We demonstrate our claims by optimising, in about two hours only, the timetable of all 196 hourly passenger trains in Belgium. Assuming primary delay-distributions with an average of 2% on the minima of each activity, the optimised timetable reduces expected passenger time in practice, as evaluated on the macroscopic level, by 3.8% during peak hours. This paper demonstrates that we added two important missing steps to make cyclic timetabling for passengers really useable in practice: (i) the addition of the objective function of expected passenger time in practice and (ii) the reduction of computation time by addition of well chosen additional constraints.     

Optimal timetable development for community shuttle network with metro stations

This paper investigates an issue for optimizing synchronized timetable for community shuttles linked with metro service. Considering a passenger arrival distribution, the problem is formulated to optimize timetables for multiple community shuttle routes, with the objective of minimizing passenger’s schedule delay cost and transfer cost. Two constraints, i.e., vehicle capacity and fleet size, are modeled in this paper. The first constraint is treated as soft, and the latter one is handled by a proposed timetable generating method. Two algorithms are employed to solve the problem, i.e., a genetic algorithm (GA) and a Frank–Wolfe algorithm combined with a heuristic algorithm of shifting departure times (FW-SDT). FW-SDT is an algorithm specially designed for this problem. The simulated and real-life examples confirm the feasibility of the two algorithms, and demonstrate that FW-SDT outperforms GA in both accuracy and effectiveness.     

A constraint generation algorithm for the construction of periodic railway timetables

This paper addresses the problem of constructing periodic timetables for train operations. We use a mathematical model consisting of periodic time window constraints by means of which arrival and departure times can be related pairwise on a clock, rather than on a linear time axis. Constructing a timetable, then, means solving a set of such constraints. This problem is known to be hard, i.e. it is NP-complete. We describe a new algorithm to solve the problem based on constraint generation and work out a real-life example. It appears that, for problem instances of modest, yet non-trivial, size, the algorithm performs very well, which opens a way to thorough performance analysis of railway systems by studying a large number of possible future timetables.     

A multi-objective train scheduling model and solution

This paper develops a multi-objective optimization model for the passenger train-scheduling problem on a railroad network which includes single and multiple tracks, as well as multiple platforms with different train capacities. In this study, lowering the fuel consumption cost is the measure of satisfaction of the railway company and shortening the total passenger-time is being regarded as the passenger satisfaction criterion. The solution of the problem consists of two steps. First the Pareto frontier is determined using the -constraint method, and second, based on the obtained Pareto frontier detailed multi-objective optimization is performed using the distance-based method with three types of distances. Numerical examples are given to illustrate the model and solution methodology.     

Demand-driven timetable design for metro services

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.     

Optimizing the demand captured by a railway system with a regular timetable

The railway systems in various European countries adopt regular timetables, in which the trains arrive and depart at constant intervals. In fact, their simple structure provides several advantages both to the passengers and to the management of the service. The design of such timetables has recently received a certain attention in the literature, but the standard model aims to optimize the service for a fixed demand. We relax this unrealistic assumption, taking into account the reciprocal influence between the quality of the timetable and the amount of transport demand captured by the railway. This results into a mixed-integer non linear model with a non-convex continuous relaxation. We solve it by a branch-and-bound algorithm based on a piecewise-linear overestimate of the objective function and a heuristic algorithm which iteratively applies the standard fixed-demand model and a demand-estimation model, feeding each one with data based on the solution obtained from the other one at the previous iteration. The computational results presented concern both random instances and a real-world regional network located in Northwestern Italy.     

A bi-level model for single-line rail timetable design with consideration of demand and capacity

This paper proposes a bi-level model to solve the timetable design problem for an urban rail line. The upper level model aims at determining the headways between trains to minimize total passenger cost, which includes not only the usual perceived travel time cost, but also penalties during travel. With the headways given by the upper level model, passengers’ arrival times at their origin stops are determined by the lower level model, in which the cost-minimizing behavior of each passenger is taken into account. To make the model more realistic, explicit capacity constraints of individual trains are considered. With these constraints, passengers cannot board a full train, but wait in queues for the next coming train. A two-stage genetic algorithm incorporating the method of successive averages is introduced to solve the bi-level model. Two hypothetical examples and a real world case are employed to evaluate the effectiveness of the proposed bi-level model and algorithm. Results show that the bi-level model performs well in reducing total passenger cost, especially in reducing waiting time cost and penalties. And the section loading-rates of trains in the optimized timetable are more balanced than the even-headway timetable. The sensitivity analyses show that passenger’s desired arrival time interval at destination and crowding penalty factor have a high influence on the optimal solution. And with the dispersing of passengers' desired arrival time intervals or the increase of crowding penalty factor, the section loading-rates of trains become more balanced.     

Transit scheduling

This paper provides an overview of the transit operational planning process with an emphasis on certain aspects of new methodologies in scheduling. The transit scheduling system usually consists of three interelated components: (1) creation of timetables; (2) scheduling vehicles to trips; and (3) assignment of drivers. These three components are described, but with a focus on the first component because of its importance from the user's perspective. The design of a transit timetable is discussed from both a practical and an analytical viewpoint. A methodology is presented on the construction of alternative computerized public timetables, based on procedures that improve the correspondence of vehicle departure times with passenger demand. The vehicle scheduling procedure is viewed through the minimization of the number of vehicles required to carry out a fixed or variable timetable. Finally, different approaches to the crew assignment component are briefly discussed. The overview and methodologies presented in the paper suggest that most scheduling tasks can be performed automatically or in a conversational man-computer mode. The adoption of new scheduling procedures will undoubtedly increase the efficiency of each of the three components of the transit scheduling system.     

Multi-objective re-synchronizing of bus timetable: Model,complexity and solution

This work is originally motived by the re-planning of a bus network timetable. The existing timetable with even headways for the network is generated using line by line timetabling approach without considering the interactions between lines. Decision-makers (i.e., schedulers) intend to synchronize vehicle timetable of lines at transfer nodes to facilitate passenger transfers while being concerned with the impacts of re-designed timetable on the regularity of existing timetable and the accustomed trip plans of passengers. Regarding this situation, we investigate a multi-objective re-synchronizing of bus timetable (MSBT) problem, which is characterized by headway-sensitive passenger demand, uneven headways, service regularity, flexible synchronization and involvement of existing bus timetable. A multi-objective optimization model for the MSBT is proposed to make a trade-off between the total number of passengers benefited by smooth transfers and the maximal deviation from the departure times of the existing timetable. By clarifying the mathematical properties and solution space of the model, we prove that the MSBT problem is NP-hard, and its Pareto-optimal front is non-convex. Therefore, we design a non-dominated sorting genetic (NSGA-II) based algorithm to solve this problem. Numerical experiments show that the designed algorithm, compared with enumeration method, can generate high-quality Pareto solutions within reasonable times. We also find that the timetable allowing larger flexibility of headways can obtain more and better Pareto-optimal solutions, which can provide decision-makers more choice.     

The concept and impact analysis of a flexible mobility on demand system

This paper introduces an innovative transportation concept called Flexible Mobility on Demand (FMOD), which provides personalized services to passengers. FMOD is a demand responsive system in which a list of travel options is provided in real-time to each passenger request. The system provides passengers with flexibility to choose from a menu that is optimized in an assortment optimization framework. For operators, there is flexibility in terms of vehicle allocation to different service types: taxi, shared-taxi and mini-bus. The allocation of the available fleet to these three services is carried out dynamically so that vehicles can change roles during the day. The FMOD system is built based on a choice model and consumer surplus is taken into account in order to improve passenger satisfaction. Furthermore, profits of the operators are expected to increase since the system adapts to changing demand patterns. In this paper, we introduce the concept of FMOD and present preliminary simulation results. It is shown that the dynamic allocation of the vehicles to different services provides significant benefits over static allocation. Furthermore, it is observed that the trade-off between consumer surplus and operator’s profit is critical. The optimization model is adapted in order to take into account this trade-off by controlling the level of passenger satisfaction. It is shown that with such control mechanisms FMOD provides improved results in terms of both profit and consumer surplus.     

Optimization of airport bus timetable in cultivation period considering passenger dynamic airport choice under conditions of uncertainty

An airport bus service, which is newly introduced in a multi-airport region, commonly leads to a gradually increasing market share of airports until a new state of equilibrium is reached. With the goal of speeding up and enlarging the increase in market share, this paper proposes a timetable optimization model by incorporating reactions of airport-loyal passengers to bus service quality. The simulation part of the model, which uses cumulative prospect theory to formulate discrete airport choices, results in predicted passenger demand needed in the optimization part. Then a genetic algorithm for multi-objective optimization problems called NSGA-II is applied to solve the model. To illustrate the model, the “Lukou airport-Wuxi” airport bus in China is taken as an example. The results show that the optimized timetables shorten the cultivation period and impel the market share to grow rapidly.     

Passenger Perspectives in Railway Timetabling: A Literature Review

When looking at railway planning, a discrepancy exists between planners who focus on the train operations and publish fixed railway schedules, and passengers who look not only at the schedules but also at the entirety of their trip, from access to waiting to on-board travel and egress. Looking into this discrepancy is essential, as assessing railway performances by merely measuring train punctuality would provide an unfair picture of the level of service experienced by passengers. Firstly, passengers’ delays are often significantly larger than the train delays responsible for the passengers to be late. Secondly, trains’ punctuality is often strictly related to too tight schedules that in turn might translate into knock-on delays for longer dwelling times at stations, trip delays for increased risk of missing transfer connections, and uncertain assessment of the level of service experienced, especially with fluctuating passenger demand. A key aspect is the robustness of railway timetables. Empirical evidence indicates that passengers give more importance to travel time certainty than travel time reductions, as passengers associate an inherent disutility with travel time uncertainty. This disutility may be broadly interpreted as an anxiety cost for the need for having contingency plans in case of disruptions, and may be looked at as the motivator for the need for delay-robust railway timetables. Interestingly, passenger-oriented optimisation studies considering robustness in railway planning typically limit their emphasis on passengers to the consideration of transfer maintenance. Clearly, passengers’ travel behaviour is far more complex and multi-faceted and thus several other aspects should be considered, as becoming more and more evident from passenger surveys. The current literature review starts by looking at the parameters that railway optimisation/planning studies are focused on and the key performance indicators that impact railway planning. The attention then turns to the parameters influencing passengers’ perceptions and travel experiences. Finally, the review proposes guidelines on how to reduce the gap between the operators’ railway planning and performance measurement on the one hand and the passengers’ perception of the railway performance on the other hand. Thereby, the conclusions create a foundation for a more passenger-oriented railway timetabling ensuring that passengers are provided with the best service possible with the resources available.