A polynomial-time algorithm for user-based relocation in free-floating car sharing systems

Free-floating car sharing (FFCS) systems are a promising concept to reduce the traffic volume in cities. However, spatial and temporal mismatches of supply and demand require a relocation of rental cars in order to avoid low degrees of utilization. Here, especially user-based relocation strategies seem to be promising to increase utilization in a cost-efficient manner. However, a thorough optimization-based assessment of user-based relocation strategies for FFCS systems is still missing. In this paper, we introduce an integer program that optimizes the assignment of user-based relocation strategies in FFCS fleets. We develop a graph representation that allows to reformulate the problem as a k-disjoint shortest paths problem and propose an exact algorithm to solve large-size instances. We show that this algorithm can solve real-world instances within a few milliseconds as well as instances with up to 100,000 customers and 10,000 vehicles in a few minutes. Furthermore, we present a case study based on real-world data and derive managerial insights on user-based relocation strategies. Our results reveal an upper bound on the benefit of user-based relocation strategies and demonstrate that the employment of such strategies can increase the number of fulfilled rental requests by 21%, while increasing the operator's revenue by 10%.