ITS Berkeley

A Dual Decomposition Method for Sector Capacity Constrained Traffic Flow Optimization

Sun, Dengfeng
Clinet, Alexis
Bayen, Alexandre M.
2011

An aggregate air traffic flow model based on a multicommodity network is used for traffic flow management in the National Airspace System. The problem of minimizing the total travel time of flights in the National Airspace System of the United States, subject to sector capacity constraints, is formulated as an Integer Program. The resulting solution achieves optimal delay control. The Integer Program implemented for the scenarios investigated has billions of variables and constraints. It is relaxed to a Linear Program for computational efficiency. A dual decomposition method is...

State Estimation and Modeling Error Approach for 2-D Shallow Water Equations and Lagrangian Measurements

Tossavainen, Olli‐Pekka
Percelay, Julie
Stacey, Mark
Kaipio, Jari P.
Bayen, Alexandre M.
2011

A state estimation method for two-dimensional shallow water equations (SWE) in rivers using Lagrangian drifter positions as measurements is proposed. Lagrangian drifters are sensors moving with the flow and reporting their location. The aim of this method is to compensate for the lack of accurate information about boundary conditions. The drifters move with the local flow and report their positions. Thus, they provide additional information about the state of the river compared to a case in which, for example, only a computational model is used to describe the river flow. In this work, the...

A General Phase Transition Model for Vehicular Traffic

Blandin, S.
Work, D.
Goatin, P.
Piccoli, B.
Bayen, A.
2011

This paper provides a mathematical model of the phenomenon of phase transitions in traffic flow. The model consists of a scalar conservation law coupled with a 2 × 2 system of conservation laws. The coupling is achieved via a free boundary, where the phase transition takes place. For this model, the Riemann problem is stated and globally solved. The Cauchy problem is proved to admit a solution defined globally in time without any assumption about the smallness of the initial data or the number of phase boundaries. Qualitative properties of real traffic flow are shown to agree with...

Convex Formulations of Data Assimilation Problems for a Class of Hamilton–Jacobi Equations

Claudel, Christian G.
Bayen, Alexandre M.
2011

Extending and improving some recent results of Hantoute, López, and Zălinescu and others, we provide characterization conditions for subdifferential formulas to hold for the supremum function of a family of convex functions on a real locally convex space.

A Tractable Class of Algorithms for Reliable Routing in Stochastic Networks

Samaranayake, S.
Blandin, S.
Bayen, A.
2012

The goal of this article is to provide the theoretical basis for enabling tractable solutions to the “arriving on time” problem and enabling its use in real-time mobile phone applications. Optimal routing in transportation networks with highly varying traffic conditions is a challenging problem due to the stochastic nature of travel-times on links of the network. The definition of optimality criteria and the design of solution methods must account for the random nature of the travel-time on each link. Most common routing algorithms consider the expected value of link travel-time as a...

Combined State-Parameter Estimation for Shallow Water Equations

Rafiee, Mohammad
Tinka, Andrew
Thai, Jérôme
Bayen, Alexandre M.
2011

In this article, a method for assimilating data into the shallow water equations when some of the model parameters are unknown is presented. The one dimensional Saint-Venant equations are used as a model of water flow in open channels. Using these equations, a nonlinear state space model is obtained. Lagrangian measurements of the flow velocity field are used as observations or measurements. These measurements may be obtained from a group of drifters equipped with GPS receivers and communication capabilities which move with the flow and report their position at every time step. Using the...

Mobile Millennium: GPS Mobile Phones as Traffic Probes, California Networked Traveler - Safe Trip 21 Phase II

Bayen, Alexander M.
2011

Recent advances in mobile devices and internet technology have led the California Department of Transportation (Caltrans) to investigate a data collection solution that offers improved data reliability and availability at a significantly lower cost. It has been postulated that information from GPS cell phones could provide position and speed data -- referred to as probe data -- for highways and arterials in near real time over much of the transportation network. The Mobile Millennium project was established to determine if the collection and use of probe data for traveler information...

An Adaptive Routing System for Location-Aware Mobile Devices on the Road Network

Borokhov, Paul
Blandin, Sébastien
Samaranayake, Samitha
Goldschmidt, Olivier
Bayen, Alexandre M.
2011

As congestion problems become a greater concern and negatively impact society, solutions which alleviate them are needed to improve the performance of the transportation system. Routing systems which take into account the travel-time experienced by the driver have been largely unexplored in the domain of adaptive routing. In this article, we present a system which enables users of smartphones to obtain directions generated using an algorithm which provides an optimal routing policy for reliable on-time arrival; that is, directions which seek to maximize the probability of arriving to the...

Optimal Decomposition of Travel Times Measured by Probe Vehicles Using a Statistical Traffic Flow Model

Hofleitner, A.
Bayen, A.
2011

Sparse location measurements of probe vehicles are a promising data source for arterial traffic monitoring. One common challenge in processing this source of data is that vehicles are sampled infrequently (on the order of once per minute), which means that many vehicles will travel several links of the network between consecutive measurements. In this article, we propose an optimal decomposition of path travel times of probe vehicles to link travel times for each link traversed. From a model of arterial traffic dynamics, we derive probability distributions of travel times. We prove that...

Scaling the Mobile Millennium System in the Cloud

Hunter, Timothy
Moldovan, Teodor
Zaharia, Matei
Merzgui, Samy
Bayen, Alexandre M.
2011

We report on our experience scaling up the Mobile Millennium traffic information system using cloud computing and the Spark cluster computing framework. Mobile Millennium uses machine learning to infer traffic conditions for large metropolitan areas from crowdsourced data, and Spark was specifically designed to support such applications. Many studies of cloud computing frameworks have demonstrated scalability and performance improvements for simple machine learning algorithms. Our experience implementing a real-world machine learning-based application corroborates such benefits, but we...