GPS sensors are a promising technique for verifying taximeters, because they do not require dedicated facilities and are compatible with a wide range of vehicles. The main drawback of this technology is based on legal issues: neither the absolute error of a GPS-based measurement nor the tolerance of the sensor can be known in advance, because they depend on environmental factors. In this paper we propose a technique that computes a dynamical tolerance for each measurement, using the Circular Error Probable at 50% and 95% levels. By combining the interpretation of a fuzzy set as a nested family of confidence intervals and a genetic algorithm-based interpolation, we have built an interval-valued estimation of the tolerance of a GPS-based verification of a taximeter.