The Electric Vehicle Shortest-Walk Problem With Battery Exchanges

Jonathan D. Adler, Pitu Mirchandani, Guoliang Xue, Minjun Xia

Research output: Contribution to journalArticlepeer-review

62 Scopus citations


Electric vehicles (EV) have received much attention in the last few years. Still, they have neither been widely accepted by commuters nor by organizations with service fleets. It is predominately the lack of recharging infrastructure that is inhibiting a wide-scale adoption of EVs. The problem of using EVs is especially apparent in long trips, or inter-city trips. Range anxiety, when the driver is concerned that the vehicle will run out of charge before reaching the destination, is a major hindrance for the market penetration of EVs. To develop a recharging infrastructure it is important to route vehicles from origins to destinations with minimum detouring when battery recharging/exchange facilities are few and far between. This paper defines the EV shortest-walk problem to determine the route from a starting point to a destination with minimum detouring; this route may include cycles for detouring to recharge batteries. Two problem scenarios are studied: one is the problem of traveling from an origin to a destination to minimize the travel distance when any number of battery recharge/exchange stops may be made. The other is to travel from origin to destination when a maximum number of stops is specified. It is shown that both of these problems are polynomially solvable and solution algorithms are provided. This paper also presents another new problem of finding the route that minimizes the maximum anxiety induced by the route.

Original languageEnglish (US)
Pages (from-to)155-173
Number of pages19
JournalNetworks and Spatial Economics
Issue number1
StatePublished - Mar 1 2016


  • Alternative-fuel vehicles
  • Constrained shortest paths
  • Constrained vehicle routing
  • Electric vehicles
  • Shortest paths with refueling

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'The Electric Vehicle Shortest-Walk Problem With Battery Exchanges'. Together they form a unique fingerprint.

Cite this