Optimization of Carsharing Fleet Placement in Round-Trip Carsharing Service

In a round-trip carsharing system, stations must be located in such a way that allow for maximum user coverage with the least walking distance as well as offer certain degrees of flexibility for returning. Therefore, a balance must be stricken between these factors. Providing a satisfactory system can be translated into an optimization problem and belongs to an NP-hard class. In this article, a novel optimization model for the round-trip carsharing fleet placement problem, called Fleet Placement Problem (FPP), is proposed. The optimization in this work is multiobjective and its NP-hard nature is proven. Three different optimization algorithms: PolySCIP (exact method), heuristics, and NSGA-II (metaheuristic) are investigated. This work adopts three real instances for the study, instead of their abstracts where they are most commonly used. They are two instance:, in the city of Luxembourg (smaller and larger) and a much larger instance in the city of Munich. Results from each algorithm are validated and compared with solution from human experts. Superiority of the proposed FPP model over the traditional methods is also demonstrated.

Automated summary

This article proposes a novel optimization model for the round-trip carsharing fleet placement problem, proves its NP-hard nature, investigates different optimization algorithms, and validates the results using real instances.