Optimizing Relocation Cost in Free-Floating Car-Sharing Systems

This paper addresses the problem of operator-based vehicle repositioning in free-floating electric car-sharing systems (FFCSs). New algorithmic techniques are developed which derive cost-effective relocation tours by primarily minimizing relocation drivers' walking time. Car repositioning takes place overnight and aims at complete rebalancing of the system i.e., at achieving an optimal, based on user demand, cars distribution among non-overlapping cells of the FFCS's operating area. The battery level of the electric cars is also taken into account when deciding if and where each car will be relocated. If k is the number of employees handling car relocations from oversupplied to undersupplied regions, when k = 1 i.e., there exists a single employee carrying out a relocation tour comprising alternating phases of a car relocation followed by walking to the next to be relocated car, we define and solve the Minimum Walking Car Repositioning Problem (MWCRP) whose main objective is to minimize the walking distance in the relocation tour as the walking part of such a tour is tiresome and takes more time than the driving one. We also define and solve the k-MWCRP when k > 1 to handle the case that a team of more than one drivers is employed to take on the relocation plan. It is worth mentioning that these are the first vehicle relocation techniques lowering the relocation cost by mostly minimizing the walking cost. Performance results confirm the effectiveness of the proposed algorithms.