Modelling relocation strategies for shared mobility system management

Often the demand for vehicle sharing services varies significantly in space and time. Some stations/regions may run out of units due to uneven demand, while concurrent end journeys may overload others. To meet user trip demand and enhance user satisfaction and usage, a relocation procedure is a solution to rebalance vehicles in various stations. This thesis focuses on free-floating car sharing systems employing an operator-based relocation process to mitigate the imbalanced vehicle distribution problem. Many previous works have already confronted the repositioning problem, optimising the relocation process only based on knowledge about the immediate future. The methods developed in this thesis aim at maximising the satisfied mobility demand avoiding a greedy and possibly short-sighted approach and taking into account demand forecasts over a longer time period and over multiple relocation steps. The objective is to identify, at each time frame, how many cars to move from one zone to another in order to maximise a given dynamic forecast demand, with constraints on the maximum number of cars to be moved and the time needed for vehicles to be relocated. In particular the thesis analyses different optimisation methods for improving the relocation strategy and investigates how far in the future is it appropriate to look. A first method is based on the dynamic programming approach, which is - in principle - able to find the optimal solution but, unfortunately, very little scalable and inappropriate to fit the problem dimensionality. A second procedure to find an approximate yet performing solution is based on the formulation of a linear optimisation program in three versions: a linear program, a mixed-integer linear program and a combination of the two, gradually relaxing more and more integrality constraints for computational time purposes. Finally, starting from the solutions obtained through such algorithms, a further neighbourhood search step, including the simulated annealing strategy, may be performed to improve the quality of the solution. Considering the city of Turin as a case study and using mobility data coming from the operating Car2go fleet, the performances of the developed strategies have been evaluated, taking into account satisfied trips, costs, and computational effort needed. A comparison with a greedy approach optimising over only a single time frame and with a no-relocation based strategy is then carried out. The approximated solution is also compared with the optimal one found through the dynamic programming approach only in a toy example. Finally, the impact of the relocation costs on the profits and the maximum relocation are investigated. Results show that a long-sighted strategy is preferred over a greedy one, with performance improvements of up to 10% more satisfied demand, with a 2 two-hour time frame look-ahead period already improving performances by around 7%. A relocation strategy enhances the system performance in the first place, although high relocation costs may result in a reduction in profits and user satisfaction, which may be mitigated with an increase in fares. Moreover, a MILP-based approach proves to be the best performing one, although computational times become prohibitive for long look ahead periods, while the LP-based approach gives good performances always in short times. Finally, the neighbourhood search doesn’t always turn out to improve performances while needing great computational effort.