Algorithms for Electric Vehicle Scheduling in Mobility-on-Demand Schemes

We study a setting where electric vehicles (EVs) can be hired to drive from pick-up to drop-off points in a mobility-on-demand (MoD) scheme. Each point in the MoD scheme is equipped with a battery swap facility that helps cope with the EVs´ limited range. The goal of the system is to maximise the number of customers that are serviced. Thus, we first model and solve this problem optimally using Mixed-Integer Programming (MIP) techniques and show that the solution scales up to medium sized problems. Given this, we develop a greedy heuristic algorithm that is shown to generate near-optimal solutions and can scale to thousands of consumer requests and EVs. Both algorithms are evaluated in a setting using data of real locations of shared vehicle pick-up and drop-off stations and the greedy algorithm is shown to be on average 90% of the optimal in terms of average task completion.