A bi‐level programming approach — Optimal transit fare under line capacity constraints

The fare of a transit line is one of the important decision variables for transit network design. It has been advocated as an efficient means of coordinating the transit passenger flows and of alleviating congestion in the transit network. This paper shows how transit fare can be optimized so as to balance the passenger flow on the transit network and to reduce the overload delays of passengers at transit stops. A bi‐level programming method is developed to optimize the transit fare under line capacity constraints. The upper‐level problem seeks to minimize the total network travel time, while the lower‐level problem is a stochastic user equilibrium transit assignment model with line capacity constraints. A heuristic solution algorithm based on sensitivity analysis is proposed. Numerical example is used to illustrate the application of the proposed model and solution algorithm.     

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.     

Transit assignment under crowded conditions

This paper presents a transit assignment algorithm for crowded networks. Both congestion in vehicles and queuing at stations are explicitly taken into account in predicting passenger flows for a fixed pattern of origin-destination trip demands. The overflow effects due to insufficient capacity of transit lines are considered to be concentrated at transit stations, while the in-vehicle congestion effects (or discomforts) are considered to be dependent on in-vehicle passenger volume. Overflow delay at a transit station is dependent on the number of excess passengers required to wait for the next transit car. We use a logit model to determine the split between passengers that chose to wait for the next transit car and passengers that chose to board on the alternative transit lines. The proposed algorithm predicts how passenger will choose their optimal routes under both queuing and crowded conditions.     

Network equilibrium for congested multi‐mode networks with elastic demand

This paper proposes an elastic demand network equilibrium model for networks with transit and walking modes. In Hong Kong, the multi‐mode transit system services over 90% of the total journeys and the demand on it is continuously increasing. Transit and walking modes are related to each other as transit passengers have to walk to and from transit stops. In this paper, the multi‐mode elastic‐demand network equilibrium problem is formulated as a variational inequality problem where the combined mode and route choices are modeled in a hierarchical logit structures and the total travel demand for each origin‐destination pair is explicitly given by an elastic demand function. In addition, the capacity constraint for transit vehicles and the effects of bi‐directional flows on walkways are considered in the proposed model. All these congestion effects are taken into account for modeling the travel choices. A solution algorithm is developed to solve the multi‐mode elastic‐demand network equilibrium model. It is based on a Block Gauss‐Seidel decomposition approach coupled with the method of successive averages. A numerical example is used to illustrate the application of the proposed model and solution algorithm.     

Validation of a schedule‐based capacity restraint transit assignment model for a large‐scale network

This paper describes the application of a capacity restraint trip assignment algorithm to a real, large‐scale transit network and the validation of the results. Unlike the conventional frequency‐based approach, the network formulation of the proposed model is dynamic and schedule‐based. Transit vehicles are assumed to operate to a set of pre‐determined schedules. Passengers are assumed to select paths based on a generalized cost function including in‐vehicle and out‐of‐vehicle time and line change penalty. The time‐varying passenger demand is loaded onto the network by a time increment simulation method, which ensures that the capacity restraint of each vehicle during passenger boarding is strictly observed. The optimal‐path and path‐loading algorithms are applied iteratively by the method of successive averages until the network converges to the predictive dynamic user equilibrium. The Hong Kong Mass Transit Railway network is used to validate the model results. The potential applications of the model are also discussed.     

A computational model for the probit‐based dynamic stochastic user optimal traffic assignment problem

This paper focuses on computational model development for the probit‐based dynamic stochastic user optimal (P‐DSUO) traffic assignment problem. We first examine a general fixed‐point formulation for the P‐DSUO traffic assignment problem, and subsequently propose a computational model that can find an approximated solution of the interest problem. The computational model includes four components: a strategy to determine a set of the prevailing routes between each origin–destination pair, a method to estimate the covariance of perceived travel time for any two prevailing routes, a cell transmission model‐based traffic performance model to calculate the actual route travel time used by the probit‐based dynamic stochastic network loading procedure, and an iterative solution algorithm solving the customized fixed‐point model. The Ishikawa algorithm is proposed to solve the computational model. A comparison study is carried out to investigate the efficiency and accuracy of the proposed algorithm with the method of successive averages. Two numerical examples are used to assess the computational model and the algorithm proposed. Results show that Ishikawa algorithm has better accuracy for smaller network despite requiring longer computational time. Nevertheless, it could not converge for larger network. Copyright © 2010 John Wiley & Sons, Ltd.     

Simultaneous optimization of transit line configuration and passenger line assignment

Passenger transportation in most large cities relies on an efficient mass transit system, whose line configuration has direct impacts on the system operating cost, passenger travel time and line transfers. Unfortunately, the interplay between transit line configuration and passenger line assignment has been largely ignored in the literature. This paper presents a model for simultaneous optimization of transit line configuration and passenger line assignment in a general network. The model is formulated as a linear binary integer program and can be solved by the standard branch and bound method. The model is illustrated with a couple of minimum spanning tree networks and a simplified version of the general Hong Kong mass transit railway network.     

Dynamic stochastic transit assignment with explicit seat allocation model

This paper proposes a stochastic dynamic transit assignment model with an explicit seat allocation process. The model is applicable to a general transit network. A seat allocation model is proposed to estimate the probability of a passenger waiting at a station or on-board to get a seat. The explicit seating model allows a better differentiation of in-vehicle discomfort experienced by sitting and standing passengers. The paper proposes simulation procedures for calculating the sitting probability of each type of passengers. A heuristic solution algorithm for finding an equilibrium solution of the proposed model is developed and tested. The numerical tests show significant influences of the seat allocation model on equilibrium departure time and route choices of passengers. The proposed model is also applied to evaluate the effects of an advanced public transport information system (APTIS) on travellers’ decision-making.     

An equilibration scheme for the traffic assignment problem with elastic demands

This note presents an algorithm for the solution of the traffic assignment problem with elastic demands. The algorithm is based on the concept of “equilibration operator” introduced by Dafermos and Sparrow (1969) for the solution of the traffic assignment problem with fixed demands. Computational experience is provided for linear and nonlinear problems for both the algorithm proposed here and the Dafermos-Sparrow algorithm applied to the “excess-demand” reformulations of the problems.     

弹性需求下的轨道交通客流分配模型和算法研究

文章分析了轨道交通客流需求量的影响因素,以拥挤条件下的出行阻抗函数为基础,通过引入弹性需求条件下的轨道交通均衡配流条件,构建了弹性需求的均衡配流模型。根据模型的特点,给出了改进的用于求解弹性需求下的轨道交通均衡配流模型的Frank-wolfe算法。最后通过一个算例说明了算法的有效性和合理性。     

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).     

Modeling transit technology selection in a linear transportation corridor

This paper proposes an analytical model for investigating transit technology selection problem from a perspective of transit authority. Given a transit technology alternative (e.g., metro, light rail transit, or bus rapid transit), the proposed model aims to maximize the social welfare of the transit system by determining the optimal combination of transit line length, number of stations, station location (or spacing), headway, and fare. In the proposed model, the effects of passenger demand elasticity and capacity constraint are explicitly considered. The properties of the model are examined analytically, and a heuristic solution procedure for determining the model solution is presented. By comparing the optimized social welfare for different transit technology alternatives, the optimal transit technology solution can be obtained together with critical population density. On the basis of a simple population growth rate formula, optimal investment timing of a new transit technology can be estimated. The proposed methodology is illustrated in several Chinese cities. Insightful findings are reported on the interrelation among transit technology selection, population density, transit investment cost, and transit line parameter design as well as the comparison between social welfare maximization and profit maximization regimes. Copyright © 2014 John Wiley & Sons, Ltd.     

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 schedule‐based dynamic transit network model — Recent advances and prospective future research

Using the schedule‐based approach, in which scheduled timetables are used to describe the movement of vehicles, a dynamic transit assignment model is formulated. Passengers are assumed to travel on a path with minimum generalized cost that consists of four components: in‐vehicle time; waiting time; walking time; and a time penalty for each line change. A specially developed branch and bound algorithm is used to generate the time‐dependent minimum path. The assignment procedure is conducted over a period in which both passenger demand and train headway are varying. This paper presents an overview of the research that has been carried out by the authors to develop the schedule‐based transit assignment model, and offers perspectives for future research.     

A stochastic transit assignment model using a dynamic schedule-based network

Using the schedule-based approach, in which scheduled time-tables are used to describe the movement of vehicles, a dynamic transit assignment model is formulated. Passengers are assumed to travel on a path with minimum generalized cost which consists of four components: in-vehicle time; waiting time; walking time; and a time penalty for each line change. With the exception of in-vehicle time, each of the other cost components is weighted by a sensitivity coefficient which varies among travelers and is defined by a density function. This time-dependent and stochastic minimum path is generated by a specially developed branch and bound algorithm. The assignment procedure is conducted over a period in which both passenger demand and train headways are varying. Due to the stochastic nature of the assignment problem, a Monte Carlo approach is employed to solve the problem. A case study using the Mass Transit Railway System in Hong Kong is given to demonstrate the model and its potential applications.     

A connected-vehicle-based dynamic control model for managing the bus bunching problem with capacity constraints

This paper describes a connected-vehicle-based system architecture which can provide more precise and comprehensive information on bus movements and passenger status. Then a dynamic control method is proposed using connected vehicle data. Traditionally, the bus bunching problem has been formulated into one of two types of optimization problem. The first uses total passenger time cost as the objective function and capacity, safe headway, and other factors as constraints. Due to the large number of scenarios considered, this type of framework is inefficient for real-time implementation. The other type uses headway adherence as the objective and applies a feedback control framework to minimize headway variations. Due to the simplicity in the formulation and solution algorithms, the headway-based models are more suitable for real-time transit operations. However, the headway-based feedback control framework proposed in the literature still assumes homogeneous conditions at all bus stations, and does not consider restricting passenger loads within the capacity constraints. In this paper, a dynamic control framework is proposed to improve not only headway adherence but also maintain the stability of passenger load within bus capacity in both homogenous and heterogeneous situations at bus stations. The study provides the stability conditions for optimal control with heterogeneous bus conditions and derives optimal control strategies to minimize passenger transit cost while maintaining vehicle loading within capacity constraints. The proposed model is validated with a numerical analysis and case study based on field data collected in Chengdu, China. The results show that the proposed model performs well on high-demand bus routes.     

The allocation of buses in heavily utilized networks with overlapping routes

Many transit systems outside North America are characterized by networks with extensively overlapping routes and buses frequently operating at, or close to, capacity. This paper addresses the problem of allocating a fleet of buses between routes in this type of system; a problem that must be solved recurrently by transit planners. A formulation of the problem is developed which recognizes passenger route choice behavior, and seeks to minimize a function of passenger wait time and bus crowding subject to constraints on the number of buses available and the provision of enough capacity on each route to carry all passengers who would select it. An algorithm is developed based on the decomposition of the problem into base allocation and surplus allocation components. The base allocation identifies a feasible solution using an (approx.) minimum number of buses. The surplus allocation is illustrated for the simple objective of minimizing the maximum crowding level on any route. The bus allocation procedure developed in this paper has been applied to part of the Cairo bus system in a completely manual procedure, and is proposed to be the central element of a short-range bus service planning process for that city.     

A schedule-based time-dependent trip assignment model for transit networks

A schedule-based time-dependent trip assignment model for transit networks is presented. First the transit network model is formulated using the schedule-based approach, in which the vehicles are assumed to arrive punctually in accordance with a scheduled time-table. Based on a previously developed time-dependent shortest path algorithm, an all-or-nothing network loading procedure is employed to assign the passenger trips onto the network. Both the passenger demand and scheduled time-table are time-varying. This provides a versatile tool for the evaluation of the performance of transit networks subject to peak period loading. A case study using the Mass Transit Railway System in Hong Kong is given to illustrate the potential applications of the model.     

Determining optimal frequency and vehicle capacity for public transit routes: A generalized newsvendor model

The level of service on public transit routes is very much affected by the frequency and vehicle capacity. The combined values of these variables contribute to the costs associated with route operations as well as the costs associated with passenger comfort, such as waiting and overcrowding. The new approach to the problem that we introduce combines both passenger and operator costs within a generalized newsvendor model. From the passenger perspective, waiting and overcrowding costs are used; from the operator’s perspective, the costs are related to vehicle size, empty seats, and lost sales. Maximal passenger average waiting time as well as maximal vehicle capacity are considered as constraints that are imposed by the regulator to assure a minimal public transit service level or in order to comply with other regulatory considerations. The advantages of the newsvendor model are that (a) costs are treated as shortages (overcrowding) and surpluses (empty seats); (b) the model presents simultaneous optimal results for both frequency and vehicle size; (c) an efficient and fast algorithm is developed; and (d) the model assumes stochastic demand, and is not restricted to a specific distribution. We demonstrate the usefulness of the model through a case study and sensitivity analysis.     

On seat capacity in traffic assignment to a transit network

Seating or standing make distinct on‐board states to a transit rider, yielding distinct discomfort costs, with potential influence on the passenger route choice onto the transit network. The paper provides a transit assignment model that captures the seating capacity and its occupancy along any transit route. The main assumptions pertain to: the seat capacity by service route, selfish user behaviour, a seat allocation process with priority rules among the riders, according to their prior state either on‐board or at boarding. To each transit leg from access to egress station is associated a set of ‘service modes’, among which the riders are assigned in a probabilistic way, conditionally on their priority status and the ratio between the available capacity and the flow of them. Thus the leg cost is a random variable, with mean value to be included in the trip disutility. Computationally efficient algorithms are provided for, respectively, loading the leg flows and evaluating the leg costs along a transit line. At the network level, a hyperpath formulation is provided for supply‐demand equilibrium, together with a property of existence and an method of successive averages equilibration algorithm. It is shown that multiple equilibria may arise. Copyright © 2010 John Wiley & Sons, Ltd.