Service requests are transmitted to multiple vehicles, each request associated with a time and a location. Driving histories of vehicles are known. A first location associated with a service request is compared with a known location in a vehicle driving history. The known location comprises a first cell identifier of a first grid where a size of the cells indicates a maximum acceptable deviation of the vehicle from a travel segment in the driving history that includes the first cell identifier. When the first location matches the known location and the associated time overlaps a start or end time of the travel segment that includes the first cell identifier, the service request is identified to the vehicle. The vehicle sends an indicator that it will perform at least a portion of a service, and an instruction is transmitted to the vehicle that causes the vehicle to perform the service.