Optimizing one-way car sharing systems

In one-way car sharing systems picking up and returning the rental cars can be done at different stations. In these systems, since the customer demand is asymmetric, operators need to hire some staff to manually relocate the cars between stations to keep the system balanced. In this thesis, we address the problem of designing optimal relocation strategies for the one-way car sharing operators both in deterministic and stochastic settings. For the deterministic case, we give a minimum cost network flow formulation. To model the stochastic one, we use stochastic dynamic programming. Our theoretical results show that the exact optimal policy to relocate the cars in a two-station case is a threshold type policy. Based on this result, a heuristic algorithm is proposed to handle the m-station case. Our heuristic significantly decreases the computational complexity of the problem.