A Linear Time and Space Algorithm for Optimal Traffic-Signal Duration at an Intersection

Finding an optimal solution for traffic-signal control duration is a computationally intensive task. It is typically O(T³) in time and O(T²) in space, where T is the length of the control interval in discrete-time steps. In this paper, we propose a linear time and space algorithm for the traffic-signal control problem. The algorithm provides an efficient dynamic programming formulation of the state space that prunes nonoptimal states early on. This paper proves the correctness of the algorithm and provides an initial experimental validation. This paper also conducts a simulation study comparing with other typical control methods. The results show significant improvement in the average waiting time metric with respect to all other methods.