Dynamic Electric Vehicle Routing with Uncertain Charging Station Access: Lower Bounds via Information Penalties

As we shift towards sustainable transport, electric vehicles (EVs) are becoming more popular in supply chain distribution functions. However, EVs pose operational challenges to which their conventional petroleum-based counterparts are immune. Perhaps most notably is EVs' restricted driving ranges which force more frequent recharging. In addition, because charging station infrastructure is limited and EVs require significant time to charge, charging stations will often be unavailable when an EV arrives and the EV may be forced to queue.

 

We address these operational challenges in the EV Routing Problem with Mid-route Recharging and Uncertain Availability (EVRP-MRUA). We model the EVRP-MRUA as a Markov decision process and implement a stochastic dynamic programming (SDP) solution using four heuristic policies. To establish a bound on the value of an optimal routing policy, we combine information relaxation techniques with mixed integer programming methods to estimate the expected value of an optimal policy with perfect information, i.e., the performance achieved via a clairvoyant logistics planner. Then, we improve on the perfect-information bound by developing computationally tractable information penalties, a first in vehicle routing. We find that for a subset of our problem instances, our dynamic policies perform within 5% of the optimal policy.