ITS Berkeley

Stackelberg Thresholds on Parallel Networks with Horizontal Queues

Jebbari, Yasser
Krichene, Walid
Reilly, J.
Bayen, Alexandre M.
2013

We study Stackelberg routing games on parallel networks with horizontal queues, in which a coordinator (leader) controls a fraction α of the total flow on the network, and the remaining players (followers) choose their routes selfishly. The objective of the coordinator is to minimize a system-wide cost function, the total travel-time, while anticipating the response of the followers. Nash equilibria of the routing game (with zero control) are known to be inefficient in the sense that the total travel-time is sub-optimal. Increasing the compliance rate α improves the cost of the equilibrium...

Precomputation Techniques for the Stochastic On-Time Arrival Problem

Sabran, Guillaume
Samaranayake, Samitha
Bayen, Alexandre M.
2013

We consider the stochastic on-time arrival (SOTA) problem of finding the optimal routing strategy for reaching a given destination within a pre-specified time budget and provide the first results on using preprocessing techniques for speeding up the query time. We start by identifying some properties of the SOTA problem that limit the types of preprocessing techniques that can be used in this setting, and then define the stochastic variants of two deterministic shortest path preprocessing techniques that can be adapted to the SOTA problem, namely reach and arc-flags. We present the...

Optimization-Based Queue Estimation on an Arterial Traffic Link with Measurement Uncertainties

Anderson, Leah
Canepa, Edward
Horowitz, Roberto
Claudel, Christian G.
Bayen, Alexandre
2014

Advanced monitoring and control of arterial road traffic network operations requires accurate knowledge of current and predicted performance measures on the network. Recently studied signal control algorithms, for example, use the lengths of vehicle queues for each turning movement to determine how subsequent signal cycles should be distributed into phases. This article presents a queue estimation procedure that can integrate measurements from classical count or occupancy sensors into a single physical model of general link state and queue length in particular. The authors show how...

Learning and Estimation Applications of an Online Homotopy Algorithm for a Generalization of the LASSO

Hofleitner, Aude
Rabbani, Tarek
Rafiee, Mohammad
Bayen, Alexandre M.
2014

The LASSO is a widely used shrinkage and selection method for linear regression. We propose a generalization of the LASSO in which the l1 penalty is applied on a linear transformation of the regression parameters, allowing to input prior information on the structure of the problem and to improve interpretability of the results. We also study time varying system with an l1-penalty on the variations of the state, leading to estimates that exhibit few “jumps”. We propose a homotopy algorithm that updates the solution as additional measurements are available. The algorithm takes advantage of...

Real-Time Estimation of Pollution Emissions and Dispersion from Highway Traffic

Samaranayake, Samitha
Glaser, Steven D.
Holstius, David
Monteil, Julien
Tracton, Ken
Bayen, Alexandre
2014

Traffic-related air pollution is a serious problem with significant health impacts in both urban and suburban environments. Despite an increased realization of the negative impacts of air pollution, assessing individuals' exposure to traffic-related air pollution remains a challenge. Obtaining high-resolution estimates are difficult due to the spatial and temporal variability of emissions, the dependence on local atmospheric conditions, and the lack of monitoring infrastructure. This presents a significant hurdle to identifying pollution concentration hot spots and understanding the...

Solutions to Estimation Problems for Scalar Hamilton–Jacobi Equations Using Linear Programming

Claudel, Christian G.
Chamoin, Timothée
Bayen, Alexandre M.
2014

This brief presents new convex formulations for solving estimation problems in systems modeled by scalar Hamilton-Jacobi (HJ) equations. Using a semi-analytic formula, we show that the constraints resulting from a HJ equation are convex, and can be written as a set of linear inequalities. We use this fact to pose various (and seemingly unrelated) estimation problems related to traffic flow-engineering as a set of linear programs. In particular, we solve data assimilation and data reconciliation problems for estimating the state of a system when the model and measurement constraints are...

A PDE-ODE Model for a Junction with Ramp Buffer

Delle Monache, Maria
Reilly, J.
Samaranayake, Samitha
Krichene, Walid
Goatin, Paola
Bayen, A.M.
2014

An extension of the Colombo phase transition model is proposed. The congestion phase is described by a two-dimensional zone defined around a standard fundamental diagram. General criteria for building such a set-valued fundamental diagram are enumerated and instantiated on several standard fluxes with different concavity properties. The solution to the Riemann problem in the presence of phase transitions is obtained through the design of a Riemann solver, which enables the construction of the solution of the Cauchy problem using wavefront tracking. The free-flow phase is described using a...

Calibration Framework based on Bluetooth Sensors for Traffic State Estimation Using a Velocity based Cell Transmission Model

Allström, Andreas
Bayen, Alexandre M.
Fransson, Magnus
Gundlegård, David
Patire, Anthony D.
2014

The velocity based cell transmission model (CTM-v) is a discrete time dynamical model that mimics the evolution of the traffic velocity field on highways. In this paper the CTM-v model is used together with an ensemble Kalman filter (EnKF) for the purpose of velocity sensor data assimilation. We present a calibration framework for the CTM-v and EnKF. The framework consists of two separate phases. The first phase is the calibration of the parameters of the fundamental diagram and the second phase is the calibration of demand and filter parameters. Results from the calibrated model are...

Traffic Modeling and Management: Trends and Perspectives

Bayen, Alexandre M.
Colombo, Rinaldo M.
Goatin, Paola
Piccoli, Benedetto
2014

The present issue of Discrete and Continuous Dynamical Systems -- Series S is devoted to Traffic Modeling and Management. This subject dramatically developed in recent years. On one hand, the successes of the analytical theory of conservationlaws have provided new tools to traffic researchers while, on the otherhand, the requirements coming from the applications have growndramatically. Remarkably, two of the papers that opened the way tothis decades long development date the same year. In 1995 ``The Unique Limit of the Glimm Scheme'' by A. Bressan (Archive forRational Mechanics and...

A Necessary and Sufficient Condition for the Existence of Potential Functions for Heterogeneous Routing Games

Farokhi, Farhad
Krichene, Walid
Bayen, Alexandre M.
Johansson, Karl H.
2014

We study a heterogeneous routing game in which vehicles might belong to more than one type. The type determines the cost of traveling along an edge as a function of the flow of various types of vehicles over that edge. We relax the assumptions needed for the existence of a Nash equilibrium in this heterogeneous routing game. We extend the available results to present necessary and sufficient conditions for the existence of a potential function. We characterize a set of tolls that guarantee the existence of a potential function when only two types of users are participating in the game. We...