In 1997, Wolpert and Macready have derived ?No free lunch theorems for optimization?. They basically state that ?the expected performance of any pair of optimization algorithms across all possible problems is identical?, that is to say that there is no algorithm that outperforms the others over the entire domain of problems. In other words, the choice of the most appropriate algorithm depends upon the specific problem under investigation and a certain algorithm, while providing good performance (both in terms of solution quality and convergence speed) on certain problems may reveal weak on certain others. This apparently straightforward concept is not always acknowledged by optimization practitioners. A typical example, in the field of traffic simulation, concerns the calibration of traffic models. In the present paper, a general method for verifying the robustness of a calibration procedure (suitable in general for any simulation optimization) is proposed based on a test with synthetic data. Main obstacle to this methodology is the significant computation time required by all the necessary simulations. For this reason, a Kriging approximation of the simulation model is proposed instead. The methodology is tested on a specific case study, where the effect on the optimization problem of different combinations of parameters, optimization algorithms, measures of goodness of fit and levels of noise in the data is also investigated. Results show the clear dependence between the performance of a calibration procedure and the case study under analysis and ascertain the need for global solutions in simulation optimization with traffic models.