Dynamic user optimal traffic assignment on congested multidestination networks

An equivalent continuous time optimal control problem is formulated to predict the temporal evolution of traffic flow pattern on a congested multiple origin-destination network, corresponding to a dynamic generalization of Wardropian user equilibrium. Optimality conditions are derived using the Pontryagin minimum principle and given economic interpretations, which are generalizations of similar results previously reported for single-destination networks. Analyses of sufficient conditions for optimality and of singular controls are also given. Under the steady-state assumptions, the model is shown to be a proper dynamic extension of Beckmann's mathematical programming problem for a static user equilibrium traffic assignment.     

A predictive dynamic traffic assignment model in congested capacity-constrained road networks

In this paper, a predictive dynamic traffic assignment model in congested capacity-constrained road networks is formulated. A traffic simulator is developed to incrementally load the traffic demand onto the network, and updates the traffic conditions dynamically. A time-dependent shortest path algorithm is also given to determine the paths with minimum actual travel time from an origin to all the destinations. The traffic simulator and time-dependent shortest path algorithm are employed in a method of successive averages to solve the dynamic equilibrium solution of the problem. A numerical example is given to illustrate the effectiveness of the proposed method.     

Estimation of origin-destination matrices from link traffic counts on congested networks

Conventional methods for estimating origin-destination (O-D) trip matrices from link traffic counts assume that route choice proportions are given constants. In a network with realistic congestion levels, this assumption does not hold. This paper shows how existing methods such as the generalized least squares technique can be integrated with an equilibrium traffic assignment in the form of a convex bilevel optimization problem. The presence of measurement errors and time variations in the observed link flows are explicitly considered. The feasibility of the model is always guaranteed without a requirement for estimating consistent link flows from counts. A solution algorithm is provided and numerical simulation experiments are implemented in investigating the model's properties. Some related problems concerning O-D matrix estimation are also discussed.     

A dynamic stochastic assignment model for the analysis of general networks

The paper adopts the framework employed by the existing dynamic assignment models, which analyse specific network forms, and develops a methodology for analysing general networks. Traffic conditions within a link are assumed to be homogeneous, and the time varying O-D travel times and traffic flow patterns are calculated using elementary relationships from traffic flow theory and link volume conservation equations. Each individual is assumed to select a departure time and a route by trading off the travel time and schedule delay associated with each alternative. A route is considered as reasonable if it includes only links which do not take the traveller back to the origin. The set of reasonable routes is not consistant but depends on the time that an individual decides to depart from his origin. Equilibrium distributions are derived from a Markovian model which describes the evolution of travel patterns from day to day. Numerical simulation experiments are conducted to analyse the impact of different work start time flexibilities on the time dependent travel patterns. The similarity between link flows and travel times obtained from static and dynamic stochastic assignment is investigated. It is shown that in congested networks the application of static assignment results in travel times which are lower than the ones predicted by dynamic assignment.     

Stochastic cell transmission model (SCTM): A stochastic dynamic traffic model for traffic state surveillance and assignment

The paper proposes a first-order macroscopic stochastic dynamic traffic model, namely the stochastic cell transmission model (SCTM), to model traffic flow density on freeway segments with stochastic demand and supply. The SCTM consists of five operational modes corresponding to different congestion levels of the freeway segment. Each mode is formulated as a discrete time bilinear stochastic system. A set of probabilistic conditions is proposed to characterize the probability of occurrence of each mode. The overall effect of the five modes is estimated by the joint traffic density which is derived from the theory of finite mixture distribution. The SCTM captures not only the mean and standard deviation (SD) of density of the traffic flow, but also the propagation of SD over time and space. The SCTM is tested with a hypothetical freeway corridor simulation and an empirical study. The simulation results are compared against the means and SDs of traffic densities obtained from the Monte Carlo Simulation (MCS) of the modified cell transmission model (MCTM). An approximately two-miles freeway segment of Interstate 210 West (I-210W) in Los Ageles, Southern California, is chosen for the empirical study. Traffic data is obtained from the Performance Measurement System (PeMS). The stochastic parameters of the SCTM are calibrated against the flow-density empirical data of I-210W. Both the SCTM and the MCS of the MCTM are tested. A discussion of the computational efficiency and the accuracy issues of the two methods is provided based on the empirical results. Both the numerical simulation results and the empirical results confirm that the SCTM is capable of accurately estimating the means and SDs of the freeway densities as compared to the MCS.     

A model of traffic dispersion from a congested road

The study of traffic flow dynamics is developed by defining and clarifying traffic divergence, continuity, congestion and dispersion. Velocity potential is introduced as a gravity function generated by the interaction of two or more motorists occupying neighbouring points in space and describes interference to continuous traffic flow. The relationship between the potential function and carrying capacity is developed and dispersion, when considered as a random walk, satisfies a diffusion equation. A model of traffic dispersion along a maximum congested road in space and time is presented as eigenfunctions of the velocity potential. This suggests that traffic can be dispersed by a series of quantum steps. A probability density function is introduced to define the probability of locating a motorist in a congestion zone.     

A comparison of user-optimum versus system-optimum traffic assignment in transportation network design

In this report, we compare the computational efficiency and results of solving two alternative models for the problem of determining improvements to an urban road network. Using a 1462 link, 584 node test network of the north Dallas area, we compare a model which assumes user-optimum behavior of travelers with a model which assumes system-optimum flows. Both of these models allow improvements to the road network to take on any nonnegative value, rather than requiring discrete improvement values. Investment costs are modeled by functions with decreasing marginal costs. Unfortunately, the user-optimum model, which is much more realistic than the system-optimum one, normally cannot be solved optimally. However, the simpler system-optimum model can be optimally solved, provided that investment costs are approximated by linear functions. Thus, for this network design problem we compare an accurate representation which can be solved only approximately with an approximate representation which can be solved optimally. Our computational testing showed that the system-optimum model produces solutions as good as those from the user-optimum model, and thus seems justified when favored by other considerations, such as ease of coding, availability of “canned” programs, etc.     

General stochastic user equilibrium traffic assignment problem with link capacity constraints

This paper addresses a general stochastic user equilibrium (SUE) traffic assignment problem with link capacity constraints. It first proposes a novel linearly constrained minimization model in terms of path flows and then shows that any of its local minimums satisfies the generalized SUE conditions. As the objective function of the proposed model involves path‐specific delay functions without explicit mathematical expressions, its Lagrangian dual formulation is analyzed. On the basis of the Lagrangian dual model, a convergent Lagrangian dual method with a predetermined step size sequence is developed. This solution method merely invokes a subroutine at each iteration to perform a conventional SUE traffic assignment excluding link capacity constraints. Finally, two numerical examples are used to illustrate the proposed model and solution method.     

Multimodal,multiclass stochastic dynamic traffic assignment for evaluating information provision strategies

A multimodal, multiclass stochastic dynamic traffic assignment model was developed to evaluate pre‐trip and enroute travel information provision strategies. Three different information strategies were examined: user optimum [UO], system optimum [SO] and mixed optimum [MO]. These information provision strategies were analyzed based on the levels of traffic congestion and market penetration rate for the information equipment. Only two modes, bus and car, were used for evaluating and calculating the modal split ratio. Several scenarios were analyzed using day‐to‐day and within day dynamic models. From the results analyzed, it was found that when a traffic manager provides information for drivers using the UO strategy and drivers follow the provided information absolutely, the total travel time may increases over the case with no information. Such worsening occurs when drivers switch their routes and face traffic congestion on the alternative route. This phenomenon is the 'Braess Paradox'.     

The dynamics of traffic assignment and traffic control: A theoretical study

The paper considers traffic assignment, with traffic controls, in an increasingly dynamic way. First, a natural way of introducing the responsive policy, P_o, into steady state traffic assignment is presented. Then it is shown that natural stability results follow within a dynamical version of this static equilibrium model (still with a constant demand). We are able to obtain similar stability results when queues are explicitly allowed for, provided demand is constant. Finally we allow demand to vary with time; we consider the dynamic assignment problem with signal-settings now fixed. Here we assume that vehicles are very short and that deterministic queueing theory applies, and show that the time-dependent queueing delay at the bottleneck at the end of a link is a monotone function of the time-dependent input profile to the bottleneck. We have been unable to obtain results when dynamic demand and responsive signal control are combined.     

A shockwave profile model for traffic flow on congested urban arterials

In this paper a new traffic flow model for congested arterial networks, named shockwave profile model (SPM), is presented. Taking advantage of the fact that traffic states within a congested link can be simplified as free-flow, saturated, and jammed conditions, SPM simulates traffic dynamics by analytically deriving the trajectories of four major shockwaves: queuing, discharge, departure, and compression waves. Unlike conventional macroscopic models, in which space is often discretized into small cells for numerical solutions, SPM treats each homogeneous road segment with constant capacity as a section; and the queuing dynamics within each section are described by tracing the shockwave fronts. SPM is particularly suitable for simulating traffic flow on congested signalized arterials especially with queue spillover problems, where the steady-state periodic pattern of queue build-up and dissipation process may break down. Depending on when and where spillover occurs along a signalized arterial, a large number of queuing patterns may be possible. Therefore it becomes difficult to apply the conventional approach directly to track shockwave fronts. To overcome this difficulty, a novel approach is proposed as part of the SPM, in which queue spillover is treated as either extending a red phase or creating new smaller cycles, so that the analytical solutions for tracing the shockwave fronts can be easily applied. Since only the essential features of arterial traffic flow, i.e., queue build-up and dissipation, are considered, SPM significantly reduces the computational load and improves the numerical efficiency. We further validated SPM using real-world traffic signal data collected from a major arterial in the Twin Cities. The results clearly demonstrate the effectiveness and accuracy of the model. We expect that in the future this model can be applied in a number of real-time applications such as arterial performance prediction and signal optimization.     

A stochastic model for highway traffic

A nonlinear model for unidirectional flow of heavy traffic on a two-lane highway is considered. Features such as entrance, exit and lane transfer with time-dependent parameters are incorporated into the model, with the result that a number of previous models employed in the study of traffic flow become special cases of ours. Using the method of system-size expansion, an asymptotic analysis of the problem, including the time evolution of both deterministic and stochastic aspects of the traffic system, is carried out. In addition, a scheme for obtaining the moments of the probability distribution for systems of finite size is developed and a comparison is made with the exact results appropriate to a particular model. The agreement between the two sets of results turns out to be remarkably good.     

Tolling traffic links under stochastic assignment: Modelling the relationship between the number and price level of tolled links and optimal traffic flows

The classical road-tolling problem is to toll network links such that under the principles of Wardropian User Equilibrium Assignment a System Optimising (SO) flow pattern is obtained. Stochastic assignment methods are accepted to be more realistic than deterministic and it is of interest to examine the potential for optimal tolling in the case of Stochastic User Equilibrium (SUE). In examining the case of Stochastic User Equilibrium the ‘desired flow pattern’ to be created must first be determined. The classical economics solution of replacing unit-cost flow functions with marginal-cost flow functions which under deterministic assignment produces the System Optimal solution (where Total Network Travel Cost (TNTC) is minimised) does not generally result in TNTC being minimised in the Stochastic Case. Instead such tolls produce a ‘Stochastic System Optimal’ (SSO) solution where the Total Perceived Network Travel Cost (TPNTC) is minimised.This paper examines and compares link-based tolling solutions to achieve both the SSO (TPNTC minimised) and true SO (TNTC minimised) under SUE and illustrates the concept with numerical examples. Such link-based tolling schemes produce network benefit by re-routing rather than traffic suppression as opposed to the cordon-based charging schemes which have been implemented in practice. Equity issues relating to charging schemes are discussed and the desirability of zero-toll routes is highlighted associated with greater potential political acceptability of charging schemes that do not impose excessive charges upon users (such as minimal or low revenue tolls). A heuristic is developed to toll network links in such a way as to balance the number of links tolled against the revenue required to produce a desired reduction in TNTC such that optimal network flow patterns are approached.     

Evidence of convective instability in congested traffic flow: A systematic empirical and theoretical investigation

An extended open system such as traffic flow is said to be convectively unstable if perturbations of the stationary state grow but propagate in only one direction, so they eventually leave the system. By means of data analysis, simulations, and analytical calculations, we give evidence that this concept is relevant for instabilities of congested traffic flow. We analyze detector data from several hundred traffic jams and propose estimates for the linear growth rate, the wavelength, the propagation velocity, and the severity of the associated bottleneck that can be evaluated semi-automatically. Scatter plots of these quantities reveal systematic dependencies. On the theoretical side, we derive, for a wide class of microscopic and macroscopic traffic models, analytical criteria for convective and absolute linear instabilities. Based on the relative positions of the stability limits in the fundamental diagram, we divide these models into five stability classes which uniquely determine the set of possible elementary spatiotemporal patterns in open systems with a bottleneck. Only two classes, both dominated by convective instabilities, are compatible with observations. By means of approximate solutions of convectively unstable systems with sustained localized noise, we show that the observed spatiotemporal phenomena can also be described analytically. The parameters of the analytical expressions can be inferred from observations, and also (analytically) derived from the model equations.     

Validation of traffic flow models with respect to the spatiotemporal evolution of congested traffic patterns

We propose a quantitative approach for calibrating and validating key features of traffic instabilities based on speed time series obtained from aggregated data of a series of neighboring stationary detectors. The approach can be used to validate models that are calibrated by other criteria with respect to their collective dynamics. We apply the proposed criteria to historic traffic databases of several freeways in Germany containing about 400 occurrences of congestions thereby providing a reference for model calibration and quality assessment with respect to the spatiotemporal dynamics. First tests with microscopic and macroscopic models indicate that the criteria are both robust and discriminative, i.e., clearly distinguishes between models of higher and lower predictive power.     

Junction interactions and monotonicity in traffic assignment

We consider the traffic equilibrium problem when the travel demand is inelastic and stationary in time. Junction interactions, which abound in urban road networks, are permitted. We prove that the set of equilibria (solutions to the assignment problem) is convex when certain monotonicity and continuity conditions are statisfied at each junction.     

A stochastic model of traffic flow: Theoretical foundations

In a variety of applications of traffic flow, including traffic simulation, real-time estimation and prediction, one requires a probabilistic model of traffic flow. The usual approach to constructing such models involves the addition of random noise terms to deterministic equations, which could lead to negative traffic densities and mean dynamics that are inconsistent with the original deterministic dynamics. This paper offers a new stochastic model of traffic flow that addresses these issues. The source of randomness in the proposed model is the uncertainty inherent in driver gap choice, which is represented by random state dependent vehicle time headways. A wide range of time headway distributions is allowed. From the random time headways, counting processes are defined, which represent cumulative flows across cell boundaries in a discrete space and continuous time conservation framework. We show that our construction implicitly ensures non-negativity of traffic densities and that the fluid limit of the stochastic model is consistent with cell transmission model (CTM) based deterministic dynamics.     

A dynamic traffic assignment model for a continuum transportation system

A predictive continuum dynamic user-optimal (PDUO-C) model is formulated in this study to investigate the dynamic characteristics of traffic flow and the corresponding route-choice behavior of travelers within a region with a dense urban road network. The modeled region is arbitrary in shape with a single central business district (CBD) and travelers continuously distributed over the region. Within this region, the road network is represented as a continuum and travelers patronize a two-dimensional continuum transportation system to travel to the CBD. The PDUO-C model is solved by a promising solution algorithm that includes elements of the finite volume method (FVM), the finite element method (FEM), and the explicit total variation diminishing Runge-Kutta (TVD-RK) time-stepping method. A numerical example is given to demonstrate the utility of the proposed model and the effectiveness of the solution algorithm in solving this PDUO-C problem.     

A modified Frank-Wolfe algorithm for solving the traffic assignment problem

This paper presents a very simple modification of the Frank-Wolfe algorithm for the solution of the traffic assignment problem. It is shown that the modified algorithm can be implemented without much increase in computational effort over the original one. Convergence of the algorithm is proved and computational results are reported to demonstrate the validity of the modification.     

Equilibrium analysis of the scheduling of tours in congested networks

In this paper, we develop a model of travel in tours that joins several locations by travel through a congested network. We develop a microscopic analysis in continuous time of individual benefits obtained by spending time at each of the locations and costs incurred through travel between them. This is combined with a continuous time macroscopic equilibrium model of travel during congested peak periods to show how individuals' travel choices are influenced by the congestion that result from corresponding choices made by others. We show how different travellers can achieve identical net utilities by making different combinations of choices within the equilibrium. The resulting model can be used to investigate the effect on travel behaviour and individual utility of various transport interventions, and we illustrate this by considering the effect of a peak‐period charge that eliminates congestion.