Online Energy-optimal Routing for Electric Vehicles with Combinatorial Multi-arm Semi-Bandit
Open Access
- 20 September 2020
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Abstract
We have seen a rapid growth in the adoption of electric vehicle in today’s commercial mobility service market, from carrying passengers to the delivery of goods. One cardinal issue concerning the operation of EVs is the optimal routing of EV fleets with limited battery capacity. In this study, we investigate the energy-optimal online routing problem for the fleet of EVs, which focuses on identifying real-time minimum electricity consumption paths (MECP) for multiple OD pairs with limited information. We develop a multi-OD combinatorial multi-arm semi-bandit model (MCMAB) that uses the fleet of EVs as sensors in the transportation network and promotes the utilization of common information shared by different OD pairs. We further enrich the model with the path elimination policy to obtain MECP of high confidence while significantly reducing the number of learning iterations and the number of explorations needed. We demonstrate the effectiveness of the MCMAB and the efficiency of the path elimination policy with comprehensive numerical experiments in Manhattan, NYC. The results show that the proposed online routing algorithms can achieve near-optimal MECPs efficiently, and the quality of the solutions is significantly better than using the shortest travel time paths as approximate MECPs.Keywords
Funding Information
- U.S. Department of Energy
- Office of Energy
This publication has 15 references indexed in Scilit:
- Optimal charging facility location and capacity for electric vehicles considering route choice and charging time equilibriumComputers & Operations Research, 2020
- Stationary Spatial Charging Demand Distribution for Commercial Electric Vehicles in Urban Area2019
- A review on the state-of-the-art technologies of electric vehicle, its impacts and prospectsRenewable and Sustainable Energy Reviews, 2015
- Optimal deployment of public charging stations for plug-in hybrid electric vehiclesTransportation Research Part B: Methodological, 2013
- Combinatorial banditsJournal of Computer and System Sciences, 2012
- Electric vehicle simulator for energy consumption studies in electric mobility systems2011
- UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problemPeriodica Mathematica Hungarica, 2010
- Exploration–exploitation tradeoff using variance estimates in multi-armed banditsTheoretical Computer Science, 2009
- Probability Inequalities for sums of Bounded Random Variables1994
- A note on two problems in connexion with graphsNumerische Mathematik, 1959