Abstract: Existing electric vehicle API platforms (e.g., SmartCar), use access control mechanisms to preserve users’ privacy. To preserve location privacy and meanwhile enable functionality of untrustworthy location-based services, a location privacy preserving mechanism (LPPM) can be used to generate a random pseudo-location as a reported location based on a user’s true location. Existing techniques solves an optimization problem on a discrete grid, to construct an optimal LPPM which achieves the highest privacy bounded by minimum tolerable utility, or vice versa. However, they cannot be applied to real-time electric vehicle scenarios since the running time required to generate an optimal LPPM is too long (which can be several days). Another problem deals with optimality of constructed LPPMs. We reveal unexpected cases (anomaly) when the optimal LPPM constructed on a fine grid with superior granularity is worse than that on a coarse one with inferior granularity. We introduce granularity independence as a formal treatment, and propose an optimal LPPM named Divide-and-Coin which can be performed on the fly. Divide-and-Coin improves the running time from at least O ( n^2.055 ) to O ( \mathrml\mathrmo\mathrmgn ), where n is the number of reported locations. Our experimental results show that it generates an optimal building-level reported location from a city-level area within 1 second.