The vehicle redistribution problem for an electric vehicle sharing service

This work is inspired by the Green Move project that aims to design and implement a flexible service of vehicle sharing in Milan, based on electric vehicles (EVs) and open to a wide range of dierent typology of users. Different optimization problems need to be solved to allow an efficient management of the user requests by part of a central unit. For instance the EVs can be parked at several stations and the users would take an EV from a station and leave it in another one. To prevent a station from running out of EVs (or of parking slots) the central unit needs to redistribute the EVs. Up till now the problem of the EV redistribution in a sharing system has been faced with a solution approach similar to that one adopted for the bike sharing, i.e. collecting the exceeding vehicles through a fleet of trucks (in the case of EV by way of tow-trucks) and move them in the stations where they are lacking. We think that such approach is too drastic and not suitable to an urban setting where the EVs may be parked in stations not easily reachable by tow-trucks. Moreover the operation of loading EVs in tow-trucks is very time consuming. For this reason we propose a completely different solution approach consisting in moving the EVs by way of a team of workers that directly drive the EVs that need to be moved. Such a problem generates a challenging pickup and delivery problem with new features that to the best of our knowledge never has been considered in the literature. For such a problem we yield a Mixed Integer Linear Programming formulation that we test on verisimilar instances built on the Milan road network.