A node-charge, graph-based online carshare rebalancing policy with capacitated electric charging

As the makeup of car-share fleets reflect the global shift to electric vehicles (EV) operators will need to address unique challenges to EV fleet scheduling. These include user time and distance requirements, time needed to recharge vehicles, and distribution of charging facilities—including limited availability of fast charging infrastructure (as of 2019 there are seven fast DC public charging stations in Manhattan including Tesla stations). Because of such factors, the viability of electric car-sharing operations depends on fleet rebalancing algorithms.

The stakes are high because potential customers may end up waiting or accessing a farther location, or even balk from using the service altogether if there is no available vehicle within a reasonable proximity (which may involve substantial access, e.g. taking a subway from downtown Manhattan to midtown to pick up a car) or no parking or return location available near the destination.

In a new study, published in the journal Transportation Science, the authors present an algorithmic technique based on graph theory that allows electric mobility services like carshares to reduce operating expenses, in part because the algorithm operates in real time, and anticipates future costs, which could make it easier for fleets to switch to EV operations in the future.

The common practice for carshare scheduling is for users to book specific time slots and reserve a vehicle from a specific location. The return location is required to be the same for “two-way” systems but is relaxed for “one-way” systems. Examples of free-floating systems were the BMW ReachNow car sharing system in Brooklyn (until 2018) and Car2Go in New York City. These two systems recently merged to become ShareNow, which is no longer in the North American market.

Rebalancing involves having either the system staff or users (through incentives) periodically drop off vehicles at locations that would better match supply to demand. While there is an abundant literature on methods to handle carshare rebalancing, research on rebalancing EVs to optimize access to charging stations is limited: there is a lack of models formulated for one-way EV carsharing rebalancing that captures all the following: 1) the stochastic dynamic nature of rebalancing with stochastic demand; 2) incorporating users’ access cost to vehicles; and 3) capacities at EV charging stations.

The researchers offer an innovative rebalancing policy based on cost function approximation (CFA) that uses a novel graph structure that allows the three challenges to be addressed. The team’s rebalancing policy uses cost function approximation in which the cost function is modeled as a relocation problem on a node-charge graph structure.

The researchers validated the algorithm in a case study of electric carshare in Brooklyn, New York, with demand data shared from BMW ReachNow operations in September 2017 (262 vehicle fleet, 231 pickups per day, 303 traffic analysis zones) and charging station location data (18 charging stations with 4 port capacities). The proposed non-myopic rebalancing heuristic reduces the cost increase compared to myopic rebalancing by 38%. Other managerial insights are further discussed.

The researchers reported that their formulation allowed them to explicitly consider a customer’s charging demand profile and optimize rebalancing operations of idle vehicles accordingly in an online system. They also reported that their approach solved the relocation problem in 15%–89% of the computational time of commercial solvers, with only 7–35% optimality gaps in a single rebalancing decision time period.

The study’s authors say future research directions include dynamic demand (function of time, price and other factors), data-driven (machine learning) algorithms for updating, more realistic/ commercial simulation environment using data from larger operations, and detailed cost-benefit analysis on the tradeoffs of EV’s and regular vehicles.