Simulation Optimization of Traffic Light Signal Timings via Perturbation Analysis

Abstract

We develop simulation optimization algorithms for determining the traffic light signal timings for an isolated intersection and a network of two-signalized intersections modeled as single-server queues. Both problem settings consider traffic flowing in one direction. The system performance is estimated via stochastic discrete-event simulation. In the first problem setting, we examine an isolated intersection. We use smoothed perturbation analysis to derive both left-hand and right-hand gradient estimators of the queue lengths with respect to the green/red light lengths within a signal cycle. Using these estimators, we are able to apply stochastic approximation, which is a gradient-based search algorithm. Next we extend the problem to the case of a two-light intersection, where there are two additional parameters that we must estimate the gradient with respect to: the green/red light lengths within a signal cycle at the second light and the offset between the two light signals. Also, the number of queues increases from two to five. We again derive both left-hand and right-hand gradient estimators of the all queue lengths with respect to the three aforementioned parameters. As before, we are able to apply gradient-based search based on stochastic approximation using these estimators. Next we reexamine the two aforementioned problem settings. However, this time we are solely concerned with optimization; thus, we model the intersections using three different stochastic fluid models, each incorporating different degrees of detail. From these new models, we derive infinitesimal perturbation analysis gradient estimators. We then implement these estimators on the underlying discrete-event simulation and are able to apply gradient-based search based on stochastic approximation using these estimators. We perform numerical experiments to test the performance of the three gradient estimators and also compare these results with finite-difference estimators. Optimization for both the one-light and two-light settings is carried out using the gradient estimation approaches.