User perspectives in public transport timetable optimisation

The present paper deals with timetable optimisation from the perspective of minimising the waiting time experienced by passengers when transferring either to or from a bus. Due to its inherent complexity, this bi-level minimisation problem is extremely difficult to solve mathematically, since timetable optimisation is a non-linear non-convex mixed integer problem, with passenger flows defined by the route choice model, whereas the route choice model is a non-linear non-continuous mapping of the timetable. Therefore, a heuristic solution approach is developed in this paper, based on the idea of varying and optimising the offset of the bus lines. Varying the offset for a bus line impacts the waiting time passengers experience at any transfer stop on the bus line.In the bi-level timetable optimisation problem, the lower level is a transit assignment calculation yielding passengers’ route choice. This is used as weight when minimising waiting time by applying a Tabu Search algorithm to adapt the offset values for bus lines. The updated timetable then serves as input in the following transit assignment calculation. The process continues until convergence.The heuristic solution approach was applied on the large-scale public transport network in Denmark. The timetable optimisation approach yielded a yearly reduction in weighted waiting time equivalent to approximately 45 million Danish kroner (9 million USD).     

Creating bus timetables with maximal synchronization

This paper addresses the problem of generating a timetable for a given network of buses so as to maximize their synchronization. It attempts to maximize the number of simultaneous bus arrivals at the connection (transfer) nodes of the network. Transit schedulers, taking into account the satisfaction and convenience of the system's users, appreciate the importance of creating a timetable with maximal synchronization, which enables the transfer of passengers from one route to another with minimum waiting time at the transfer nodes. In this paper, the problem is formulated as a mixed integer linear programming problem, and a heuristic algorithm is developed to solve the problem in polynomial time. The efficiency of this algorithm, compared to optimal solutions, is illustrated through a series of examples.     

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.     

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.     

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.     

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.     

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.     

地铁车站票务设备节能优化研究

为解决城市轨道交通车站售票能力冗余导致城市电力资源及地铁公司运营成本闲置的问题,分析普通车站日常客流分布,综合考虑地铁车站售票设备成本和乘客的时间成本因素,建立地铁车站售票设备开启数量优化模型,同时通过排队论和Lingo软件进行计算,获得最优化的地铁车站售票设备开启数量。以郑州地铁农业南路站的日常客流为例,应用地铁车站售票设备开启数量优化模型,计算得到农业南路站售票设备优化方案,通过优化方案进行节能成果分析证明,该方案可有效节约城市电力资源及地铁公司运营成本。     

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.     

Isolating high-priority metro and feeder bus transfers using smart card data

Fixed-rail metro (or ‘subway’) infrastructure is generally unable to provide access to all parts of the city grid. Consequently, feeder bus lines are an integral component of urban mass transit systems. While passengers prefer a seamless transfer between these two distinct transportation services, each service’s operations are subject to a different set of factors that contribute to metro-bus transfer delay. Previous attempts to understand transfer delay were limited by the availability of tools to measure the time and cost associated with passengers’ transfer experience. This paper uses data from smart card systems, an emerging technology that automatically collects passenger trip data, to understand transfer delay. The primary objective of this study is to use smart card data to derive a reproducible methodology that isolates high priority transfer points between the metro system and its feeder-bus systems. The paper outlines a methodology to identify transfer transactions in the smart card dataset, estimate bus headways without the aid of geographic location information, estimate three components of the total transfer time (walking time, waiting time, and delay time), and isolate high-priority transfer pairs. The paper uses smart card data from Nanjing, China as a case study. The results isolate eight high priority metro-bus transfer pairs in the Nanjing metro system and finally, offers several targeted measures to improve transfer efficiency.     

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.

     

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.     

A behavioural comparison of route choice on metro networks: Time,transfers, crowding,topology and socio-demographics

Understanding travellers’ behaviour is key element in transportation planning. This article presents a route choice model for metro networks that considers different time components as well as variables related to the transferring experience, train crowding, network topology and socio-demographic characteristics. The route choice model is applied to the London Underground and Santiago Metro networks, to make a comparison of the decision making process of the users on both cities. As all the variables are statistically significant, it is possible to affirm that public transport users take into account a wide variety of elements when choosing routes. While in London the travellers prefer to spend time walking, in Santiago is preferable to spend time waiting. Santiago Metro users are more willing to travel in crowded trains than London Underground users. Both user groups have a similar dispreference to transfers after controlling for the time spent on transfer, but different attitudes to ascending and descending transfers. Topological factors presented on a distorted Metro map are more important than actual topology to passengers’ route choice decisions.     

A practical model for transfer optimization in a transit network: Model formulations and solutions

This paper studies the transit network scheduling problem and aims to minimize the waiting time at transfer stations. First, the problem is formulated as a mixed integer programming model that gives the departure times of vehicles in lines so that passengers can transfer between lines at transfer stations with minimum waiting times. Then, the model is expanded to a second model by considering the extra stopping time of vehicles at transfer stations as a new variable set. By calculating the optimal values for these variables, transfers can be better performed. The sizes of the models, compared with the existing models, are small enough that the models can be solved for small- and medium-sized networks using regular MIP solvers, such as CPLEX. Moreover, a genetic algorithm approach is represented to more easily solve larger networks. A simple network is used to describe the models, and a medium-sized, real-life network is used to compare the proposed models with another existing model in the literature. The results demonstrate significant improvement. Finally, a large-scale, real-life network is used as a case study to evaluate the proposed models and the genetic algorithm approach.     

Development of efficient stop planning optimization process for high‐speed rail systems

The Taiwan High Speed Rail (THSR) has recently added three additional stations to its original network. Although the three additional stations can improve accessibility to the system, these new stations can present difficulties in the transportation planning process, particularly for planning of train stops. The additional stations may benefit some passengers, but may also lengthen the travel time for the other passengers. Therefore, the main challenge faced by THSR is finding an efficient way to design appropriate stopping patterns. Past studies on stop planning usually adopted meta‐heuristics or decomposition methods to solve this complex problem. Although these solution techniques can improve solution efficiency, none of them can guarantee the optimality of the solution and capture the transfer movement of different stopping patterns. In this research, we proposed an innovative network structure to address complex stop planning problems for high‐speed rail systems. Given its special network structure, two binary integer programming models were developed to simultaneously form and determine the optimal stopping patterns for real‐world THSR stop planning problems. An optimization process was also developed to accurately estimate the station transfer time corresponding to the variation in stopping patterns and passenger flow. Results of the case studies suggest that the proposed binary integer programming models exhibit superior solution quality and efficiency over existing exact optimization models. Consequently, using this stop planning optimization process can help high‐speed rail system planners in designing optimal stopping patterns that correspond to passenger demand. Copyright © 2017 John Wiley & Sons, Ltd.     

Modelling waiting time for passengers transferring from rail to buses

This paper develops a mathematical model to calculate the average waiting time for passengers transferring from rail transit to buses based on the statistical analysis of primary data collected in Beijing. An important part of the average waiting time modelling is to analyse the distributions of passenger arrival rates. It is shown that the lognormal and gamma distributions have the best fit for direct transfer and non-direct transfer passengers, respectively. Subsequently, an average waiting time model for transferring passengers is developed based on passenger arrival rate distributions. Furthermore, case studies are conducted for two scenarios with real and estimated data, resulting in relative errors of ?3.69% and ?3.77%, respectively. Finally, the paper analyses the impacts of bus headway, the headway of rail cars, and the proportion of direct transfer passengers on average waiting time.     

Analysis of subway station capacity with the use of queueing theory

A new concept of subway station capacity (SSC) is defined according to the gathering and scattering process. A queuing network analytical model of station is created for calculating SSC, which is built by M/G/C/C state dependent queuing network and discrete time Markov chain (DTMC). Based on the definition and the analytical queuing network, a SSC optimization model is developed, whose objective function is to optimize SSC with a satisfactory rate of remaining passengers. Besides, a solution to the model is proposed integrating response surface methodology with iterative generalized expansion method (IGEM) and DTMC. A case study of Beijing Station in Beijing subway line 2 is implemented to verify the validity and practicability of the proposed methods by comparison with simulation model in different experiments. Finally, some sensitivity analysis results are provided to identify the nodes that have the greatest impact on SSC.     

Transit network design based on travel time reliability

This paper presents a transit network optimization method, in which travel time reliability on road is considered. A robust optimization model, taking into account the stochastic travel time, is formulated to satisfy the demand of passengers and provide reliable transit service. The optimization model aims to maximize the efficiency of passenger trips in the optimized transit network. Tabu search algorithm is defined and implemented to solve the problem. Then, transit network optimization method proposed in this paper is tested with two numerical examples: a simple route and a medium-size network. The results show the proposed method can effectively improve the reliability of a transit network and reduce the travel time of passengers in general.     

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.     

A congested and dwell time dependent transit corridor assignment model

This research proposes an equilibrium assignment model for congested public transport corridors in urban areas. In this model, journey times incorporate the effect of bus queuing on travel times and boarding and alighting passengers on dwell times at stops. The model also considers limited bus capacity leading to longer waiting times and more uncomfortable journeys. The proposed model is applied to an example network, and the results are compared with those obtained in a recent study. This is followed by the analysis and discussion of a real case application in Santiago de Chile. Finally, different boarding and alighting times and different vehicle types are evaluated. In all cases, demand on express services tends to be underestimated by using constant dwell time assignment models, leading to potential planning errors for these lines. The results demonstrate the importance of considering demand dependent dwell times in the assignment process, especially at high demand levels when the capacity constraint should also be considered. Copyright © 2017 John Wiley & Sons, Ltd.