Computational Efficiency of Alternative Algorithms for Arterial Offset Optimization

Abstract

This paper compares the performance of several algorithms for offset optimization. A case study of a five-intersection arterial is presented. Cyclic probability distributions of vehicle arrivals and the probability of green are used to characterize traffic conditions under alternative offsets. Five algorithms for offset optimization were selected for comparison: quasi-exhaustive search, Monte Carlo selection, genetic algorithms, hill climbing, and the combination method. Each algorithm was evaluated with two alternative objectives: minimize delay and maximize vehicle arrivals on green. The relative performances of the algorithms were characterized by the optimality of the solution that they returned, the number of computations needed to execute the algorithm, and the marginal cost of adding an additional intersection to the system. All five algorithms effectively identified optimal or near-optimal offsets within the solution space. Hill climbing was more efficient than genetic algorithms, but the optimality of the solutions from both types was similar. The combination method found the most optimal offsets, with efficiency similar to that of hill climbing. The combination method is recommended for arterial offset optimization because of its deterministic computational performance for identifying optimized offset timing plans.