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.     

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

A robust optimization approach for dynamic traffic signal control with emission considerations

We consider an analytical signal control problem on a signalized network whose traffic flow dynamic is described by the Lighthill–Whitham–Richards (LWR) model (Lighthill and Whitham, 1955; Richards, 1956). This problem explicitly addresses traffic-derived emissions as constraints or objectives. We seek to tackle this problem using a mixed integer mathematical programming approach. Such class of problems, which we call LWR-Emission (LWR-E), has been analyzed before to certain extent. Since mixed integer programs are practically efficient to solve in many cases (Bertsimas et al., 2011b), the mere fact of having integer variables is not the most significant challenge to solving LWR-E problems; rather, it is the presence of the potentially nonlinear and nonconvex emission-related constraints/objectives that render the program computationally expensive.To address this computational challenge, we proposed a novel reformulation of the LWR-E problem as a mixed integer linear program (MILP). This approach relies on the existence of a statistically valid macroscopic relationship between the aggregate emission rate and the vehicle occupancy on the same link. This relationship is approximated with certain functional forms and the associated uncertainties are handled explicitly using robust optimization (RO) techniques. The RO allows emissions-related constraints and/or objectives to be reformulated as linear forms under mild conditions. To further reduce the computational cost, we employ a link-based LWR model to describe traffic dynamics with the benefit of fewer (integer) variables and less potential traffic holding. The proposed MILP explicitly captures vehicle spillback, avoids traffic holding, and simultaneously minimizes travel delay and addresses emission-related concerns.     

Dynamic user equilibrium based on a hydrodynamic model

In this paper we present a continuous-time network loading procedure based on the Lighthill–Whitham–Richards model proposed by Lighthill and Whitham, 1955, Richards, 1956. A system of differential algebraic equations (DAEs) is proposed for describing traffic flow propagation, travel delay and route choices. We employ a novel numerical apparatus to reformulate the scalar conservation law as a flow-based partial differential equation (PDE), which is then solved semi-analytically with the Lax–Hopf formula. This approach allows for an efficient computational scheme for large-scale networks. We embed this network loading procedure into the dynamic user equilibrium (DUE) model proposed by Friesz et al. (1993). The DUE model is solved as a differential variational inequality (DVI) using a fixed-point algorithm. Several numerical examples of DUE on networks of varying sizes are presented, including the Sioux Falls network with a significant number of paths and origin–destination pairs (OD).The DUE model presented in this article can be formulated as a variational inequality (VI) as reported in Friesz et al. (1993). We will present the Kuhn–Tucker (KT) conditions for that VI, which is a linear system for any given feasible solution, and use them to check whether a DUE solution has been attained. In order to solve for the KT multiplier we present a decomposition of the linear system that allows efficient computation of the dual variables. The numerical solutions of DUE obtained from fixed-point iterations will be tested against the KT conditions and validated as legitimate solutions.     

A multi-commodity Lighthill–Whitham–Richards model of lane-changing traffic flow

Systematic lane changes can seriously deteriorate traffic safety and efficiency inside lane-drop, merge, and other bottleneck areas. In our previous studies (Jin, 2010a, Jin, 2010b), a phenomenological model of lane-changing traffic flow was proposed, calibrated, and analyzed based on a new concept of lane-changing intensity. In this study, we further consider weaving and non-weaving vehicles as two commodities and develop a multi-commodity, behavioral Lighthill–Whitham–Richards (LWR) model of lane-changing traffic flow. Based on a macroscopic model of lane-changing behaviors, we derive a fundamental diagram with parameters determined by car-following and lane-changing characteristics as well as road geometry and traffic composition. We further calibrate and validate fundamental diagrams corresponding to a triangular car-following fundamental diagram with NGSIM data. We introduce an entropy condition for the multi-commodity LWR model and solve the Riemann problem inside a homogeneous lane-changing area. From the Riemann solutions, we derive a flux function in terms of traffic demand and supply. Then we apply the model to study lane-changing traffic dynamics inside a lane-drop area and show that the smoothing effect of HOV lanes is consistent with observations in existing studies. The new theory of lane-changing traffic flow can be readily incorporated into Cell Transmission Model, and this study could lead to better strategies for mitigating bottleneck effects of lane-changing traffic flow.     

Development and calibration of a long-distance passenger traffic assignment model

This paper studies the assignment of long-distance passenger traffic on a highway corridor network. First, we propose a traditional model for the long-distance traffic assignment considering interactions with local commuter traffic. It addresses the effect of local networks on highway corridors. An iterative algorithm is developed to solve for the exact solution. Then, to address the potential computational issues that arise therein, a decomposition method is proposed by introducing a new concept of corridor elasticity. An assignment procedure for long-distance passenger traffic is developed accordingly. Numerical tests show that the proposed decomposition method makes significant improvements in computational performance at a small loss of optimality. This decomposition method well approximates the exact assignment from the traditional formulation, especially when the highway corridors are near-saturation. The proposed decomposition method appears practical for application.     

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.     

A bi-level model of dynamic traffic signal control with continuum approximation

This paper proposes a bi-level model for traffic network signal control, which is formulated as a dynamic Stackelberg game and solved as a mathematical program with equilibrium constraints (MPEC). The lower-level problem is a dynamic user equilibrium (DUE) with embedded dynamic network loading (DNL) sub-problem based on the LWR model (Lighthill and Whitham, 1955; Richards, 1956). The upper-level decision variables are (time-varying) signal green splits with the objective of minimizing network-wide travel cost. Unlike most existing literature which mainly use an on-and-off (binary) representation of the signal controls, we employ a continuum signal model recently proposed and analyzed in Han et al. (2014), which aims at describing and predicting the aggregate behavior that exists at signalized intersections without relying on distinct signal phases. Advantages of this continuum signal model include fewer integer variables, less restrictive constraints on the time steps, and higher decision resolution. It simplifies the modeling representation of large-scale urban traffic networks with the benefit of improved computational efficiency in simulation or optimization. We present, for the LWR-based DNL model that explicitly captures vehicle spillback, an in-depth study on the implementation of the continuum signal model, as its approximation accuracy depends on a number of factors and may deteriorate greatly under certain conditions. The proposed MPEC is solved on two test networks with three metaheuristic methods. Parallel computing is employed to significantly accelerate the solution procedure.     

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.     

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.     

The variational formulation of a non-equilibrium traffic flow model: Theory and implications

The analysis and numerical solution of non-equilibrium traffic flow models in current literature are almost exclusively carried out in the hyperbolic conservation law framework, which requires a good understanding of the delicate and non-trivial Riemann problems for conservation laws. In this paper, we present a novel formulation of certain non-equilibrium traffic flow models based on their isomorphic relation with optimal control problems. This formulation extends the minimum principle observed by the LWR model. We demonstrate that with the new formulation, generic initial-boundary conditions can be conveniently handled and a simplified numerical solution scheme for non-equilibrium models can be devised. Besides deriving the variational formulation, we provide a comprehensive discussion on its mathematical properties and physical implications.     

Comparing whole-link travel time models

In a model commonly used in dynamic traffic assignment the link travel time for a vehicle entering a link at time t is taken as a function of the number of vehicles on the link at time t. In an alternative recently introduced model, the travel time for a vehicle entering a link at time t is taken as a function of an estimate of the flow in the immediate neighbourhood of the vehicle, averaged over the time the vehicle is traversing the link. Here we compare the solutions obtained from these two models when applied to various inflow profiles. We also divide the link into segments, apply each model sequentially to the segments and again compare the results. As the number of segments is increased, the discretisation refined to the continuous limit, the solutions from the two models converge to the same solution, which is the solution of the Lighthill, Whitham, Richards (LWR) model for traffic flow. We illustrate the results for different travel time functions and patterns of inflows to the link. In the numerical examples the solutions from the second of the two models are closer to the limit solutions. We also show that the models converge even when the link segments are not homogeneous, and introduce a correction scheme in the second model to compensate for an approximation error, hence improving the approximation to the LWR model.     

Dynamic system‐optimal traffic assignment for a city using the continuum modeling approach

This paper presents a continuum dynamic traffic assignment model for a city in which the total cost of the traffic system is minimized: the travelers in the system are organized to choose the route to their destinations that minimizes the total cost of the system. Combined with the objective function, which defines the total cost and constraints such as certain physical and boundary conditions, a continuum model can be formulated as an optimization scheme with a feasible region in the function space. To obtain an admissible locally optimal solution to this problem, we first reformulate the optimization in discrete form and then introduce a heuristic method to solve it. This method converges rapidly with attractive computational cost. Numerical examples are used to demonstrate the effectiveness of the method. Copyright © 2013 John Wiley & Sons, Ltd.     

An applicatoin of an optimal traffic control during lane closure periods of a two‐lane road

On two‐lane roadways, when provision should be made for alternative one‐way movement (for construction or maintenance), the traffic characteristics differ from normal operation in which no lane is closed. The purpose of this study is to derive optimal strategies for controlling, by means of traffic signals, the one lane operation (in two‐way roadways). In this study, strategies to determine the optimal length of the closed one‐lane section during construction and maintenance work are established. This length minimizes the objective function representing the tradeoff between delay cost and operational cost. Using the length value obtained by the proposed model, plus a timing methodology, the overall cost of operating the closed highway section can be minimized. The sensitivity analysis of the optimal solution for the section length is examined with respect to the input variables. This analysis shows that for very low traffic flow values (less than 100 vph per direction), the solution is very sensitive to fuel price changes, while for greater flow values, the solution is insensitive to this change. Similar results are obtained for changes in the worker's wage which is part of both the operational and the delay cost. That is, the section's length is sensitive to wage changes at low traffic flow and insensitive otherwise. Based on the results presented in this study, it is possible to establish a guideline for the section's length determination. The control measure can emerge from a pair of traffic signals that can be installed at both ends of the closed highway segment. This traffic control system is also described in the study in terms of its components and operational features and advantages.     

Continuous equilibrium network design models

It is known that the network design problem with the assumption of user optimal flows can be modeled as a 0–1 mixed integer programming problem. Instead, we formulate the network design problem with continuous investment variables subject to equilibrium assignment as a nonlinear optimization problem. We show that this optimization problem is equivalent to an unconstrained problem which we solve by direct search techniques. For convex investment cost functions, the performance of both Powell's method and the method of Hooke and Jeeves is approximately the same with respect to computational requirements for a 24 node, 76 arc network. For the case of concave investment functions, Hooke and Jeeves was superior. The solution to the concave continuous model was very similar to that of the 0–1 model. Furthermore, the required solution time was far less than that required by the corresponding discrete model of the same network. The advantages and disadvantages of the continuous approach as well as the computational requirements are discussed.     

A multi-objective approach for Dynamic Airspace Sectorization using agent based and geometric models

A key limitation when accommodating the continuing air traffic growth is the fixed airspace structure including sector boundaries. The geometry of sectors has stayed relatively constant despite the fact that route structures and demand have changed dramatically over the past decade. Dynamic Airspace Sectorization is a concept where the airspace is redesigned dynamically to accommodate changing traffic demands. Various methods have been proposed to dynamically partition the airspace to accommodate the traffic growth while satisfying other sector constraints and efficiency metrics. However, these approaches suffer from several operational drawbacks, and their computational complexity increases fast as the airspace size and traffic volume increase. In this paper, we evaluate and identify the gaps in existing 3D sectorization methods, and propose an improved Agent Based Model (iABM) to address these gaps. We also propose three additional models using KD-Tree, Bisection and Voronoi Diagrams in 3D, to partition the airspace to satisfy the convexity constraint and reduce computational cost. We then augment these methods with a multi-objective optimization approach that uses four objectives: minimizing the variance of controller workload across the sectors, maximizing the average sector flight time, and minimizing the distance between sector boundaries and the traffic flow crossing points. Experimental results show that iABM has the best performance on workload balancing, but it is restrictive when it comes to the convexity constraint. Bisection- and Voronoi Diagram-based models perform worse than iABM on workload balancing but better on average sector flight time, and they can satisfy the convexity constraint. The KD-tree-based model has a lower computational cost, but with a poor performance on the given objectives.     

Revisiting Jiang’s dynamic continuum model for urban cities

Jiang et al. (Jiang, Y.Q., Wong, S.C., Ho, H.W., Zhang, P., Liu, R.X., Sumalee, A., 2011. A dynamic traffic assignment model for a continuum transportation system. Transportation Research Part B 45 (2), 343–363) proposed a predictive continuum dynamic user-optimaDUO-l to investigate the dynamic characteristics of traffic flow and the corresponding route-choice behavior of travelers. Their modeled region is a dense urban city that is arbitrary in shape and has a single central business district (CBD). However, we argue that the model is not well posed due to an inconsistency in the route-choice strategy under certain conditions. To overcome this inconsistency, we revisit the PDUO-C problem, and construct an improved path-choice strategy. The improved model consists of a conservation law to govern the density, in which the flow direction is determined by the improved path-choice strategy, and a Hamilton–Jacobi equation to compute the total travel cost. The simultaneous satisfaction of both equations can be treated as a fixed-point problem. A self-adaptive method of successive averages (MSA) is proposed to solve this fixed-point problem. This method can automatically determine the optimal MSA step size using the least squares approach. Numerical examples are used to demonstrate the effectiveness of the model and the solution algorithm.     

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.     

A day-to-day dynamical model for the evolution of path flows under disequilibrium of traffic networks with fixed demand

Transportation networks are often subjected to perturbed conditions leading to traffic disequilibrium. Under such conditions, the traffic evolution is typically modeled as a dynamical system that captures the aggregated effect of paths-shifts by drivers over time. This paper proposes a day-to-day (DTD) dynamical model that bridges two important gaps in the literature. First, existing DTD models generally consider current path flows and costs, but do not factor the sensitivity of path costs to flow. The proposed DTD model simultaneously captures all three factors in modeling the flow shift by drivers. As a driver can potentially perceive the sensitivity of path costs with the congestion level based on past experience, incorporating this factor can enhance real-world consistency. In addition, it smoothens the time trajectory of path flows, a desirable property for practice where the iterative solution procedure is typically terminated at an arbitrary point due to computational time constraints. Second, the study provides a criterion to classify paths for an origin–destination pair into two subsets under traffic disequilibrium: expensive paths and attractive paths. This facilitates flow shifts from the set of expensive paths to the set of attractive paths, enabling a higher degree of freedom in modeling flow shift compared to that of shifting flows only to the shortest path, which is behaviorally restrictive. In addition, consistent with the real-world driver behavior, it also helps to preclude flow shifts among expensive paths. Improved behavioral consistency can lead to more meaningful path/link time-dependent flow profiles for developing effective dynamic traffic management strategies for practice. The proposed DTD model is formulated as the dynamical system by drawing insights from micro-economic theory. The stability of the model and existence of its stationary point are theoretically proven. Results from computational experiments validate its modeling properties and illustrate its benefits relative to existing DTD dynamical models.     

Computational comparisons of algorithms for general asymmetric traffic equilibrium problems with fixed and elastic demands

In this note we compare the computational efficiency of projection and relaxation methods for the solution of the asymmetric traffic equilibrium problem with elastic demands with their computational efficiency for the fixed demand problem. In particular, we tested networks with three different classes of travel cost and travel disutility functions. Our experiments suggest that the form of the travel cost and disutility functions affects not only the relative efficiencies of these two methods but also their overall efficiencies.