Simulation-based optimization of traffic signal timing has become pervasive and popular, in the field of traffic engineering. When the underlying simulation model is well-trusted and/or well-calibrated, it is only natural that typical engineers would want their signal timing optimized using the judgment of that same model. As such, it becomes important that the heuristic search methods typically used by these optimizations are capable of locating global optimum solutions, for a wide range of signal systems. However off-line and real-time solutions alike offer just a subset of the available search methods. The result is that many optimizations are likely converging prematurely on mediocre solutions. In response, this paper compares several search methods from the literature, in terms of both optimality (i.e., solution quality) and computer run times. Simulated annealing and genetic algorithm methods were equally effective in achieving near-global optimum solutions. Two selection methods (roulette wheel and tournament), commonly used within genetic algorithms, exhibited similar effectiveness. Tabu searching did not provide significant benefits. Trajectories of optimality versus run time (OVERT) were similar for each method, except some methods aborted early along the same trajectory. Hill-climbing searches always aborted early, even with a large number of step-sizes. Other methods only aborted early when applied with ineffective parameter settings (e.g. mutation rate, annealing schedule). These findings imply (1) todays products encourage a sub-optimal one size fits all approach, (2) heuristic search methods and parameters should be carefully selected based on the system being optimized, (3) weaker searches abort early along the OVERT curve, and (4) improper choice of methods and/or parameters can reduce optimization benefits by 2233%.