Nowadays vehicle fleets are launched to perform business or scientific tasks, with new features supported by the emerging multi-access edge computing (MEC) platform. In the presence of high vehicle mobility, however, it is challenging to precisely provision resources among distributed edge clouds so that i) the QoS of vehicular service is guaranteed and meanwhile ii) the provisioning cost is minimized. We systematically investigate the QoS guaranteed optimal resource provisioning problem for the connected vehicle fleet in the MEC environment. Based on stochastic traffic analysis, we propose an optimization framework to minimize the cost of resource provisioning, while the service blocking probability is guaranteed to be smaller than a predefined threshold. We then present a lightweight two-phase algorithm based on bracketing and binary searching to solve the problem efficiently. To evaluate our method, we use two large real-world datasets collected by an online taxi service platform and validate the QoS with our resource provisioning strategy. The results demonstrate that our method can save the total provision cost up to 40%, compared with the naïve resource provisioning strategy, and meanwhile can provide reliable QoS guarantee, compared with the mobility estimation-based approach.