The car sharing problem

We consider a novel type of metric task system, termed the car sharing problem , in which the operator of a car sharing program aims to serve the requests of customers occurring at different locations. Requests are modeled as a stochastic process with known parameters and a request is served if a car is located at the position of its occurrence at this time. Customers pay the service provider according to the distance they travel and similarly the service provider incurs cost proportional to the distance traveled when relocating a car from one position to another between requests. We derive an efficient algorithm to compute a redistribution policy that yields average long-term revenue within a factor of 2 of optimal and provide a complementing proof of APX-hardness. Considering a variation of the problem in which requests occur simultaneously in all locations, we arrive at an interesting repeated balls-into-bins process, for which we prove bounds on the average number of occupied bins.