Efficient algorithms for DNL and DTA as lower level component in bi-level optimization
Event details
| Date | 21.03.2014 |
| Hour | 12:15 › 13:15 |
| Speaker | Prof. Chris M.J. Tampère (KU Leuven, Belgium) |
| Location | |
| Category | Conferences - Seminars |
Many analyses require a large number of DNL/DTA runs as the lower level in a bi-level optimization: e.g. optimizing network-wide traffic control, dynamic tolling, network design and dynamic origin-destination (OD) estimation.
Repeated lower level calculations get substantially more efficient by exploiting the considerable overlap between successive iterations, which usually differ only marginally from a base scenario (e.g. gradient approximation) or move progressively (with relatively small steps) in some large solution space. This is exploited in Marginal Computation (MaC) algorithms for the Link Transmission Model, a first order macroscopic network simulation model. It starts from a known DNL/DTA solution, and changes marginally those state variables that differ between the previous iterate and the current.
The seminar presents LTM and two MaC versions of it. One uses a traditional, CFL-consistent calculation scheme. It progresses forward in time, guaranteeing consistency of traffic propagation immediately at each new time step. It is about 40 times faster on mid-sized networks than a full LTM run. But it is quite complex and approximation errors increase as one moves further from the base scenario. i-LTM was re-engineered to account from scratch for marginal computation. It iterates to a fixed-point between a forward propagation stage and a backward stage imposing propagation constraints. They flag to each other which variables have changed compared to a previous iteration, herewith limiting recomputation parsimoniously to only those space-time grid points. Not only does this procedure by-pass CFL requirement on the time step size, it elegantly computes variations to a previous DNL/DTA as flagged changes that are iterated parsimoniously to a new fixed-point.
The seminar presents an application of dynamic OD calibration, where MaC allows for numerical jacobian approximation of DNL/DTA in reasonable time. Exploiting this sensitivity information increases substantially the quality of the optimization on the upper level.
Bio : Chris M. J. Tampère (°1973, Antwerp, Belgium) holds a Masters’ degree in Civil Engineering (1997, KU Leuven, Belgium) and a PhD from Delft University of Technology (2004, The Netherlands).
At TNO Inro, Delft (1997-2003) he developed the MIXIC microsimulator for traffic flows with a variety of Advanced Driver Assistance systems and several travel time estimation and prediction algorithms for freeway and urban networks. His PhD research with TU Delft and TRAIL was on traffic flow theory for ADA systems in congested flows (2004). As a Postdoc Researcher at KU Leuven, he developed realtime models for estimation and prediction of urban traffic conditions (IWT postdoc grant), and did research on network structures, travel time reliability, network traffic management, Dynamic Network Loading (DNL) and Dynamic Traffic Assignment (DTA) models.
Since 2010, he is a Tenure Track Professor at the CIB – Traffic & Infrastructure unit at KU Leuven. He was co-founder of the master in engineering on traffic, logistics and ITS (VLITS), in which he teaches courses on Transportation Engineering, Transport Modeling, Intelligent Transportation Systems, and Dynamic Traffic Management. His current research continues with DNL/DTA modeling and calibration, integrated infrastructure, demand and traffic management in regional transportation networks (KUL research fund), and network design problems with multiple transportation service suppliers.
Repeated lower level calculations get substantially more efficient by exploiting the considerable overlap between successive iterations, which usually differ only marginally from a base scenario (e.g. gradient approximation) or move progressively (with relatively small steps) in some large solution space. This is exploited in Marginal Computation (MaC) algorithms for the Link Transmission Model, a first order macroscopic network simulation model. It starts from a known DNL/DTA solution, and changes marginally those state variables that differ between the previous iterate and the current.
The seminar presents LTM and two MaC versions of it. One uses a traditional, CFL-consistent calculation scheme. It progresses forward in time, guaranteeing consistency of traffic propagation immediately at each new time step. It is about 40 times faster on mid-sized networks than a full LTM run. But it is quite complex and approximation errors increase as one moves further from the base scenario. i-LTM was re-engineered to account from scratch for marginal computation. It iterates to a fixed-point between a forward propagation stage and a backward stage imposing propagation constraints. They flag to each other which variables have changed compared to a previous iteration, herewith limiting recomputation parsimoniously to only those space-time grid points. Not only does this procedure by-pass CFL requirement on the time step size, it elegantly computes variations to a previous DNL/DTA as flagged changes that are iterated parsimoniously to a new fixed-point.
The seminar presents an application of dynamic OD calibration, where MaC allows for numerical jacobian approximation of DNL/DTA in reasonable time. Exploiting this sensitivity information increases substantially the quality of the optimization on the upper level.
Bio : Chris M. J. Tampère (°1973, Antwerp, Belgium) holds a Masters’ degree in Civil Engineering (1997, KU Leuven, Belgium) and a PhD from Delft University of Technology (2004, The Netherlands).
At TNO Inro, Delft (1997-2003) he developed the MIXIC microsimulator for traffic flows with a variety of Advanced Driver Assistance systems and several travel time estimation and prediction algorithms for freeway and urban networks. His PhD research with TU Delft and TRAIL was on traffic flow theory for ADA systems in congested flows (2004). As a Postdoc Researcher at KU Leuven, he developed realtime models for estimation and prediction of urban traffic conditions (IWT postdoc grant), and did research on network structures, travel time reliability, network traffic management, Dynamic Network Loading (DNL) and Dynamic Traffic Assignment (DTA) models.
Since 2010, he is a Tenure Track Professor at the CIB – Traffic & Infrastructure unit at KU Leuven. He was co-founder of the master in engineering on traffic, logistics and ITS (VLITS), in which he teaches courses on Transportation Engineering, Transport Modeling, Intelligent Transportation Systems, and Dynamic Traffic Management. His current research continues with DNL/DTA modeling and calibration, integrated infrastructure, demand and traffic management in regional transportation networks (KUL research fund), and network design problems with multiple transportation service suppliers.
Practical information
- General public
- Free
Organizer
- Nikolas Geroliminis & Katrin Beyer
Contact
- Prof. Nikolas Geroliminis