A restricted branch-and-bound approach for generating maximum bandwidth signal timing plans for traffic networks

The synchronization of traffic signals located along the urban/suburban arterials in metropolitan areas is perhaps one of the most cost-effective methods for improving traffic flow along these streets. The main objective of synchronized signal timing is to keep traffic moving in platoons throughout the signal controlled system, by setting the signals along the arterials/networks to provide maximum bandwidth progression. A popular technique for generating signal timing plans formulates the problem as a mixed-integer linear program and uses the Land and Powell branch-and-bound search technique to arrive at the optimal solution. Due to numerical instability of the solution technique and the exhaustive nature of the search procedure, the current implementation tends to be computationally inefficient and infeasable for realistic network problems. Furthermore, numerical instability results in suboptimal or no solutions for network problems with a range of variable cycle times. This paper presents the development of a fast and numerically stable heuristic for the maximum bandwidth signal setting problem. The heuristic is computationally efficient, can generate optimal/near-optimal solutions, and is implemented on a PC. It is based on restricted search of the integer variables in the solution space. The efficiency of this heuristic is supported by computational results for a number of test problems. 1998 Elsevier Science Ltd. All rights reserved