Toll prices on traffic networks have been traditionally determined using a single expected demand value or deterministic demand supply relationships. Previous work by Gardner, Unnikrishnan, and Waller (2008) show that marginal social cost prices obtained using the expected value of demand can significantly deteriorate system performance especially when the actual system state deviates from the planned forecasted conditions. Determining the globally optimal tolls which are resilient to demand uncertainty entails a significantly high number of system performance evaluations which is a computationally intensive process. This work presents two practical methods to arrive at near optimal tolls - single point approximation methods and multiple point inflation/deflation approximation methods - and compares their performance in terms of computational efficiency and proximity to the optimal solution with two other commonly used meta-heuristics - Genetic Algorithm and Adaptive Simulated Annealing. Computational tests reveal that inflation/deflation methods can provide " near to optimal solutions" using a lower number of system performances in comparison to the meta-heuristics and single point approximation methods.