A polynomial-time algorithm for user-based relocation in free-floating car sharing systems. (January 2021)

• Record Type: Journal Article
• Authors: Schiffer, Maximilian; Hiermann, Gerhard; Rüdel, Fabian; Walther, Grit
• Is Part Of: Transportation research. Volume 143(2021)
• Page Start: 65
• Page End: 85
• Publication Date: 2021-01
• Subjects: Free-floating car sharing -- User-based relocation -- Polynomial algorithm; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2020.11.001
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: We present a polynomial algorithm for user-based relocation and vehicle dispatching. We solve instances with 100, 000 requests and 10, 000 vehicles in less than 4 min. We show that spatial relocation outperforms temporal relocation. We analyze the impact of discount strategies on user comfort. Abstract: 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%.