An exact convex relaxation of the freeway network control problem with controlled merging junctions

Marius Schmitt, John Lygeros

This paper, published by researchers at ETH Zurich, provides a significant theoretical breakthrough in traffic engineering by proving that a notoriously difficult non-convex optimization problem—controlling freeway traffic—can be solved exactly using efficient convex optimization techniques.

TL;DR

The authors prove that the non-convex freeway network control problem can be solved via an "exact" convex relaxation by reformulating the system using cumulative flows instead of traffic densities. This allows researchers to use standard linear or convex programming to find globally optimal traffic control strategies (like ramp metering) for complex networks with arbitrary concave fundamental diagrams.

What Problem Does This Paper Address?

Traffic on freeways is typically modeled using the Cell Transmission Model (CTM), which describes how traffic density ($\rho$) and flow ($\phi$) evolve over time. The core of this model is the "fundamental diagram"—a non-linear relationship where flow increases with density until a critical point (capacity) and then decreases as congestion sets in.

Because this relationship is non-linear and non-convex, finding the optimal way to control traffic (e.g., via ramp metering) usually requires solving a non-convex optimization problem. These are computationally expensive and often get stuck in local optima. While engineers often use a "relaxed" convex version of the problem to simplify things, there was no guarantee that the solution to the simplified problem would actually work in the real world—until now.

Methods

The authors' primary innovation is a mathematical "change of coordinates." 1. Cumulative Flow Representation: Instead of using traffic density (cars per kilometer) as the state variable, they use cumulative flow ($\Phi$)—the total number of vehicles that have passed a specific point since time zero. 2. CCTM (Cumulative CTM): They show that in this new representation, the system dynamics become concave and state-monotone. 3. Exactness Proof: Leveraging properties of monotone systems, they prove that if the goal is to minimize the Total Time Spent (TTS) in the network, the convex relaxation is "exact." This means the optimal solution to the easy (relaxed) problem is identical to the optimal solution of the hard (original) problem. 4. Junction Modeling: They categorize merging junctions into three types—symmetric, asymmetric (typical for metered onramps), and sub-critical—and show that controlling the flows at these merges is sufficient to maintain the exactness of the relaxation.

Datasets

The authors validated their theory using two primary setups:

  • The Rocade Sud (Grenoble, France): A real-world freeway segment with 8 metered onramps and 7 off-ramps. They used historical traffic demand data from April 14, 2014, to simulate a 5-hour afternoon rush hour.
  • Artificial Network: A complex synthetic 23-cell network designed specifically to test various combinations of merging and diverging junctions that typically break simpler models.

Key Insights and Ideas

  • State Choice Matters: The "Aha!" moment is that while the CTM is not monotone when looking at densities (because of how diverging junctions work), it is monotone when looking at cumulative flows. This mathematical shift unlocks the use of convex optimization.
  • Generalization: Previous proofs of "exactness" only worked for very specific, symmetric triangular fundamental diagrams. This paper generalizes the result to any concave, monotone fundamental diagram, making it applicable to much more realistic traffic models.
  • Merge Control is Sufficient: You don't need to control the speed or demand of every single car in every cell. Controlling the "valves" at merging junctions is enough to achieve the global optimum for the entire network.

Key Results

  • Efficiency Gains: In the Grenoble case study, the optimized control strategy reduced the Total Time Spent by 3.5% overall, which translated to a 12.1% reduction in total delay compared to the uncontrolled scenario.
  • Computational Speed: The researchers solved a massive linear program with over 67,000 variables and 134,000 constraints in just 270 seconds on a standard laptop.
  • Handling the "Capacity Drop": Real-world traffic often sees a sudden drop in discharge flow once a bottleneck becomes congested. While this effect is non-concave, the authors demonstrated a heuristic based on their convex framework that delayed the onset of congestion and improved performance by nearly 10% compared to standard controllers.

Limitations and Future Work

  • Uncontrolled Merges: The proof relies on having some level of control over merging flows. The authors note that the theory does not currently hold for "uncontrolled" proportional-priority merges, which are common in some jurisdictions.
  • Deterministic Model: The current work assumes perfect knowledge of future traffic demand. Future research is needed to incorporate "robust" or "stochastic" optimization to handle the inherent uncertainty of real-world traffic.
  • FIFO Diverging: While the model handles First-In-First-Out (FIFO) diverging junctions, these junctions are the primary reason the system isn't monotone in the density domain, and they remain a point of sensitivity in the cumulative flow domain.

Summary updated

Abstract

We consider the freeway network control problem where the aim is to optimize the operation of traffic networks modeled by the Cell Transmission Model via ramp metering and partial mainline demand control. Optimal control problems using the Cell Transmission Model are usually non-convex, due to the nonlinear fundamental diagram, but a convex relaxation in which demand and supply constraints are relaxed is often used. Previous works have established conditions under which solutions of the relaxation can be made feasible with respect to the original constraints. In this work, we generalize these conditions and show that the control of flows into merging junctions is sufficient to do so if the objective is to minimize the total time spent in traffic. We derive this result by introducing an alternative system representation. In the new representation, the system dynamics are concave and state-monotone. We show that exactness of the convex relaxation of finite horizon optimal control problems follows from these properties. Deriving the main result via a characterization of the system dynamics allows one to treat arbitrary monotone, concave fundamental diagrams and several types of control for merging junctions in a uniform manner. The derivation also suggests a straightforward method to verify if the results continue to hold for extensions or modifications of the models studied in this work.
BibTeX
@inproceedings{schmitt2018exact,
  author = {Marius Schmitt and John Lygeros},
  title = {{An exact convex relaxation of the freeway network control problem with controlled merging junctions}},
  booktitle = {Transportation},
  year = {2018},
  doi = {10.1016/j.trb.2018.05.006},
}

Loading related content...

Figure