A Link-based Mixed Integer LP Approach for Adaptive Traffic Signal\n Control

Ke Han, Terry L. Friesz, Tao YaoarXiv 2012 · DOI · arXiv

Abstract

This paper is concerned with adaptive signal control problems on a road network, using a link-based kinematic wave model. Such a model employs the Lighthill-Whitham-Richards model with a triangular fundamental diagram. A variational type argument is applied so that the system dynamics can be determined without knowledge of the traffic state in the interior of each link. A Riemann problem for the signalized junction is explicitly solved; and an optimization problem is formulated in continuous-time with the aid of binary variables. A time-discretization turns the optimization problem into a mixed integer linear program (MILP). Unlike the cell-based approaches, the proposed framework does not require modeling or computation within a link, thus reducing the number of (binary) variables and computational effort. The proposed model is free of vehicle-holding problems, and captures important features of signalized networks such as physical queue, spill back, vehicle turning, time-varying flow patterns and dynamic signal timing plans. The MILP can be efficiently solved with standard optimization software.

Introduction

Adaptive traffic signal control is essential for managing urban congestion by adjusting light timings in response to real-time traffic conditions. However, the mathematical complexity of modeling city-wide traffic often leads to a trade-off between physical accuracy and computational efficiency. Traditional "exact" models typically rely on the Cell Transmission Model (CTM), which discretizes roads into numerous small segments or "cells." This approach suffers from two primary drawbacks: significant computational overhead due to the high number of variables, and the "vehicle-holding" phenomenon, where mathematical relaxations allow vehicles to be artificially delayed in a cell despite downstream capacity.

This research proposes a link-based approach that circumvents these issues by focusing on traffic dynamics at link boundaries rather than within the links themselves.

Methodology

The core of the proposed framework is the Link-based Kinematic Wave Model (LKWM). By utilizing the Lighthill-Whitham-Richards (LWR) model with a triangular fundamental diagram, the authors apply a variational argument (Lax-Hopf formula) to track traffic states.

Boundary-Centric Modeling

Instead of calculating density at every point along a road, the model determines the traffic state at the entrance and exit of each link. This allows the system to capture the movement of shockwaves—whether they are propagating forward in free-flow or backward in congestion—without interior computation.

Figure 2: Traffic regimes in the time-space plane, showing free-flow (case i) and congested (case ii) phases at link boundaries.

Junction Dynamics and MILP Formulation

To handle intersections, the authors explicitly solve the Riemann problem for junctions, determining how traffic is distributed among competing links during different signal phases.

Figure 1: Schematic of a signalized junction with incoming and outgoing links.

The continuous-time dynamics are discretized into a Mixed Integer Linear Program (MILP). Binary variables are employed to represent discrete states, such as signal phases (red/green) and the traffic regime (free-flow/congested) at link boundaries. This formulation naturally prevents "vehicle holding" because it does not rely on the same linear relaxations as cell-based models.

Key Insights

  • Efficiency through Reduction: By ignoring the interior of links, the number of variables is drastically reduced compared to CTM-based models.
  • Shockwave Awareness: The model explicitly bounds shockwaves, allowing for constraints that prevent "spillback"—where queues grow long enough to block upstream intersections.
  • Physical Realism: The link-based approach captures physical queues, vehicle turning percentages, and time-varying flow patterns without sacrificing speed.

Results and Discussion

The model was evaluated on a synthetic network of two signalized intersections and seven links. Using standard optimization software (ILOG CPLEX), the MILP was solved in approximately 0.49 seconds. This performance indicates that the link-based approach is highly suitable for "rolling horizon" adaptive control, where signals are updated frequently based on short-term forecasts.

Despite its efficiency, the model maintains high physical accuracy. Visualization of Moskowitz functions (cumulative vehicle counts) confirmed that the model correctly identifies traffic regimes and handles the flow discontinuities caused by signal changes.

Conclusion

The link-based MILP framework offers a computationally lean and physically robust alternative to traditional cell-based traffic signal optimization. While MILPs are inherently NP-hard, the significant reduction in variables makes this approach promising for real-time applications. Future research will focus on scaling the model to larger networks, potentially integrating heuristic algorithms or parallel computing, and incorporating dynamic route choice to better reflect driver behavior in response to signal timing changes.

Summary updated

Abstract

This paper is concerned with adaptive signal control problems on a road\nnetwork, using a link-based kinematic wave model (Han et al., 2012). Such a\nmodel employs the Lighthill-Whitham-Richards model with a triangular\nfundamental diagram. A variational type argument (Lax, 1957; Newell, 1993) is\napplied so that the system dynamics can be determined without knowledge of the\ntraffic state in the interior of each link. A Riemann problem for the\nsignalized junction is explicitly solved; and an optimization problem is\nformulated in continuous-time with the aid of binary variables. A\ntime-discretization turns the optimization problem into a mixed integer linear\nprogram (MILP). Unlike the cell-based approaches (Daganzo, 1995; Lin and Wang,\n2004; Lo, 1999b), the proposed framework does not require modeling or\ncomputation within a link, thus reducing the number of (binary) variables and\ncomputational effort.\n The proposed model is free of vehicle-holding problems, and captures\nimportant features of signalized networks such as physical queue, spill back,\nvehicle turning, time-varying flow patterns and dynamic signal timing plans.\nThe MILP can be efficiently solved with standard optimization software.\n
BibTeX
@misc{han2012link,
  author = {Ke Han and Terry L. Friesz and Tao Yao},
  title = {{A Link-based Mixed Integer LP Approach for Adaptive Traffic Signal\textbackslash\{\}n Control}},
  year = {2012},
  eprint = {1211.4625},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1211.4625},
}

Loading related content...

Figure