Matching supply and demand for free-floating car sharing: On the value of optimization

After a promising ramp up, free-floating car sharing is about to establish itself as a mainstream mobility option in many urban areas. This form of short-term car rental allows users to begin trips wherever they are offered an available car and end them at their most convenient position. Current implementations are not based on optimization; each user decides locally whether to place a short-term reservation among available cars. This paper evaluates the potential gains for a car sharing provider if, instead, a sophisticated optimization algorithm is applied to match demand and supply centrally. For this purpose, we formulate the car-request assignment problem, provide a heuristic solution approach, and show how to apply it in different booking processes. Specifically, we compare the status quo with different optimization-based matching approaches, where either the booking with all its details is instantaneously confirmed to the customer or only a service promise is accredited, but the final specification of the car is postponed. Furthermore, we differentiate whether incoming customer requests are collected for a short batching interval and then jointly optimized, or if each customer receives immediate feedback. In an computational study, based on generated and real-world data, these five different booking policies are benchmarked in a dynamic environment where new requests appear over time. The computational tests also evaluate the impact of no-shows, late car returns, and the application of relocators. The results reveal that, once customers are willing to accept an altered booking process, an optimization-based matching mechanism promises considerable improvement of services.