Optimizing acyclic traffic signal switching sequences through an Extended Linear Complementarity Problem formulation

De Schutter, Bart · 2002 · Crossref

DOI: 10.1016/s0377-2217(01)00364-2

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the optimization of acyclic traffic signal switching sequences for intersections to mitigate congestion. The primary motivation is the need for efficient traffic management strategies that maximize the utility of existing infrastructure, as constructing new roads is often impractical. The specific problem involves determining optimal switching time instants for a pre-fixed phase sequence to minimize criteria such as average queue length, worst-case queue length, and average waiting time. The study focuses on switched systems with linear dynamics subject to saturation, modeling queue lengths as evolving linearly until they hit upper or lower bounds. The methodology formulates the optimization problem as an Extended Linear Complementarity Problem (ELCP). The authors model the evolution of queue lengths using linear growth rates and saturation constraints, resulting in a nonlinear, non-convex optimization problem. While the ELCP formulation can yield globally optimal switching times, it is NP-hard and computationally infeasible for large numbers of phases. To address this, the paper proposes approximations for systems with saturation only at the lower level (zero queue length). By introducing approximate objective functions based on piecewise-linear interpolations of queue lengths, the authors derive a "relaxed" problem. They prove that for strictly monotonic objective functions, such as average queue length, the optimal solution to this relaxed convex problem is also optimal for the original non-convex problem. Furthermore, they demonstrate that linear approximations of these objectives reduce the problem to a linear programming task, which can be solved very efficiently. The findings indicate that while the full ELCP approach provides global optimality, its exponential execution time limits practical application. However, the proposed approximations for lower-saturation-only systems allow for the computation of suboptimal switching sequences that are close to the global optimum with significantly reduced computational effort. The authors show that multi-start local optimization and a "multi-ELCP" approach (solving smaller horizons iteratively) can also yield practical solutions. Crucially, the linear approximation method transforms the complex optimization into a tractable linear programming problem, enabling rapid calculation of switching times suitable for online, moving-horizon control. The significance of this work lies in providing a mathematically rigorous yet computationally viable framework for real-time traffic signal optimization. By bridging the gap between theoretical global optimality and practical computational constraints, the paper offers methods that can be implemented in traffic management systems to dynamically adjust signal timings based on measured arrival and departure rates. This contributes to the field of control systems and operational research by demonstrating how complex switched systems with saturation can be effectively managed using complementarity problem formulations and their efficient approximations.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• gap acceptance