High-resolution numerical relaxation approximations to second-order macroscopic traffic flow models

A novel numerical approach for the approximation of several, widely applied, macroscopic traffic flow models is presented. A relaxation-type approximation of second-order non-equilibrium models, written in conservation or balance law form, is considered. Using the relaxation approximation, the nonlinear equations are transformed to a semi-linear diagonilizable problem with linear characteristic variables and stiff source terms. To discretize the resulting relaxation system, low- and high-resolution reconstructions in space and implicit–explicit Runge–Kutta time integration schemes are considered. The family of spatial discretizations includes a second-order MUSCL scheme and a fifth-order WENO scheme, and a detailed formulation of the scheme is presented. Emphasis is given on the WENO scheme and its performance for solving the different traffic models. To demonstrate the effectiveness of the proposed approach, extensive numerical tests are performed for the different models. The computations reported here demonstrate the simplicity and versatility of relaxation schemes as solvers for macroscopic traffic flow models.     

A variational formulation for higher order macroscopic traffic flow models of the GSOM family

The GSOM (Generic second order modelling) family of traffic flow models combines the LWR model with dynamics of driver-specific attributes and can be expressed as a system of conservation laws. The object of the paper is to show that a proper Lagrangian formulation of the GSOM model can be recast as a Hamilton–Jacobi equation, the solution of which can be expressed as the value function of an optimal control problem. This value function is interpreted as the position of vehicles, and the optimal trajectories of the optimal control formulation can be identified with the characteristics. Further the paper analyzes the initial and boundary conditions, proposes a generalization of the inf-morphism and the Lax–Hopf formulas to the GSOM model, and considers numerical aspects.     

The Aw–Rascle and Zhang’s model: Vacuum problems,existence and regularity of the solutions of the Riemann problem

In this paper we will discuss some aspects of the recent macroscopic models of the second-order proposed by [Aw, A., Rascle, M., 2000. Resurrection of second order models of traffic flow. SIAM Journal of Applied Mathematics 60 (3), 916–938] and [Zhang, H.M., 2002. A non-equilibrium traffic model devoid of gas-like behavior. Transportation Research Part B 36, 275–290]. These models were suggested after the publication of an article written by [Daganzo, C.F., 1995. Requiem for second-order fluid approximations of traffic flow. Transportation Research Part B 29, 277–286] showing that some classical second-order models can exhibit non-physical solutions. It is shown in this note that the ARZ (Aw–Rascle–Zhang) model respects the anisotropic character of traffic flow, that it yields physical solutions, and that vacuum problems can be solved satisfactorily, provided that the fundamental diagram (equilibrium speed–density relationship) is extended in a suitable fashion. It follows that the Riemann problem for the ARZ model with extended fundamental diagram always admits a solution, and that this solution depends continuously on the initial conditions.     

Boundedly rational user equilibria (BRUE): Mathematical formulation and solution sets

Boundedly rational user equilibria (BRUE) represent traffic flow distribution patterns where travellers can take any route whose travel cost is within an ‘indifference band’ of the shortest path cost. Those traffic flow patterns satisfying the above condition constitute a set, named the BRUE solution set. It is important to obtain all the BRUE flow patterns, because it can help predict the variation of the link flow pattern in a traffic network under the boundedly rational behavior assumption. However, the methodology of constructing the BRUE set has been lacking in the established literature. This paper fills the gap by constructing the BRUE solution set on traffic networks with fixed demands. After defining ε-BRUE, where ε is the indifference band for the perceived travel cost, we formulate the ε-BRUE problem as a nonlinear complementarity problem (NCP), so that a BRUE solution can be obtained by solving a BRUE–NCP formulation. To obtain the BRUE solution set encompassing all BRUE flow patterns, we propose a methodology of generating acceptable path set which may be utilized under the boundedly rational behavior assumption. We show that with the increase of the indifference band, the acceptable path set that contains boundedly rational equilibrium flows will be augmented, and the critical values of indifference band to augment these path sets can be identified by solving a family of mathematical programs with equilibrium constraints (MPEC) sequentially. The BRUE solution set can then be obtained by assigning all traffic demands to the acceptable path set. Various numerical examples are given to illustrate our findings.     

Phase transition model of non-stationary traffic flow: Definition,properties and solution method

We consider the problem of modeling traffic phenomena at a macroscopic level. Increasing availability of streaming probe data allowing the observation of non-stationary traffic motivates the development of models capable of leveraging this information. We propose a phase transition model of non-stationary traffic in conservation form, capable of propagating joint measurements from fixed and mobile sensors, to model complex traffic phenomena such as hysteresis and phantom jams, and to account for forward propagation of information in congested traffic. The model is shown to reduce to the Lighthill–Whitham–Richards model within each traffic phase for the case of stationary states, and to have a physical mesoscopic interpretation in terms of drivers’ behavior. A corresponding discrete formulation appropriate for practical implementation is shown to provide accurate numerical solution to the proposed model. The performance of the model introduced is assessed on benchmark cases and on experimental vehicle trajectories from the NGSIM datasets.     

System optimal dynamic traffic assignment: Properties and solution procedures in the case of a many-to-one network

Thanks to its high dimensionality and a usually non-convex constraint set, system optimal dynamic traffic assignment remains one of the most challenging problems in transportation research. This paper identifies two fundamental properties of the problem and uses them to design an efficient solution procedure. We first show that the non-convexity of the problem can be circumvented by first solving a relaxed problem and then applying a traffic holding elimination procedure to obtain the solution(s) of the original problem. To efficiently solve the relaxed problem, we explore the relationship between the relaxed problems based on different traffic flow models (PQ, SQ, CTM) and a minimal cost flow (MCF) problem for a special space-expansion network. It is shown that all the four problem formulations produce the same minimal system cost and share one common solution which does not involve inside queues in the network. Efficient solution algorithms such as the network simplex method can be applied to solve the MCF problem and identify such an optimal traffic pattern. Numerical examples are also presented to demonstrate the efficiency of the proposed solution procedure.     

A partial differential equation formulation of Vickrey’s bottleneck model,part I: Methodology and theoretical analysis

This paper is concerned with the continuous-time Vickrey model, which was first introduced in Vickrey (1969). This model can be described by an ordinary differential equation (ODE) with a right-hand side which is discontinuous in the unknown variable. Such a formulation induces difficulties with both theoretical analysis and numerical computation. Moreover it is widely suspected that an explicit solution to this ODE does not exist. In this paper, we advance the knowledge and understanding of the continuous-time Vickrey model by reformulating it as a partial differential equation (PDE) and by applying a variational method to obtain an explicit solution representation. Such an explicit solution is then shown to be the strong solution to the ODE in full mathematical rigor. Our methodology also leads to the notion of generalized Vickrey model (GVM), which allows the flow to be a distribution, instead of an integrable function. As explained by Han et al. (in press), this feature of traffic modeling is desirable in the context of analytical dynamic traffic assignment (DTA). The proposed PDE formulation provides new insights into the physics of The Vickrey model, which leads to a number of modeling extensions as well as connection with first-order traffic models such as the Lighthill–Whitham–Richards (LWR) model. The explicit solution representation also leads to a new computational method, which will be discussed in an accompanying paper, Han et al. (in press).     

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.     

Information metrics for improved traffic model fidelity through sensitivity analysis and data assimilation

We develop theoretical and computational tools which can appraise traffic flow models and optimize their performance against current time-series traffic data and prevailing conditions. The proposed methodology perturbs the parameter space and undertakes path-wise analysis of the resulting time series. Most importantly the approach is valid even under non-equilibrium conditions and is based on procuring path-space (time-series) information. More generally we propose a mathematical methodology which quantifies traffic information loss.In particular the method undertakes sensitivity analysis on available traffic data and optimizes the traffic flow model based on two information theoretic tools which we develop. One of them, the relative entropy rate, can adjust and optimize model parameter values in order to reduce the information loss. More precisely, we use the relative entropy rate as an information metric between time-series data and parameterized stochastic dynamics describing a microscopic traffic model. On the other hand, the path-space Fisher Information Matrix, (pFIM) reduces model complexity and can even be used to control fidelity. This is achieved by eliminating unimportant model parameters or their combinations. This results in easier regression of parametric models with a smaller number of parameters.The method reconstructs the Markov Chain and emulates the traffic dynamics through Monte Carlo simulations. We use the microscopic interaction model from Sopasakis and Katsoulakis (2006) as a representative traffic flow model to illustrate this parameterization methodology. During the comparisons we use both synthetic and real, rush-hour, traffic data from highway US-101 in Los Angeles, California.     

Exact and grid-free solutions to the Lighthill–Whitham–Richards traffic flow model with bounded acceleration for a class of fundamental diagrams

In this article, we propose a new exact and grid-free numerical scheme for computing solutions associated with an hybrid traffic flow model based on the Lighthill–Whitham–Richards (LWR) partial differential equation, for a class of fundamental diagrams. In this hybrid flow model, the vehicles satisfy the LWR equation whenever possible, and have a constant acceleration otherwise. We first propose a mathematical definition of the solution as a minimization problem. We use this formulation to build a grid-free solution method for this model based on the minimization of component function. We then derive these component functions analytically for triangular fundamental diagrams, which are commonly used to model traffic flow. We also show that the proposed computational method can handle fixed or moving bottlenecks. A toolbox implementation of the resulting algorithm is briefly discussed, and posted at https://dl.dropbox.com/u/1318701/Toolbox.zip.     

Network equilibrium: Optimization formulations with both quantities and prices as variables

The optimization formulation of the traffic assignment problem is usually stated in terms of flow (quantity) variables but can also be stated entirely in terms of price variables (the dual formulation), and recently it has also been stated in terms of a combination of both quantity and price variables. Here we consider properties and problems associated with the latter optimization formulations and relate these formulations to the traffic equilibrium conditions and to the purely quantity formulation.     

A novel traffic signal control formulation

A novel traffic signal control formulation is developed through a mixed integer programming technique. The formulation considers dynamic traffic, uses dynamic traffic demand as input, and takes advantage of a convergent numerical approximation to the hydrodynamic model of traffic flow. As inherent from the underlying hydrodynamic model, this formulation covers the whole range of the fundamental relationships between speed, flow, and density. Kinematic waves of the stop-and-go traffic associated with traffic signals are also captured. Because of this property, one does not need to tune or switch the model for the different traffic conditions. It “automatically” adjusts to the different traffic conditions. We applied the model to three demand scenarios in a simple network. The results seemed promising. This model produced timing plans that are consistent with models that work for unsaturated conditions. In gridlock conditions, it produced a timing plan that was better than conventional queue management practices.     

A partial differential equation formulation of Vickrey’s bottleneck model,part II: Numerical analysis and computation

The Vickrey model, originally introduced in Vickrey (1969), is one of the most widely used link-based models in the current literature in dynamic traffic assignment (DTA). One popular formulation of this model is an ordinary differential equation (ODE) that is discontinuous with respect to its state variable. As explained in Ban et al., 2011, Han et al., 2013, such an irregularity induces difficulties in both continuous-time analysis and discrete-time computation. In Han et al. (2013), the authors proposed a reformulation of the Vickrey model as a partial differential equation (PDE) and derived a closed-form solution to the aforementioned ODE. This reformulation enables us to rigorously prove analytical properties of the Vickrey model and related DTA models.In this paper, we present the second of a two-part exploration regarding the PDE formulation of the Vickrey model. As proposed by Han et al. (2013), we continue research on the generalized Vickrey model (GVM) in a discrete-time framework and in the context of DTA by presenting a highly computable solution methodology. Our new computational scheme for the GVM is based on the closed-form solution mentioned above. Unlike finite-difference discretization schemes which could yield non-physical solutions (Ban et al., 2011), the proposed numerical scheme guarantees non-negativity of the queue size and the exit flow as well as first-in-first-out (FIFO). Numerical errors and convergence of the computed solutions are investigated in full mathematical rigor. As an application of the GVM, a class of network system optimal dynamic traffic assignment (SO-DTA) problems is analyzed. We show existence of a continuous-time optimal solution and propose a discrete-time mixed integer linear program (MILP) as an approximation to the original SO-DTA. We also provide convergence results for the proposed MILP approximation.     

Model and a solution algorithm for the dynamic resource allocation problem for large-scale transportation network evacuation

Allocating movable resources dynamically enables evacuation management agencies to improve evacuation system performance in both the spatial and temporal dimensions. This study proposes a mixed integer linear program (MILP) model to address the dynamic resource allocation problem for transportation evacuation planning on large-scale networks. The proposed model is built on the earliest arrival flow formulation that significantly reduces problem size. A set of binary variables, specifically, the beginning and the ending time of resource allocation at a location, enable a strong formulation with tight constraints. A solution algorithm is developed to solve for an optimal solution on large-scale network applications by adopting Benders decomposition. In this algorithm, the MILP model is decomposed into two sub-problems. The first sub-problem, called the restricted master problem, identifies a feasible dynamic resource allocation plan. The second sub-problem, called the auxiliary problem, models dynamic traffic assignment in the evacuation network given a resource allocation plan. A numerical study is performed on the Dallas–Fort Worth network. The results show that the Benders decomposition algorithm can solve an optimal solution efficiently on a large-scale network.     

Analytical and grid-free solutions to the Lighthill-Whitham-Richards traffic flow model

In this article, we propose a computational method for solving the Lighthill-Whitham-Richards (LWR) partial differential equation (PDE) semi-analytically for arbitrary piecewise-constant initial and boundary conditions, and for arbitrary concave fundamental diagrams. With these assumptions, we show that the solution to the LWR PDE at any location and time can be computed exactly and semi-analytically for a very low computational cost using the cumulative number of vehicles formulation of the problem. We implement the proposed computational method on a representative traffic flow scenario to illustrate the exactness of the analytical solution. We also show that the proposed scheme can handle more complex scenarios including traffic lights or moving bottlenecks. The computational cost of the method is very favorable, and is compared with existing algorithms. A toolbox implementation available for public download is briefly described, and posted at http://traffic.berkeley.edu/project/downloads/lwrsolver.     

Continuum modelling of transportation networks

The standard discrete transportation models, which attempt to determine traffic flow on every link of a transportation network, are inapplicable to complex dense urban networks, in view of the amount of computation involved. In this paper we adopt a radically new point of view and construct a family of models based on the assumption of continuous traffic distribution over the network. We derive the flow conservation equations and the equilibrium conditions for user-optimized and system-optimized networks.     

Dynamic network traffic control

This study developed a dynamic traffic control formulation designated as dynamic intersection signal control optimization (DISCO). Traffic in DISCO is modeled after the cell-transmission model (CTM), which is a convergent numerical approximation to the hydrodynamic model of traffic flow. It considers the entire fundamental diagram and captures traffic phenomena such as shockwaves and queue dynamics. As a dynamic approach, the formulation derives dynamic timing plans for time-variant traffic patterns. We solved DISCO based on a genetic algorithm (GA) approach and applied it to a traffic black spot in Hong Kong that is notorious for severe congestion. For performance comparisons, we also applied TRANSYT to the same scenarios. The Results showed that DISCO outperformed TRANSYT for all the scenarios tested especially in congested traffic. For the congested scenarios, DISCO could reduce delay by as much as 33% when compared with TRANSYT. Even for the uncongested scenarios, DISCO’s delays could be smaller by as much as 23%.     

Real-time airport surface movement planning: Minimizing aircraft emissions

This paper presents a study towards the development of a real-time taxi movement planning system that seeks to optimize the timed taxiing routes of all aircraft on an airport surface, by minimizing the emissions that result from taxiing aircraft operations. To resolve this online planning problem, one of the most commonly employed operations research methods for large-scale problems has been successfully used, viz., mixed-integer linear programming (MILP). The MILP formulation implemented herein permits the planning system to update the total taxi planning every 15 s, allowing to respond to unforeseen disturbances in the traffic flow. Extensive numerical experiments involving a realistic (hub) airport environment bear out that an estimated environmental benefit of 1–3 percent per emission product can be obtained. This research effort clearly demonstrates that a surface movement planning system capable of minimizing the emissions in conjunction with the total taxiing time can be beneficial for airports that face dense surface traffic and stringent environmental requirements.     

The Hamilton–Jacobi partial differential equation and the three representations of traffic flow

This paper applies the theory of Hamilton–Jacobi partial differential equations to the case of first-order traffic flow models. The traffic flow surface is analyzed with respect to the three 2-dimensional coordinate systems arising in the space of vehicle number, time and distance. In each case, the solution to the initial and boundary value problems are presented. Explicit solution methods and examples are shown for the triangular flow-density diagram case. This unveils new models and shows how a number of existing models are cast as special cases.