Global convergence of the trial-and-error method for the traffic-restraint congestion-pricing scheme with day-to-day flow dynamics

The traffic-restraint congestion-pricing scheme (TRCPS) aims to maintain traffic flow within a desirable threshold for some target links by levying the appropriate link tolls. In this study, we propose a trial-and-error method using observed link flows to implement the TRCPS with the day-to-day flow dynamics. Without resorting to the origin–destination (O–D) demand functions, link travel time functions and value of time (VOT), the proposed trial-and-error method works as follows: tolls for the traffic-restraint links are first implemented each time (trial) and they are subsequently updated using observed link flows in a disequilibrium state at any arbitrary time interval. The trial-and-error method has the practical significance because it is necessary only to observe traffic flows on those tolled links and it does not require to wait for the network flow pattern achieving the user equilibrium (UE) state. The global convergence of the trial-and-error method is rigorously demonstrated under mild conditions. We theoretically show the viability of the proposed trial-and-error method, and numerical experiments are conducted to evaluate its performance. The result of this study, without doubt, enhances the confidence of practitioners to adopt this method.     

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.     

Physics of day-to-day network flow dynamics

This paper offers a new look at the network flow dynamics from the viewpoint of physics by demonstrating that the traffic system, in terms of the aggregate effects of human behaviors, may exhibit like a physical system. Specifically, we look into the day-to-day evolution of network flows that arises from travelers’ route choices and their learning behavior on perceived travel costs. We show that the flow dynamics is analogous to a damped oscillatory system. The concepts of energies are introduced, including the potential energy and the kinetic energy. The potential energy, stored in each link, increases with the traffic flow on that link; the kinetic energy, generated by travelers’ day-to-day route swapping, is proportional to the square of the path flow changing speed. The potential and kinetic energies are converted to each other throughout the whole flow evolution, and the total system energy keeps decreasing owing to travelers’ tendency to stay on their current routes, which is analogous to the damping of a physical system. Finally, the system will approach the equilibrium state with minimum total potential energy and zero kinetic energy. We prove the stability of the day-to-day dynamics and provide numerical experiments to elucidate the interesting findings.     

Road pricing for congestion control with unknown demand and cost functions

It is widely recognized that precise estimation of road tolls for various pricing schemes requires a few pieces of information such as origin–destination demand functions, link travel time functions and users’ valuations of travel time savings, which are, however, not all readily available in practice. To circumvent this difficulty, we develop a convergent trial-and-error implementation method for a particular pricing scheme for effective congestion control when both the link travel time functions and demand functions are unknown. The congestion control problem of interest is also known as the traffic restraint and road pricing problem, which aims at finding a set of effective link toll patterns to reduce link flows to below a desirable target level. For the generalized traffic equilibrium problem formulated as variational inequalities, we propose an iterative two-stage approach with a self-adaptive step size to update the link toll pattern based on the observed link flows and given flow restraint levels. Link travel time and demand functions and users’ value of time are not needed. The convergence of the iterative toll adjustment algorithm is established theoretically and demonstrated on a set of numerical examples.     

Continuous price and flow dynamics of tradable mobility credits

This study examines the price and flow dynamics under a tradable credit scheme, when the credits can be traded in a free market. A continuous dynamic model in a finite time horizon is proposed to describe the travelers’ learning behavior and the evolution of network flows and credit price, and then the existence and uniqueness of the equilibria are established. The conditions for stability and convergence of the dynamic system as the time horizon extends to infinity and the impact of limited implementation time horizon on the system behavior are investigated.     

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.     

Node modeling for congested urban road networks

First-order network flow models are coupled systems of differential equations which describe the build-up and dissipation of congestion along network road segments, known as link models. Models describing flows across network junctions, referred to as node models, play the role of the coupling between the link models and are responsible for capturing the propagation of traffic dynamics through the network. Node models are typically stated as optimization problems, so that the coupling between the link dynamics is not known explicitly. This renders network flow models analytically intractable. This paper examines the properties of node models for urban networks. Solutions to node models that are free of traffic holding, referred to as holding-free solutions, are formally defined and it is shown that flow maximization is only a sufficient condition for holding-free solutions. A simple greedy algorithm is shown to produce holding-free solutions while also respecting the invariance principle. Staging movements through nodes in a manner that prevents conflicting flows from proceeding through the nodes simultaneously is shown to simplify the node models considerably and promote unique solutions. The staging also models intersection capacities in a more realistic way by preventing unrealistically large flows when there is ample supply in the downstream and preventing artificial blocking when some of the downstream supplies are restricted.     

Convergence of the Frank-Wolfe method for certain bounded variable traffic assignment problems

In two recent papers published in Transportation Research, Daganzo presented a modification of the Frank-Wolfe algorithm to solve certain link capacitated traffic assignment problems satisfying certain conditions. In order to show convergence of the modified algorithm, the assumption was made that the integral of the volume delay formula for each link tends to infinity as the link flow approaches the link capacity. In this paper we give a Theorem which establishes convergence of the modified algorithm under much weaker conditions. This result is then used to show convergence if the objective function of the assignment model is sufficiently large (not necessarily infinite) when the link flows are at capacity. Thus the modified method is applicable to a broader class of assignment problems. Two numerical examples illustrate (a) when the method converges and when it does not, and (b) that our Theorem provides a weaker condition for convergence of the method.     

On the variance of recurrent traffic flow for statistical traffic assignment

This paper generalizes and extends classical traffic assignment models to characterize the statistical features of Origin-Destination (O-D) demands, link/path flow and link/path costs, all of which vary from day to day. The generalized statistical traffic assignment (GESTA) model has a clear multi-level variance structure. Flow variance is analytically decomposed into three sources, O-D demands, route choices and measurement errors. Consequently, optimal decisions on roadway design, maintenance, operations and planning can be made using estimated probability distributions of link/path flow and system performance. The statistical equilibrium in GESTA is mathematically defined. Its multi-level statistical structure well fits large-scale data mining techniques. The embedded route choice model is consistent with the settings of O-D demands considering link costs that vary from day to day. We propose a Method of Successive Averages (MSA) based solution algorithm to solve for GESTA. Its convergence and computational complexity are analyzed. Three example networks including a large-scale network are solved to provide insights for decision making and to demonstrate computational efficiency.     

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.     

Dynamic congestion pricing with day-to-day flow evolution and user heterogeneity

This paper investigates evolutionary implementation of congestion pricing schemes to minimize the system cost and time, measured in monetary and time units, respectively, with the travelers’ day-to-day route adjustment behavior and their heterogeneity. The travelers’ heterogeneity is captured by their value-of-times. First, the multi-class flow dynamical system is proposed to model the travelers’ route adjustment behavior in a tolled transportation network with multiple user classes. Then, the stability condition and properties of equilibrium is examined. We further investigate the trajectory control problem via dynamic congestion pricing scheme to derive the system cost, time optimum, and generally, Pareto optimum in the sense of simultaneous minimization of system cost and time. The trajectory control problem is modeled by a differential–algebraic system with the differential sub-system capturing the flow dynamics and the algebraic one capturing the pricing constraint. The explicit Runge–Kutta method is proposed to calculate the dynamic flow trajectories and anonymous link tolls. The method allows the link tolls to be updated with any predetermined periods and forces the system cost and/or time to approach the optimum levels. Both analytical and numerical examples are adopted to examine the efficiency of the method.     

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.     

Interactive travel choices and traffic forecast in a doubly dynamical system with user inertia and information provision

This study models the joint evolution (over calendar time) of travelers’ departure time and mode choices, and the resulting traffic dynamics in a bi-modal transportation system. Specifically, we consider that, when adjusting their departure time and mode choices, travelers can learn from their past travel experiences as well as the traffic forecasts offered by the smart transport information provider/agency. At the same time, the transport agency can learn from historical data in updating traffic forecast from day to day. In other words, this study explicitly models and analyzes the dynamic interactions between transport users and traffic information provider. Besides, the impact of user inertia is taken into account in modeling the traffic dynamics. When exploring the convergence of the proposed model to the dynamic bi-modal commuting equilibrium, we find that appropriate traffic forecast can help the system converge to the user equilibrium. It is also found that user inertia might slow down the convergence speed of the day-to-day evolution model. Extensive sensitivity analysis is conducted to account for the impacts of inaccurate parameters adopted by the transport agency.     

Trial-and-error method for congestion pricing scheme under side-constrained probit-based stochastic user equilibrium conditions

A toll pattern that can restrict link flows on the tolled links to some predetermined thresholds is named as effective toll solution, which can be theoretically obtained by solving a side-constraint traffic assignment problem. Considering the practical implementation, this paper investigates availability of an engineering-oriented trial-and-error method for the effective toll pattern of cordon-based congestion pricing scheme, under side-constrained probit-based stochastic user equilibrium (SUE) conditions. The trial-and-error method merely requires the observed traffic counts on each entry of the cordon. A minimization model for the side-constrained probit-based SUE problem with elastic demand is first proposed and it is shown that the effective toll solution equals to the product of value of time and optimal Lagrangian multipliers with respect to the side constraints. Then, employing the Lagrangian dual formulation of the minimization method, this paper has built a convergent trial-and-error method. The trial-and-error method is finally tested by a numerical example developed from the cordon-based congestion pricing scheme in Singapore.     

Bayesian inference for day-to-day dynamic traffic models

There is significant current interest in the development of models to describe the day-to-day evolution of traffic flows over a network. We consider the problem of statistical inference for such models based on daily observations of traffic counts on a subset of network links. Like other inference problems for network-based models, the critical difficulty lies in the underdetermined nature of the linear system of equations that relates link flows to the latent path flows. In particular, Bayesian inference implemented using Markov chain Monte Carlo methods requires that we sample from the set of route flows consistent with the observed link flows, but enumeration of this set is usually computationally infeasible.We show how two existing conditional route flow samplers can be adapted and extended for use with day-to-day dynamic traffic. The first sampler employs an iterative route-by-route acceptance–rejection algorithm for path flows, while the second employs a simple Markov model for traveller behaviour to generate candidate entire route flow patterns when the network has a tree structure. We illustrate the application of these methods for estimation of parameters that describe traveller behaviour based on daily link count data alone.     

Limits and perspectives of effective O–D matrix correction using traffic counts

Correction of the O–D matrix from traffic counts is a classical procedure usually adopted in transport engineering by practitioners for improving the overall reliability of transport models. Recently, Papola and Marzano [Papola, A., Marzano, V., 2006. How can we trust in the O–D matrix correction procedure using traffic counts? In: Proceedings of the 2006 ETC Conference, Strasbourg] showed through laboratory experiments that this procedure is generally unable to provide for effective correction of the O–D matrix. From a theoretical standpoint, this result can be justified by the lower number of (stochastic) equations (independent observed link flows) with respect to the unknowns (O–D flows). This paper first confirms that this represents the main reason for the failure of this procedure, showing that satisfactory correction is generally obtained when the number of equations is greater than the number of unknowns. Then, since this circumstance does not occur in practice, where the number of O–D pairs usually far exceeds the number of link counts, we explore alternative assumptions and contexts, allowing for a proper balance between unknowns and equations. This can be achieved by moving to within-day dynamic contexts, where a much larger number of equations are generally available. In order to bound the corresponding increase in the number of unknowns, specific reasonable hypotheses on O–D flow variation across time slices must be introduced. In this respect, we analyze the effectiveness of the O–D matrix correction procedure in the usually adopted linear hypothesis on the dynamic process evolution of O–D flows and under the assumption of constant distribution shares. In the second case it is shown that satisfactory corrections can be performed using a small number of time slices of up to 3 min in length, leading to a time horizon in which the hypothesis of constant distribution shares can be regarded as trustworthy and realistic.     

Mesoscopic simulation of a dynamic link loading process

Passing from path flows to link flows requires non-linear and complex flow propagation models known as network loading models. In specific technical literature, different approaches have been used to study Dynamic Network Loading models, depending on whether the link performances are expressed in an aggregate or disaggregate way, and how vehicles are traced. When vehicle movements are traced implicitly and link performances are expressed in an aggregate way, the approach is macroscopic. When vehicle movements are traced explicitly, two cases are possible, depending on whether link performances are expressed in a disaggregate or aggregate way. In the first case, the approach is microscopic, otherwise it is mesoscopic.In this paper, a mesoscopic Dynamic Network Loading model is considered, based on discrete packets and taking into account the vehicle acceleration and deceleration. A simulation was carried out, first using theoretical input data to simulate over-saturation condition, and then real data to validate the model. The results show that the model appears realistic in the representation of outflow dynamics and is quite easy to calculate. It is worth noting that network loading models are usually used downstream of the assignment models from which they take path flows to calculate link flows. In the above mentioned simulation, we assumed that a generic assignment model provides sinusoidal path flow.     

An intersection turning movement estimation procedure based on path flow estimator

Estimation of intersection turning movements is one of the key inputs required for a variety of transportation analysis, including intersection geometric design, signal timing design, traffic impact assessment, and transportation planning. Conventional approaches that use manual techniques for estimation of turning movements are insensitive to congestion. The drawbacks of the manual techniques can be amended by integrating a network traffic model with a computation procedure capable of estimating turning movements from a set of link traffic counts and intersection turning movement counts. This study proposes using the path flow estimator, originally used to estimate path flows (hence origin–destination flows), to derive not only complete link flows, but also turning movements for the whole road network given some counts at selected roads and intersections. Two case studies using actual traffic counts are used to demonstrate the proposed intersection turning movement estimation procedure. Copyright © 2010 John Wiley & Sons, Ltd.     

On the convergence of iterative methods for the distribution balancing problem

A general distribution balancing problem, specified by the given outflows and inflows and the factorial form of its solution, is formulated. Solution uniqueness and boundedness is discussed—primarily in graph theoretical terms. An entropy maximisation problem, subject to general linear constraints, is transformed into an unconstrained optimisation problem by application of standard duality theory, and a relevant general convergence theorem for iterative solution methods is given. The optimum solution in a special case is identified with the flow solution. When expressed in flow variables, the dual objective has a unique and bounded optimum solution and is an appropriate unifying concept for measuring the rate of convergence of different solution methods. By regarding the balancing procedure as an iterative optimisation method, a new and simple proof of its convergence is given, together with some asymptotic results, which are also compared with those of Newton's method. It is pointed out that there are two different forms of Newton's method, according to the choice of variables—untransformed or transformed— in the original distribution balancing problem. When Newton's method is applied to the whole system of equations simultaneously, the trajectory of iterates is observed to depend on this variable choice. For the transformed variables it is noticed that the convergence with the balancing procedure is quicker than with Newton's method applied to the outflow- and inflow- equations, alternately. To guarantee global convergence with Newton's method and to increase the rate a supplementary linear search routine is recommended.     

Speed or spacing? Cumulative variables,and convolution of model errors and time in traffic flow models validation and calibration

This paper proves that in traffic flow model calibration and validation the cumulative sum of a variable has to be preferred to the variable itself as a measure of performance. As shown through analytical relationships, model residuals dynamics are preserved if discrepancy measures of a model against reality are calculated on a cumulative variable, rather than on the variable itself. Keeping memory of model residuals occurrence times is essential in traffic flow modelling where the ability of reproducing the dynamics of a phenomenon – as a bottleneck evolution or a vehicle deceleration profile – may count as much as the ability of reproducing its order of magnitude. According to the aforesaid finding, in a car-following models context, calibration on travelled space is more robust than calibration on speed or acceleration. Similarly in case of macroscopic traffic flow models validation and calibration, cumulative flows are to be preferred to flows. Actually, the findings above hold for any dynamic model.