Dynamic Electric Vehicle Routing: Heuristics and Dual Bounds

e-VRO’s N. Kullman, J. Goodson, and J.E. Mendoza just released a manuscript titled  “Dynamic Electric Vehicle Routing: Heuristics and Dual Bounds”. In their paper, they introduce the electric vehicle routing problem with public-private recharging strategy in which vehicles may recharge en-route at public charging infrastructure as well as at a privately-owned depot. To hedge against uncertain demand at public charging stations, they design routing policies that anticipate station queue dynamics. They leverage a decomposition to identify good routing policies, including the optimal static policy and fixed-route-based rollout policies that dynamically respond to observed queues. The decomposition also enables them to establish dual bounds, providing a measure of goodness for their routing policies. In computational experiments, they show the value of their policies to be within 4.7 percent of the value of an optimal policy in most instances. Further, they demonstrate that their policies significantly outperform the industry-standard routing strategy in which vehicle recharging generally occurs at a central depot. More broadly, they offer examples for how operations research tools classically employed in static and deterministic routing can be adapted for dynamic and stochastic routing problems. The manuscript, available here, is the first paper of N. Kullman‘s dissertation. Congratulations Nick.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: