Car-sharing systems are an attractive alternative to private vehicles due to their benefits in terms of mobility and sustainability. However, the distribution of vehicles throughout the network in one-way systems is disturbed due to asymmetry and stochasticity in demand. As a consequence, vehicles need to be relocated to maintain an adequate service level. In this paper, we develop a user-based vehicle relocation approach through the incentivization of customers and a predictive model for the state of the system based on Markov chains. Our methods determine the optimal incentive as a trade-off between the cost of an incentive and the expected omitted demand loss while taking into account the value of time of customers. We introduce a learning algorithm that allows the operator to estimate unknown customer preferences to find the optimal incentive. Experimental results in an event-based simulation of a real system show that the use of incentives can significantly increase the service level and profitability of a car-sharing system and decrease the number of staff members needed to balance the vehicles in the system. Thereby, incentives are a more sustainable alternative to staff-based relocations. Extensive sensitivity analyses show the prospective benefits in terms of customer flexibility and the robustness of our results to varying customer preferences.