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

E. Rigas, S. Ramchurn, N. Bassiliades, “Algorithms for Electric Vehicle Scheduling in Mobility-on-Demand Schemes”, Proc. 2015 IEEE 18th International Conference on Intelligent Transportation Systems (ITSC), Las Palmas de Gran Canaria, Spain, 15-18 Sep 2015, pp. 1339-1344.

Electric Vehicles, Energy Efficiency, Smart Mobility, Transportation Electrification.

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, while 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 approach that is shown to output solutions that are close to the optimal and can scale to thousands of consumer requests and EVs. Both algorithms are evaluated in a setting using data of actual locations of shared vehicle pick-up and dropoff stations in Washington DC, USA and the greedy algorithm is shown to be on average 90% of the optimal in terms of average task completion.