An Exact Convex Relaxation of the Freeway Network Control Problem with Controlled Merging Junctions

Marius Schmitt, John Lygeros

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.

Introduction

Traffic congestion on urban freeways is a major economic and environmental burden. Efficiently managing this traffic often involves solving complex optimization problems to determine optimal ramp metering and mainline control strategies. Traditionally, these problems are framed using the Cell Transmission Model (CTM), which captures the essential dynamics of traffic flow. However, the CTM's inherent non-convexity—stemming from the non-linear relationship between traffic density and flow—makes finding global optima computationally challenging. This paper presents a significant theoretical advancement by proving that a convex relaxation of this problem is "exact" under specific conditions, allowing for efficient and globally optimal solutions.

The Challenge of Non-Convexity

The core of traffic modeling is the "fundamental diagram," which describes how flow ($\phi$) changes with traffic density ($\rho$). In a typical freeway cell, flow increases with density until it reaches capacity at a critical density ($\rho^c$), after which it decreases due to congestion. This non-monotonic behavior introduces non-convexity into optimization problems aimed at minimizing metrics like Total Time Spent (TTS). While researchers often use a relaxed convex version of the problem to simplify computation, there is generally no guarantee that the resulting solution is feasible for the original, non-relaxed system.

Methods: A Change of Coordinates

The authors' primary innovation is a mathematical reformulation of the system state. Instead of using traffic density, they utilize cumulative flow ($\Phi$)—the total count of vehicles that have passed a specific point since a reference time.

Various fundamental diagrams supported by the model: (a) Piecewise-affine, (b) Concave, and (c) with capacity drop.

In this new representation, termed the Cumulative Cell Transmission Model (CCTM), the system dynamics become concave and state-monotone. Leveraging the properties of monotone systems, the authors prove that if the objective is to minimize TTS, the convex relaxation is exact. This means the optimal solution to the simplified convex problem is identical to the optimal solution of the original hard problem. This result is particularly powerful because it generalizes to any concave, monotone fundamental diagram, moving beyond the restrictive triangular models used in previous proofs.

Junction Modeling and Network Topology

The paper extends these findings to complex networks by analyzing merging ($\mathcal{M}$) and diverging ($\mathcal{D}$) junctions. A key insight is that controlling the flows at merging junctions—such as through ramp metering—is sufficient to ensure the exactness of the convex relaxation for the entire network.

Notation for freeway network elements and examples of topology violations.

The authors categorize merges into different types (symmetric, asymmetric, and sub-critical) and demonstrate that as long as these "valves" are controllable, the global optimum can be reached. They also define specific topological constraints, such as avoiding self-loops, to maintain the system's monotonicity.

Key Results and Validation

The theoretical framework was validated using both a real-world case study and a complex synthetic network:

  • Rocade Sud (Grenoble, France): Using historical data from a 10.5 km freeway segment with 15 ramps, the optimized control strategy reduced the Total Time Spent by 3.5%, which corresponds to a 12.1% reduction in total delay compared to an uncontrolled baseline.
  • Computational Efficiency: The researchers solved a massive linear program with over 67,000 variables and 134,000 constraints in just 270 seconds on a standard laptop, highlighting the practical utility of the convex approach.
  • Handling Capacity Drop: While the "capacity drop" (a sudden decrease in flow once congestion starts) is non-concave, the authors developed a heuristic within their framework that delayed congestion onset, improving performance by nearly 10% over standard controllers.

Conclusion

By shifting the perspective from traffic density to cumulative flow, this research provides a robust and general proof for the exactness of convex relaxations in freeway control. This allows traffic engineers to use standard, efficient optimization tools to find globally optimal strategies for complex networks, significantly improving the management of urban congestion.

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},
}
Figure