Title: Charging management of shared taxis: Neighbourhood search for the E-ADARP
Abstract: The electric vehicle market is booming. However, these vehicles need to be refilled more often and do so much more slowly than internal combustion engine (ICE) vehicles. The arrival of autonomous vehicles will enable both fully centralised systems for taxi fleet management and a 24/7 use of each taxi. Finally, the ride-sharing market is also booming. Thus, efficient future taxi fleets will have to provide efficient, integrated solutions for ride-sharing, charging and automation. In this paper, the problem focused on is a variation of the Dial-A-Ride-Problem (DARP) where charging as well as the availability of charging stations are taken into account: Given a fleet of autonomous and electric taxis, a charging infrastructure, and a set of trip requests, the objective is to assign trips and charges to taxis such that the total profit of the fleet is maximised. Our contribution consists in the development of a greedy method, and of a simulated annealing. Our methods are evaluated on large instances (10000 requests) based on taxi trip datasets in Porto. Our conclusions show that while high-capacity batteries are largely unneeded in normal circumstances, they are capital in case of disruption, and useful when the charging infrastructure is shared, with queueing time to access to a charger. Parking searches also represent a significant energy expense for autonomous taxis.