SWUTC Research Project Description
Boundary Conditions Estimation on a Road Network Using Compressed Sensing
University: University of Texas at Austin
Principal Investigator:
Christian Claudel
Department of Civil and Environmental Engineering
(512) 705-7195
Project Monitor:
Guillaume Costeseque
INRIA Sophia Antipolis Mediterranee
ACUMES Team
Valbonne, France
Funding Source: USDOT
Total Project Cost: $50,093
Project Number: 600451-00090
Date Started: 6/1/15
Estimated Completion Date: 12/31/15
Project Summary
Project Abstract:
Controlling the traffic on a road network requires the knowledge of both the current initial conditions (initial distribution of traffic) and the boundary conditions (demand and supply patterns) that will be applied to the network. In this project, our objective is to formulate the problem of estimating historical boundary conditions on a road network using the classical Lighthill Whitham Richards (LWR) partial differential equation (PDE) in conjunction with density, speed, flow and travel time data. Using a semi-analytical formulation of the solutions to the PDE, our objective is to pose the problem of estimating the boundary flows as an optimization problem. Since this problem is expected to be largely undetermined, L1 regularization (or compressed sensing) will be applied to select a unique, likely solution. The performance of this framework will be validated on an experimental traffic dataset.
Project Objectives:
The primary objective of this study is to create a framework for estimating the demand and supply functions at the boundaries of an arbitrary traffic network, using arbitrary traffic measurement data. This framework should use a combination of semi-analytical formulations of the solutions to the LWR PDE, and constraints related to measurement data. To simplify this problem, we assume that no model uncertainty is present (though measurement uncertainty can exist).
The second objective of this study is to validate this framework on an experimental dataset (for instance a traffic network dataset obtained from the PeMS system). The performance of the demand/supply estimation scheme will be evaluated by separating the sensor data measurements in two set: a set used by the demand/supply estimation framework, and a set for validation that consists in flow measurements from on and off-ramp sensors, which are common in the PeMS system.
Task Descriptions:
Task 1: Literature review of network boundary condition estimation algorithms
Perform a comprehensive review of relevant literature associated with boundary condition estimation in networks, and the associated O/D matrix estimation problem. The literature review will be used to determine relevant objective functions that can be used in the estimation framework, as well as relevant regularization parameters and scales.
Task 2: Develop an optimization framework for boundary condition estimation on a single link
Use the Lax-Hopf formulas to determine the constraints arising at the boundaries of a single link, and build a feasibility problem to determine what the feasible inflows and outflows on a link are, given measurement data.
Task 3: Extension to networks
Extend the optimization formulation of task 2 on networks, given junction models and arbitrary splitting coefficients. The junction models are expected to yield mixed integer linear constraints in flows, and the network boundary flow feasibility problem should yield a mixed integer linear program.
Task 4: Determination of relevant objective functions
Extend the optimization formulation of task 3 (which involves a feasibility analysis only) to select solutions minimizing an objective function. Objective functions will be determined from task 1, and will consist in the difference between the computed boundary demand and supplies (given the constraints from the flow model and measurement data) and the expected load resulting from daily driving.
Task 5: Validation
The optimization formulation developed as part of task 4 will be validated on an actual road network. Our objective is to choose a well instrumented, large scale network in which flow, density and/or travel time measurements are available on large sections of the network. To evaluate the performance of this scheme in practice, the measurement dataset will be separated in two. The flow measurement data from on and off ramps will be used as a validation set (ground truth), and the rest of the dataset will be used in the optimization scheme. The PeMS data generated in California seems a promising datset, particularly on the SF-Bay area or around Los Angeles.
Task 6: Preparation of comprehensive final report
The final research report will provide a complete description of the problem, approach, methodology, findings, conclusions, and recommendations, developed in the project and will completely document all data gathered, analyses performed, and results achieved.
Implementation of Research Outcomes:
This project is one of the first attempts to aid traffic engineers by integrating traffic flow models with the complex problem of estimating boundary conditions (demand and supply patterns) on a road network. Using a compressed sensing approach, we can regularize this underdetermined problem and find unique solutions that exhibit a low number of features over time and space.
Products developed by this research:
Software: This research developed software for integrating traffic flow data with models, for the purpose of boundary condition estimation.
New Technique: A new technique for solving the boundary estimation problem, based on Mixed Integer Linear programming was developed. The researchers do not anticipate sharing this technique right now, though we will include it in a future journal article submission.
Impacts/Benefits of Implementation:
The results of this research may make an impact on socioeconomic conditions, since better estimation of O/D matrices may lead to reduced traffic congestion through better traffic control. The integration of models into the problem may help (if computationally tractable) to address the fundamental issue of a lack of data to solve such problems.
Web Links:
Final Technical Report