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.     

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 stochastic optimization model for transit network timetable design to mitigate the randomness of traveling time by adding slack time

Transit network timetabling aims at determining the departure time of each trip of all lines in order to facilitate passengers transferring either to or from a bus. In this paper, we consider a bus timetabling problem with stochastic travel times (BTP-STT). Slack time is added into timetable to mitigate the randomness in bus travel times. We then develop a stochastic integer programming model for the BTP-STT to minimize the total waiting time cost for three types of passengers (i.e., transferring passengers, boarding passengers and through passengers). The mathematical properties of the model are characterized. Due to its computational complexity, a genetic algorithm with local search (GALS) is designed to solve our proposed model (OPM). The numerical results based on a small bus network show that the timetable obtained from OPM reduces the total waiting time cost by an average of 9.5%, when it is tested in different scenarios. OPM is relatively effective if the ratio of the number of through passengers to the number of transferring passengers is not larger than a threshold (e.g., 10 in our case). In addition, we test different scale instances randomly generated in a practical setting to further verify the effectiveness of OPM and GALS. We also find that adding slack time into timetable greatly benefits transferring passengers by reducing the rate of transferring failure.     

An equity‐based passenger flow control model with application to Hong Kong‐Shenzhen border‐crossing

Cross‐border passengers from Hong Kong to Shenzhen by the east Kowloon‐Canton Railway (KCR) through the Lo Wu customs exceed nearly 200 thousand on a special day such as a day during the Chinese Spring Festival. Such heavy passenger demand often exceeds the processing and holding capacity of the Lo Wu customs for many hours a day. Thus, passengers must be metered off at all entrance stations along the KCR line through ticket rationing to restrain the number of passengers waiting at Lo Wu within its safe holding capacity. This paper proposes an optimal control strategy and model to deal with this passenger crowding and control problem. Because the maximum passenger checkout rate at Lo Wu is fixed, total passenger waiting time is not affected by the control strategy for given time‐dependent arriving rates at each station. An equity‐based control strategy is thus proposed to equalize the waiting times of passengers arriving at all stations at the same time. This equity is achieved through optimal allocation of the total quota of tickets to all entrance stations for each train service. The total ticket quota for each train service is determined such that the capacity constraint of the passenger queue at Lo Wu is satisfied. The control problem is formulated as a successive linear programming problem and demonstrated for the KCR system with partially simulated data.     

A capacity restraint transit assignment with elastic line frequency

This paper proposes a new formulation for the capacity restraint transit assignment problem with elastic line frequency, in which the line frequency is related to the passenger flows on transit lines. A stochastic user equilibrium transit assignment model with congestion and elastic line frequency is proposed and the equivalent mathematical programming problem is also formulated. Since the passenger waiting time and the line capacity are dependent on the line frequency, a fixed point problem with respect to the line frequency is devised accordingly. The existence of the fixed point problem has been proved. A solution algorithm for the proposed model is presented. Finally, a numerical example is used to illustrate the application of the proposed model and solution algorithm.     

Passenger-demands-oriented train scheduling for an urban rail transit network

This paper considers the train scheduling problem for an urban rail transit network. We propose an event-driven model that involves three types of events, i.e., departure events, arrival events, and passenger arrival rates change events. The routing of the arriving passengers at transfer stations is also included in the train scheduling model. Moreover, the passenger transfer behavior (i.e., walking times and transfer times of passengers) is also taken into account in the model formulation. The resulting optimization problem is a real-valued nonlinear nonconvex problem. Nonlinear programming approaches (e.g., sequential quadratic programming) and evolutionary algorithms (e.g., genetic algorithms) can be used to solve this train scheduling problem. The effectiveness of the event-driven model is evaluated through a case study.     

Simultaneous passenger train routing and timetabling using an efficient train-based Lagrangian relaxation decomposition

This paper focuses on the simultaneous passenger train routing and timetabling problem on the rail network consisting of both unidirectional and bidirectional tracks using an efficient train-based Lagrangian relaxation decomposition. We first build an integer linear programming model with many 0–1 binary and non-negative integer decision variables, after then reformulate it as a train path-choice model for providing an easier train-based Lagrangian relaxation decomposition mechanism based on the construction of space-time discretized network extending from node-cell-based rail network. Moreover, through reformulating safety usage interval restrictions with a smaller number of constraints in this reformulated model, the train-based decomposition needs fewer Lagrangian multipliers to relax these constraints. On the basis of this decomposition, a solving framework including a heuristic algorithm is proposed to simultaneously optimize both the dual and feasible solutions. A set of numerical experiments demonstrate the proposed Lagrangian relaxation decomposition approach has better performances in terms of minimizing both train travel time and computational times.     

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.     

A case study on the coordination of last trains for the Beijing subway network

Passengers may make several transfers between different lines to reach their destinations in urban railway transit networks. Coordination of last trains in feeding lines and connecting lines at transfer stations is especially important because it is the last chance for many travellers to transfer. In this paper, a mathematical method is used to reveal the relationships between passenger transfer connection time (PTCT) and passenger transfer waiting time (PTWT). A last-train network transfer model (LNTM) is established to maximize passenger transfer connection headways (PTCH), which reflect last-train connections and transfer waiting time. Additionally, a genetic algorithm (GA) is developed based upon this LNTM model and used to test a numerical example to verify its effectiveness. Finally, the Beijing subway network is taken as a case study. The results of the numerical example show that the model improves five connections and reduces to zero the number of cases when a feeder train arrives within one headway’s time after the connecting train departed.     

Stochastic transit equilibrium

We present a transit equilibrium model in which boarding decisions are stochastic. The model incorporates congestion, reflected in higher waiting times at bus stops and increasing in-vehicle travel time. The stochastic behavior of passengers is introduced through a probability for passengers to choose boarding a specific bus of a certain service. The modeling approach generates a stochastic common-lines problem, in which every line has a chance to be chosen by each passenger. The formulation is a generalization of deterministic transit assignment models where passengers are assumed to travel according to shortest hyperpaths. We prove existence of equilibrium in the simplified case of parallel lines (stochastic common-lines problem) and provide a formulation for a more general network problem (stochastic transit equilibrium). The resulting waiting time and network load expressions are validated through simulation. An algorithm to solve the general stochastic transit equilibrium is proposed and applied to a sample network; the algorithm works well and generates consistent results when considering the stochastic nature of the decisions, which motivates the implementation of the methodology on a real-size network case as the next step of this research.     

Equity-oriented skip-stopping schedule optimization in an oversaturated urban rail transit network

In this study, we focus on improving system-wide equity performance in an oversaturated urban rail transit network based on multi-commodity flow formulation. From the system perspective, an urban rail transit network is a distributed system, where a set of resources (i.e., train capacity) is shared by a number of users (i.e., passengers), and equitable individuals and groups should receive equal shares of resources. However, when oversaturation occurs in an urban rail transit network during peak hours, passengers waiting at different stations may receive varying shares of train capacity leading to the inequity problem under train all-stopping pattern. Train skip-stopping pattern is an effective operational approach, which holds back some passengers at stations and re-routes their journeys in the time dimension based on the available capacity of each train. In this study, the inequity problem in an oversaturated urban rail transit network is analyzed using a multi-commodity flow modeling framework. In detail, first, discretized states, corresponding to the number of missed trains for passengers, are constructed in a space-time-state three-dimensional network, so that the system-wide equity performance can be viewed as a distribution of all passengers in different states. Different from existing flow-based optimization models, we formulate individual passenger and train stopping pattern as commodity and network structure in the multi-commodity flow-modeling framework, respectively. Then, we aim to find an optimal commodity flow and well-designed network structure through the proposed multi-commodity flow model and simultaneously achieve the equitable distribution of all passengers and the optimal train skip-stopping pattern. To quickly solve the proposed model and find an optimal train skip-stopping pattern with preferable system-wide equity performance, the proposed linear programming model can be effectively decomposed to a least-cost sub-problem with positive arc costs for each individual passenger and a least-cost sub-problem with negative arc costs for each individual train under a Lagrangian relaxation framework. For application and implementation, the proposed train skip-stopping optimization model is applied to a simple case and a real-world case based on Batong Line in the Beijing Subway Network. The simple case demonstrates that our proposed Lagrangian relaxation framework can obtain the approximate optimal solution with a small-gap lower bound and a lot of computing time saved compared with CPLEX solver. The real-world case based on Batong Line in the Beijing Subway Network compares the equity and efficiency indices under the operational approach of train skip-stopping pattern with those under the train all-stopping pattern to state the advantage of the train skip-stopping operational approach.     

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.     

Metro disruption management: Optimal initiation time of substitute bus services under uncertain system recovery time

Determining the initiation time of substitute bus (SB) services is critical for metro disruption management, especially under uncertain recovery time. This study develops a mathematical formulation to determine the optimal initiation time (OIT) of SB services by trading-off their initiation cost and passenger delay cost, thereby minimizing the total system cost. Given the probability distribution of metro disruption duration, we determine the OIT by formulating an optimization problem to minimize the expected total system cost. We then conduct sensitivity analyses of the initiation cost of SB services, passenger value of time, and SB services rate. The results show that SB services ought to be activated only if the metro incident lasts longer than a certain time interval, depending on the factors mentioned earlier, and the OIT should advance with the predicted incident duration. This paper derives analytical results for the case of linear passenger arrival, and determines the results numerically for the case of non-linear passenger arrival when analytical closed-form solutions are not available. The findings will facilitate transit operators to develop response plans in the aftermath of a metro disruption.     

A robust,tactic-based,real-time framework for public-transport transfer synchronization

Missed transfers affect public transport (PT) operations by increasing passenger’s waiting and travel times and frustration. Because of the stochastic and uncertain nature of PT systems, synchronized transfers do not always materialize. This work proposes a new mathematical programming model to minimize total passenger travel time and maximize direct (without waiting) transfers. The model consists of four policies built on a combination of three tactics: holding, skip-stops, and short-turn, the last applied, for the first time, as a real-time control action. The concept is implemented in two steps: optimization and simulation. An agent-based simulation framework is used to represent real-life scenarios, generate random input data, and validate the optimization results. In order to assess the robustness of this framework, a wide range of schedule-deviation scenarios are defined using efficient algorithms for solving the control models within a rolling horizon structure. A case study of the Auckland, New Zealand, PT system is described for assessing the methodology developed. The results show a 4.7% reduction in total passenger travel time and a more than 150% increase in direct transfers. The best impressive results are attained under short headway operations.     

A subway planning bi-objective multi-period optimization model integrating timetabling and vehicle scheduling: a case study of Tehran

Due to the interaction among different planning levels and various travel demands during a day, the transit network planning is of great importance. In this paper, a bi-objective multi-period planning model is proposed for the synchronization of timetabling and vehicle scheduling. The main aim of the problem is to minimize the weighted transfer waiting time in the interchange stations along with the operational costs of vehicles. In order to demonstrate the effectiveness of the proposed integrated model, a real case study of Tehran subway is considered. The proposed model is solved by the ε-constraint method and some outstanding results are achieved.

     

Passenger arrival and waiting time distributions dependent on train service frequency and station characteristics: A smart card data analysis

Waiting time at public transport stops is perceived by passengers to be more onerous than in-vehicle time, hence it strongly influences the attractiveness and use of public transport. Transport models traditionally assume that average waiting times are half the service headway by assuming random passenger arrivals. However, research agree that two distinct passenger behaviour types exist: one group arrives randomly, whereas another group actively tries to minimise their waiting time by arriving in a timely manner at the scheduled departure time. This study proposes a general framework for estimating passenger waiting times which incorporates the arrival patterns of these two groups explicitly, namely by using a mixture distribution consisting of a uniform and a beta distribution. The framework is empirically validated using a large-scale automatic fare collection system from the Greater Copenhagen Area covering metro, suburban, and regional rail stations thereby giving a range of service headways from 2 to 60 min. It was shown that the proposed mixture distribution is superior to other distributions proposed in the literature. This can improve waiting time estimations in public transport models. The results show that even at 5-min headways 43% of passengers arrive in a timely manner to stations when timetables are available. The results bear important policy implications in terms of providing actual timetables, even at high service frequencies, in order for passengers to be able to minimise their waiting times.     

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.     

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.     

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.