A discrete dynamical system of formulating traffic assignment: Revisiting Smith’s model

Through relaxing the behavior assumption adopted in Smith’s model (Smith, 1984), we propose a discrete dynamical system to formulate the day-to-day evolution process of traffic flows from a non-equilibrium state to an equilibrium state. Depending on certain preconditions, the equilibrium state can be equivalent to a Wardrop user equilibrium (UE), Logit-based stochastic user equilibrium (SUE), or boundedly rational user equilibrium (BRUE). These equivalence properties indicate that, to make day-to-day flows evolve to equilibrium flows, it is not necessary for travelers to choose their routes based on actual travel costs of the previous day. Day-to-day flows can still evolve to equilibrium flows provided that travelers choose their routes based on estimated travel costs which satisfy these preconditions. We also show that, under a more general assumption than the monotonicity of route cost function, the trajectory of the dynamical system converges to a set of equilibrium flows by reasonably setting these parameters in the dynamical system. Finally, numerical examples are presented to demonstrate the application and properties of the dynamical system. The study is helpful for understanding various processes of forming traffic jam and designing an algorithm for calculating equilibrium flows.     

Modeling the evolutions of day‐to‐day route choice and year‐to‐year ATIS adoption with stochastic user equilibrium

Suppose that in an urban transportation network there is a specific advanced traveler information system (ATIS) which acts for reducing the drivers' travel time uncertainty through provision of pre‐trip route information. Because of the imperfect information provided, some travelers are not in compliance with the ATIS advice although equipped with the device. We thus divide all travelers into three groups, one group unequipped with ATIS, another group equipped and in compliance with ATIS advice and the third group equipped but without compliance with the advice. Each traveler makes route choice in a logit‐based manner and a stochastic user equilibrium with multiple user classes is reached for every day. In this paper, we propose a model to investigate the evolutions of daily path travel time, daily ATIS compliance rate and yearly ATIS adoption, in which the equilibrium for every day's route choice is kept. The stability of the evolution model is initially analyzed. Numerical results obtained from a test network are presented for demonstrating the model's ability in depicting the day‐to‐day and year‐to‐year evolutions.     

Modeling and solving discrete network design problem with stochastic user equilibrium

In this paper, we address the discrete network design problem, which determines the addition of new roads to existing transportation network to optimize the transportation system performance. Road users are assumed to follow the traffic assignment principle of stochastic user equilibrium. A mixed‐integer nonlinear nonconvex problem is developed to model this discrete network design problem with stochastic user equilibrium. The original problem is relaxed into a convex mixed‐integer nonlinear program, whose solution provides a lower bound of the original problem. The relaxed problem is then embedded into two proposed global optimization solution algorithms to obtain the global optimal solution of the problem. Copyright © 2016 John Wiley & Sons, Ltd.     

A review of models for the temporal distribution of peak traffic demand

The existing models for predicting the temporal distribution of peak traffic demand are reviewed in this paper. Based on their assumptions and concepts, the models are classified into three groups as follows: deterministic user equilibrium (DUE), stochastic user equilibrium (SUE) and system optimum (SO). The merits and weaknesses of each group are discussed with regards to the validity of their assumptions and computational problems associated with them. Most of the models were developed for the single origin-destination pair with simple network system which is an oversimplification of a practical problem involving multiple origin-destination pairs with complex network systems. This is a major limitation when considering the application of the existing models to real life problems. Directions for future research are then proposed.     

Global optimization method for network design problem with stochastic user equilibrium

In this paper, we consider the continuous road network design problem with stochastic user equilibrium constraint that aims to optimize the network performance via road capacity expansion. The network flow pattern is subject to stochastic user equilibrium, specifically, the logit route choice model. The resulting formulation, a nonlinear nonconvex programming problem, is firstly transformed into a nonlinear program with only logarithmic functions as nonlinear terms, for which a tight linear programming relaxation is derived by using an outer-approximation technique. The linear programming relaxation is then embedded within a global optimization solution algorithm based on range reduction technique, and the proposed approach is proved to converge to a global optimum.     

Modeling and optimizing urban bus transit considering headway variation for cost and service reliability analysis

Due to the stochastic nature of traffic conditions and demand fluctuations, it is a challenging task for operators to maintain reliable services, and passengers often suffer from longer travel times. A failure to consider this issue while planning bus services may lead to undesirable results, such as higher costs and a deterioration in level of service. Considering headway variation at route stops, this paper develops a mathematical model to optimize bus stops and dispatching headways that minimize total cost, consisting of both user and operator costs. A Genetic Algorithm is applied to search for a cost-effective solution in a real-world case study of a bus transit system, which improves service reliability in terms of a reduced coefficient of variation of headway.     

A reliability‐based network design problem

This paper presents a reliability‐based network design problem. A network reliability concept is embedded into the continuous network design problem in which travelers' route choice behavior follows the stochastic user equilibrium assumption. A new capacity‐reliability index is introduced to measure the probability that all of the network links are operated below their capacities when serving different traffic patterns deviating from the average condition. The reliability‐based network design problem is formulated as a bi‐level program in which the lower level sub‐program is the probit‐based stochastic user equilibrium problem and the upper level sub‐program is the maximization of the new capacity reliability index. The lower level sub‐program is solved by a variant of the method of successive averages using the exponential average to represent the learning process of network users on a daily basis that results in the daily variation of traffic‐flow pattern, and Monte Carlo stochastic loading. The upper level sub‐program is tackled by means of genetic algorithms. A numerical example is used to demonstrate the concept of the proposed framework.     

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.     

Formulating the within-day dynamic stochastic traffic assignment problem from a Bayesian perspective

This study proposes a formulation of the within-day dynamic stochastic traffic assignment problem. Considering the stochastic nature of route choice behavior, we treat the solution to the assignment problem as the conditional joint distribution of route traffic, given that the network is in dynamic stochastic user equilibrium. We acquire the conditional joint probability distribution using Bayes’ theorem. A Metropolis–Hastings sampling scheme is developed to estimate the characteristics (e.g., mean and variance) of the route traffic. The proposed formulation has no special requirements for the traffic flow models and user behavior models, and so is easily implemented.     

On the flexibility of using marginal distribution choice models in traffic equilibrium

Traffic equilibrium models are fundamental to the analysis of transportation systems. The stochastic user equilibrium (SUE) model which relaxes the perfect information assumption of the deterministic user equilibrium is one such model. The aim of this paper is to develop a new user equilibrium model, namely the MDM-SUE model, that uses the marginal distribution model (MDM) as the underlying route choice model. In this choice model, the marginal distributions of the path utilities are specified but the joint distribution is not. By focusing on the joint distribution that maximizes expected utility, we show that MDM-SUE exists and is unique under mild assumptions on the marginal distributions. We develop a convex optimization formulation for the MDM-SUE. For specific choices of marginal distributions, the MDM-SUE model recreates the optimization formulation of logit SUE and weibit SUE. Moreover, the model is flexible since it can capture perception variance scaling at the route level and allows for modeling different user preferences by allowing for skewed distributions and heavy tailed distributions. The model can also be generalized to incorporate bounded support distributions and discrete distributions which allows to distinguish between used and unused routes within the SUE framework. We adapt the method of successive averages to develop an efficient approach to compute MDM-SUE traffic flows. In our numerical experiments, we test the ability of MDM-SUE to relax the assumption that the error terms are independently and identically distributed random variables as in the logit models and study the additional modeling flexibility that MDM-SUE provides on small-sized networks as well as on the large network of the city of Winnipeg. The results indicate that the model provides both modeling flexibility and computational tractability in traffic equilibrium.     

A reliability‐based traffic assignment model for multi‐modal transport network under demand uncertainty

In densely populated and congested urban areas, the travel times in congested multi‐modal transport networks are generally varied and stochastic in practice. These stochastic travel times may be raised from day‐to‐day demand fluctuations and would affect travelers' route and mode choice behaviors according to their different expectations of on‐time arrival. In view of these, this paper presents a reliability‐based user equilibrium traffic assignment model for congested multi‐modal transport networks under demand uncertainty. The stochastic bus frequency due to the unstable travel time of bus route is explicitly considered. By the proposed model, travelers' route and mode choice behaviors are intensively explored. In addition, a stochastic state‐augmented multi‐modal transport network is adopted in this paper to effectively model probable transfers and non‐linear fare structures. A numerical example is given to illustrate the merits of the proposed model. Copyright © 2012 John Wiley & Sons, Ltd.     

Comparative analysis of three user equilibrium models under stochastic demand

Recent empirical studies on the value of time and reliability reveal that travel time variability plays an important role on travelers' route choice decision process. It can be considered as a risk to travelers making a trip. Therefore, travelers are not only interested in saving their travel time but also in reducing their risk. Typically, risk can be represented by two different aspects: acceptable risk and unacceptable risk. Acceptable risk refers to the reliability aspect of acceptable travel time, which is defined as the average travel time plus the acceptable additional time (or buffer time) needed to ensure more frequent on‐time arrivals, while unacceptable risk refers to the unreliability aspect of unacceptable late arrivals (though infrequent) that have a travel time excessively higher than the acceptable travel time. Most research in the network equilibrium based approach to modeling travel time variability ignores the unreliability aspect of unacceptable late arrivals. This paper examines the effects of both reliability and unreliability aspects in a network equilibrium framework. Specifically, the traditional user equilibrium model, the demand driven travel time reliability‐based user equilibrium model, and the α‐reliable mean‐excess travel time user equilibrium model are considered in the investigation under an uncertain environment due to stochastic travel demand. Numerical results are presented to examine how these models handle risk under travel time variability.     

Distributed computing approaches for large‐scale probit‐based stochastic user equilibrium problems

Applications of probit‐based stochastic user equilibrium (SUE) principle on large‐scale networks have been largely limited because of the overwhelming computational burden in solving its stochastic network loading problem. A two‐stage Monte Carlo simulation method is recognized to have satisfactory accuracy level when solving this stochastic network loading. This paper thus works on the acceleration of the Monte Carlo simulation method via using distributed computing system. Three distributed computing approaches are then adopted on the workload partition of the Monte Carlo simulation method. Wherein, the first approach allocates each processor in the distributed computing system to solve each trial of the simulation in parallel and in turns, and the second approach assigns all the processors to solve the shortest‐path problems in one trial of the Monte Carlo simulation concurrently. The third approach is a combination of the first two, wherein both different trials of the Monte Carlo simulation as well as the shortest path problems in one trial are solved simultaneously. Performances of the three approaches are comprehensively tested by the Sioux‐Falls network and then a randomly generated network example. It shows that computational time for the probit‐based SUE problem can be largely reduced by any of these three approaches, and the first approach is found out to be superior to the other two. The first approach is then selected to calculate the probit‐based SUE problem on a large‐scale network example. Copyright © 2011 John Wiley & Sons, Ltd.     

A day-to-day route flow evolution process towards the mixed equilibria

This study investigates a travelers’ day-to-day route flow evolution process under a predefined market penetration of advanced traveler information system (ATIS). It is assumed that some travelers equipped with ATIS will follow the deterministic user equilibrium route choice behavior due to the complete traffic information provided by ATIS, while the other travelers unequipped with ATIS will follow the stochastic user equilibrium route choice behavior. The interaction between these two groups of travelers will result in a mixed equilibrium state. We first propose a discrete day-to-day route flow adjustment process for this mixed equilibrium behavior by specifying the travelers’ route adjustment principle and adjustment ratio. The convergence of the proposed day-to-day flow dynamic model to the mixed equilibrium state is then rigorously demonstrated under certain assumptions upon route adjustment principle and adjustment ratio. In addition, without affecting the convergence of the proposed day-to-day flow dynamic model, the assumption concerning the adjustment ratio is further relaxed, thus making the proposed model more appealing in practice. Finally, numerical experiments are conducted to illustrate and evaluate the performance of the proposed day-to-day flow dynamic model.     

First-best marginal cost toll for a traffic network with stochastic demand

First-best marginal cost pricing (MCP) in traffic networks has been extensively studied with the assumption of deterministic travel demand. However, this assumption may not be realistic as a transportation network is exposed to various uncertainties. This paper investigates MCP in a traffic network under stochastic travel demand. Cases of both fixed and elastic demand are considered. In the fixed demand case, travel demand is represented as a random variable, whereas in the elastic demand case, a pre-specified random variable is introduced into the demand function. The paper also considers a set of assumptions of traveler behavior. In the first case, it is assumed that the traveler considers only the mean travel time in the route choice decision (risk-neutral behavior), and in the second, both the mean and the variance of travel time are introduced into the route choice model (risk-averse behavior). A closed-form formulation of the true marginal cost toll for the stochastic network (SN-MCP) is derived from the variational inequality conditions of the system optimum and user equilibrium assignments. The key finding is that the calculation of the SN-MCP model cannot be made by simply substituting related terms in the original MCP model by their expected values. The paper provides a general function of SN-MCP and derives the closed-form SN-MCP formulation for specific cases with lognormal and normal stochastic travel demand. Four numerical examples are explored to compare network performance under the SN-MCP and other toll regimes.     

Bounded rationality and irreversible network change

A network change is said to be irreversible if the initial network equilibrium cannot be restored by revoking the change. The phenomenon of irreversible network change has been observed in reality. To model this phenomenon, we develop a day-to-day dynamic model whose fixed point is a boundedly rational user equilibrium (BRUE) flow. Our BRUE based approach to modeling irreversible network change has two advantages over other methods based on Wardrop user equilibrium (UE) or stochastic user equilibrium (SUE). First, the existence of multiple network equilibria is necessary for modeling irreversible network change. Unlike UE or SUE, the BRUE multiple equilibria do not rely on non-separable link cost functions, which makes our model applicable to real-world large-scale networks, where well-calibrated non-separable link cost functions are generally not available. Second, travelers’ boundedly rational behavior in route choice is explicitly considered in our model. The proposed model is applied to the Twin Cities network to model the flow evolution during the collapse and reopening of the I-35 W Bridge. The results show that our model can to a reasonable level reproduce the observed phenomenon of irreversible network change.     

An integrated, dynamic approach to travel demand forecasting

This paper presents a unified approach for improving travel demand models through the application and extension of supernetwork models of multi-dimensional travel choices. Proposed quite some time ago, supernetwork models solved to stochastic user equilibrium can provide a simultaneous solution to trip generation, distribution, mode choice, and assignment that is consistent with disaggregate models and predicts their aggregate effects. The extension to incorporate the time dimension through the use of dynamic equilibrium assignment methods is proposed as an enhancement that is necessary in order to produce realistic models. A variety of theoretical and practical problems are identified whose solution underlies implementation of this approach. Recommended future research includes improved algorithms for stochastic and dynamic equilibrium assignment, new methods for calibrating assignment models, and the use of Geographic Information Systems (GIS) technology for data and model management.     

Direct formulation and algorithms for the probit-based stochastic user equilibrium traffic assignment problem

This paper proposes simple and direct formulation and algorithms for the probit-based stochastic user equilibrium traffic assignment problem. It is only necessary to account for random variables independent of link flows by performing a simple transformation of the perceived link travel time with a normal distribution. At every iteration of a Monte-Carlo simulation procedure, the values of the random variables are sampled based on their probability distributions, and then a regular deterministic user equilibrium assignment is carried out to produce link flows. The link flows produced at each iteration of the Monte-Carlo simulation are averaged to yield the final flow pattern. Two test networks demonstrate that the proposed algorithms and the traditional algorithm (the Method of Successive Averages) produce similar results and that the proposed algorithms can be extended to the computation of the case in which the random error term depends on measured travel time.     

A day-to-day and within-day dynamic stochastic assignment model

In this article a doubly dynamis assignment model for a general network is presented. It is assumed that users' choices are based on information about travel times and generalized transportation costs occurred in a finite number of previous days and, possibly, in previous periods of the same day. The information may be supplied and managed by an informative system. In this context, path and link flows vary for different subperiods of the same day (within-day dynamics) and for different days (day-to-day dynamics). The proposed model follows a nonequilibrium approach in which both within-day and day-to-day flow fluctuations are modelled as a stochastic process. A model of dynamic network loading for computing within-day variable arc flows from path flows is also presented. The model deals explicitly with queuing at oversaturated intersections and can be formulated as a fixed point problem. A solution scheme for the doubly dynamic assignment model is presented embedding a solution algorithm for the fixed-point problem.