Relocation Strategies and Algorithms for Free-Floating Car Sharing Systems

During the last years so-called free-floating Car Sharing Systems became very popular. These systems in comparison to the conventional Car Sharing Systems allow short one-way trips. Today, the spatial distribution of vehicles within free-floating Car Sharing Systems is either self-organized, which means it is only dependent on the customer's demand or in a few cases the positioning is manually controlled by system operators. None of the real-life free-floating Car Sharing Systems has a clear defined relocation strategy or is even online optimized based on the current demand. Within this paper several relocation strategies are introduced and categorized. For each category known relocation algorithms are described and evaluated. Also a new integrated two-step model for optimal vehicle positioning and relocation is described in detail. This new approach consists of an offline demand clustering that allows for the prediction of demand and thus the prediction of the optimal future state of spatially available vehicles. The online module of the approach measures the differences between optimal vehicle positioning and current positioning. An optimization algorithm finds optimal relocation strategies if necessary. The main focus of this paper is on the description of the Offline Demand Module.