Models and Algorithms for Carsharing Systems and Related Problems

In a Carsharing System, a fleet of cars is distributed at specified stations in an urban area, users can take and return cars at any time and station. For operating such a system in a satisfactory way, the stations have to keep a good ratio between the total number of places and the number of cars in each station, in order to refuse as few customer requests as possible. In this work, we propose to model the resulting problem of balancing the load of the stations as a General Pickup and Delivery Problem. As problems of this type are known to be hard, we discuss possible heuristic approaches both for the static (offline) and the dynamic (online) version of the problem, and give approximation results for special cases.