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.     

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.     

Toll sequence operation to realize target flow pattern under bounded rationality

Because boundedly rational user equilibrium (BRUE) always has a set of solutions instead of a unique one, from a static network equilibrium viewpoint, under BRUE there is no guarantee of attainability of any specific target flow by implementing tolls. In this study, from a disequilibrium flow evolution perspective, we design toll sequence operations (TS-operations) to guide the network flow to evolve towards the traditional Wardrop user equilibrium (UE) flow pattern. Under homogeneous bounded rationality (BR), iteratively implementing our TS-operations can make the network flow pattern converge to UE, which essentially solves the nonuniqueness problem of BRUE and re-establishes the effectiveness of link tolls in realizing any target link flow pattern. In particular we show that under homogenous BR the best-case untolled link-based BRUE can be realized as the untolled equilibrium. Under heterogeneous BR among different OD pairs, our TS-operations can make the flow converge to reduced BRUE and/or sub-network UE, which give smaller estimate intervals of the equilibrium flow pattern as compared to the original BRUE.     

Effects of queue spillover in networks considering simultaneous departure time and route choices

This paper explores the effects of queue spillover in transportation networks, in the context of dynamic traffic assignment. A model of spatial queue is defined to characterize dynamic traffic flow and queuing formation in network links. Network users simultaneously choose departure time and travel route to minimize the travel cost including journey time and unpunctuality penalty. Using some necessary conditions of the dynamic user equilibrium, dynamic network flows are obtained exactly on some networks with typical structure. Various effects of queue spillover are discussed based on the results of these networks, and some new paradoxes of link capacity expansion have been found as a result of such effects. Analytical and exact results in these typical networks show that ignoring queuing length may generate biased solutions, and the link storage capacity is a very important factor concerning the performance of networks.     

Global optimization methods for the discrete network design problem

This paper addresses the discrete network design problem (DNDP) with multiple capacity levels, or multi-capacity DNDP for short, which determines the optimal number of lanes to add to each candidate link in a road network. We formulate the problem as a bi-level programming model, where the upper level aims to minimize the total travel time via adding new lanes to candidate links and the lower level is a traditional Wardrop user equilibrium (UE) problem. We propose two global optimization methods by taking advantage of the relationship between UE and system optimal (SO) traffic assignment principles. The first method, termed as SO-relaxation, exploits the property that an optimal network design solution under SO principle can be a good approximate solution under UE principle, and successively sorts the solutions in the order of increasing total travel time under SO principle. Optimality is guaranteed when the lower bound of the total travel time of the unexplored solutions under UE principle is not less than the total travel time of a known solution under UE principle. The second method, termed as UE-reduction, adds the objective function of the Beckmann-McGuire-Winsten transformation of UE traffic assignment to the constraints of the SO-relaxation formulation of the multi-capacity DNDP. This constraint is convex and strengthens the SO-relaxation formulation. We also develop a dynamic outer-approximation scheme to make use of the state-of-the-art mixed-integer linear programming solvers to solve the SO-relaxation formulation. Numerical experiments based on a two-link network and the Sioux-Falls network are conducted.     

Accounting for dynamic speed limit control in a stochastic traffic environment: A reinforcement learning approach

This paper proposes a novel dynamic speed limit control model accounting for uncertain traffic demand and supply in a stochastic traffic network. First, a link based dynamic network loading model is developed to simulate the traffic flow propagation allowing the change of speed limits. Shockwave propagation is well defined and captured by checking the difference between the queue forming end and the dissipation end. Second, the dynamic speed limit problem is formulated as a Markov Decision Process (MDP) problem and solved by a real time control mechanism. The speed limit controller is modeled as an intelligent agent interacting with the stochastic network environment stochastic network environment to assign time dependent link based speed limits. Based on different metrics, e.g. total network throughput, delay time, vehicular emissions are optimized in the modeling framework, the optimal speed limit scheme is obtained by applying the R-Markov Average Reward Technique (R-MART) based reinforcement learning algorithm. A case study of the Sioux Falls network is constructed to test the performance of the model. Results show that the total travel time and emissions (in terms of CO) are reduced by around 18% and 20% compared with the base case of non-speed limit control.     

How tube strikes affect macroscopic and link travel times in London

Abstract

The purpose of this study was to investigate the impact of the five strikes on the London Underground (metro) rail system, which occurred in 2009 and 2010, on macroscopic and road link travel times. A consequence of these strikes was an increase in road traffic flows above usual levels. This provides an opportunity to observe the operation of the road network under unusually high flows. The first objective involves the examination of strike effects on inbound (IT) and outbound traffic (OT) within central, inner and outer London. Travel time data obtained from automatic number plate recognition cameras are used within the first part of the analysis. The second more detailed objective was to investigate in spatio-temporal effects on travel times on five road links. Correlation analyses and general linear models are developed using both traffic flow and travel time data. According to the results of the study, the morning IT had approximately twice as much delay as the OT. Central London experienced the highest delays, followed by inner and outer London. As would be expected, the unique full-day strike in 2009 yielded the worst impact on the network with the highest percentage increase in total travel time (60%) occurring during the morning peak in the IT in inner London. The results from the link-level analysis showed statistical significance amongst the examined links indicating heterogeneous effects from one link to another. It was also found that travel time changes may be more effectively captured through time-of-day terms compared to hourly traffic flows.     

Learning marginal-cost pricing via a trial-and-error procedure with day-to-day flow dynamics

This paper investigates the convergence of the trial-and-error procedure to achieve the system optimum by incorporating the day-to-day evolution of traffic flows. The path flows are assumed to follow an ‘excess travel cost dynamics’ and evolve from disequilibrium states to the equilibrium day by day. This implies that the observed link flow pattern during the trial-and-error procedure is in disequilibrium. By making certain assumptions on the flow evolution dynamics, we prove that the trial-and-error procedure is capable of learning the system optimum link tolls without requiring explicit knowledge of the demand functions and flow evolution mechanism. A methodology is developed for updating the toll charges and choosing the inter-trial periods to ensure convergence of the iterative approach towards the system optimum. Numerical examples are given in support of the theoretical findings.     

Dynamic user equilibrium with side constraints for a traffic network: Theoretical development and numerical solution algorithm

This paper investigates a traffic volume control scheme for a dynamic traffic network model which aims to ensure that traffic volumes on specified links do not exceed preferred levels. The problem is formulated as a dynamic user equilibrium problem with side constraints (DUE-SC) in which the side constraints represent the restrictions on the traffic volumes. Travelers choose their departure times and routes to minimize their generalized travel costs, which include early/late arrival penalties. An infinite-dimensional variational inequality (VI) is formulated to model the DUE-SC. Based on this VI formulation, we establish an existence result for the DUE-SC by showing that the VI admits at least one solution. To analyze the necessary condition for the DUE-SC, we restate the VI as an equivalent optimal control problem. The Lagrange multipliers associated with the side constraints as derived from the optimality condition of the DUE-SC provide the traffic volume control scheme. The control scheme can be interpreted as additional travel delays (either tolls or access delays) imposed upon drivers for using the controlled links. This additional delay term derived from the Lagrange multiplier is compared with its counterpart in a static user equilibrium assignment model. If the side constraint is chosen as the storage capacity of a link, the additional delay can be viewed as the effort needed to prevent the link from spillback. Under this circumstance, it is found that the flow is incompressible when the link traffic volume is equal to its storage capacity. An algorithm based on Euler’s discretization scheme and nonlinear programming is proposed to solve the DUE-SC. Numerical examples are presented to illustrate the mechanism of the proposed traffic volume control scheme.     

Travel time estimation for urban road networks using low frequency probe vehicle data

The paper presents a statistical model for urban road network travel time estimation using vehicle trajectories obtained from low frequency GPS probes as observations, where the vehicles typically cover multiple network links between reports. The network model separates trip travel times into link travel times and intersection delays and allows correlation between travel times on different network links based on a spatial moving average (SMA) structure. The observation model presents a way to estimate the parameters of the network model, including the correlation structure, through low frequency sampling of vehicle traces. Link-specific effects are combined with link attributes (speed limit, functional class, etc.) and trip conditions (day of week, season, weather, etc.) as explanatory variables. The approach captures the underlying factors behind spatial and temporal variations in speeds, which is useful for traffic management, planning and forecasting. The model is estimated using maximum likelihood. The model is applied in a case study for the network of Stockholm, Sweden. Link attributes and trip conditions (including recent snowfall) have significant effects on travel times and there is significant positive correlation between segments. The case study highlights the potential of using sparse probe vehicle data for monitoring the performance of the urban transport system.     

Mechanisms that govern how the Price of Anarchy varies with travel demand

Selfish routing, represented by the User-Equilibrium (UE) model, is known to be inefficient when compared to the System Optimum (SO) model. However, there is currently little understanding of how the magnitude of this inefficiency, which can be measured by the Price of Anarchy (PoA), varies across different structures of demand and supply. Such understanding would be useful for both transport policy and network design, as it could help to identify circumstances in which policy interventions that are designed to induce more efficient use of a traffic network, are worth their costs of implementation.This paper identifies four mechanisms that govern how the PoA varies with travel demand in traffic networks with separable and strictly increasing cost functions. For each OD movement, these are expansions and contractions in the sets of routes that are of minimum cost under UE and minimum marginal total cost under SO. The effects of these mechanisms on the PoA are established via a combination of theoretical proofs and conjectures supported by numerical evidence. In addition, for the special case of traffic networks with BPR-like cost functions having common power, it is proven that there is a systematic relationship between link flows under UE and SO, and hence between the levels of demand at which expansions and contractions occur. For this case, numerical evidence also suggests that the PoA has power law decay for large demand.     

Multi-class percentile user equilibrium with flow-dependent stochasticity

Travelers often reserve a buffer time for trips sensitive to arrival time in order to hedge against the uncertainties in a transportation system. To model the effects of such behavior, travelers are assumed to choose routes to minimize the percentile travel time, i.e. the travel time budget that ensures their preferred probability of on-time arrival; in doing so, they drive the system to a percentile user equilibrium (UE), which can be viewed as an extension of the classic Wardrop equilibrium. The stochasticity in the supply of transportation are incorporated by modeling the service flow rate of each road segment as a random variable. Such stochasticity is flow-dependent in the sense that the probability density functions of these random variables, from which the distribution of link travel time are constructed, are specified endogenously with flow-dependent parameters. The percentile route travel time, obtained by directly convolving the link travel time distributions in this paper, is not available in closed form in general and has to be numerically evaluated. To reveal their structural properties, percentile UE solutions are examined in special cases and verified with numerical results. For the general multi-class percentile UE traffic assignment problem, a variational inequality formulation is given and solved using a route-based algorithm. The algorithm makes use of the diagonal elements in the Jacobian of percentile route travel time, which is approximated through recursive convolution. Preliminary numerical experiments indicate that the algorithm is able to achieve highly precise equilibrium solutions.     

Identification of vehicle sensor locations for link-based network traffic applications

Information on link flows in a vehicular traffic network is critical for developing long-term planning and/or short-term operational management strategies. In the literature, most studies to develop such strategies typically assume the availability of measured link traffic information on all network links, either through manual survey or advanced traffic sensor technologies. In practical applications, the assumption of installed sensors on all links is generally unrealistic due to budgetary constraints. It motivates the need to estimate flows on all links of a traffic network based on the measurement of link flows on a subset of links with suitably equipped sensors. This study, addressed from a budgetary planning perspective, seeks to identify the smallest subset of links in a network on which to locate sensors that enables the accurate estimation of traffic flows on all links of the network under steady-state conditions. Here, steady-state implies that the path flows are static. A “basis link” method is proposed to determine the locations of vehicle sensors, by using the link-path incidence matrix to express the network structure and then identifying its “basis” in a matrix algebra context. The theoretical background and mathematical properties of the proposed method are elaborated. The approach is useful for deploying long-term planning and link-based applications in traffic networks.     

A traffic flow simulator for network reliability assessment

This paper investigates the transportation network reliability based on the information provided by detectors installed on some links. A traffic flow simulator (TFS) model is formulated for assessing the network reliability (in terms of travel time reliability), in which the variation of perceived travel time error and the fluctuations of origin-destination (OD) demand are explicitly considered. On the basis of prior OD demand and partial updated detector data, the TFS can estimate the link flows for the whole network together with link/path travel times, and their variance and covariance. The travel time reliability by OD pair can also be assessed and the OD matrix can be updated simultaneously. A Monte Carlo based algorithm is developed to solve the TFS model. The application of the proposed TFS model is illustrated by a numerical example.     

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.     

A graphical approach to identify sensor locations for link flow inference

Information of link flows in a traffic network becomes increasingly critical in contemporary transportation practice and researches. The network sensor installation is carried out to supply such information. In this paper, we present a graphical approach to determine the smallest subset of links in a traffic network for counting sensor installation, so as to infer the flows on all remaining links. The elegant assumption-free character of the problem introduced by Hu, Peeta and Chu is still kept in this approach. This study points out the topological tree feature of solutions that makes it possible for traffic management agencies to easily and flexibly select links for sensor installation in practice. Addressing from the same graphical perspective, we provide solutions to four other important problems about sensor locations. The preceding two problems are, in traffic networks that already have sensors installed on some links, to identify the subset of links on which link flows can be inferred from sensor measurements and to determine the smallest subset of links on which counting sensors also need to be installed so as to infer link flows on all remaining non-equipped links. The third is to identify the optimal locations for a given number of sensors so as to infer flows on as many links as possible by gradually enlarging the number of links included in circuits. The last one is to determine the smallest subset of links on which to install sensors, in such a way that it becomes possible at the same time to satisfy prior requirements and infer the flows on all remaining links, through building a minimum spanning tree. These methods can be applied to all kinds of long-term planning and link-based applications in traffic networks.     

Effect of speed limits in degradable transport networks

This paper studies how link-specific speed limits influence the performance of degradable transport networks, in which the capacity of each link is a degradable random variable. The distribution and cumulative distribution of link travel time have been presented with the effect of speed limits taken into account. The mean and variance of link and route travel time are formulated. Three link states have been classified, and their physical meanings have been discussed. The relationship between critical capacity, travel time and speed limit has been elaborated. We have proposed a Speed Limit- and Reliability-based User Equilibrium (SLRUE), adopting travel time budget as the principle of travelers’ route choice. A heuristic method employing the method of successive averages is developed to solve the SLRUE in degradable networks. Through numerical studies, we find that for some networks both the mean and standard deviation of the total travel time could be reduced simultaneously by imposing some speed limits. The speed limit design problem has been studied, and it is found that imposing speed limits cannot always reduce the total travel time budget of a network.     

Decomposing travel times measured by probe-based traffic monitoring systems to individual road segments

In probe-based traffic monitoring systems, traffic conditions can be inferred based on the position data of a set of periodically polled probe vehicles. In such systems, the two consecutive polled positions do not necessarily correspond to the end points of individual links. Obtaining estimates of travel time at the individual link level requires the total traversal time (which is equal to the polling interval duration) be decomposed. This paper presents an algorithm for solving the problem of decomposing the traversal time to times taken to traverse individual road segments on the route. The proposed algorithm assumes minimal information about the network, namely network topography (i.e. links and nodes) and the free flow speed of each link. Unlike existing deterministic methods, the proposed solution algorithm defines a likelihood function that is maximized to solve for the most likely travel time for each road segment on the traversed route. The proposed scheme is evaluated using simulated data and compared to a benchmark deterministic method. The evaluation results suggest that the proposed method outperforms the bench mark method and on average improves the accuracy of the estimated link travel times by up to 90%.     

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

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

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.