Routing electric vehicles on congested street networks

Alexandre M. Florio, Nabil Absi, Dominique Feillet

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Freight distribution with electric vehicles (EVs) is a promising alternative to reduce the carbon footprint associated with city logistics. Algorithms for planning routes for EVs should take into account their relatively short driving range and the effects of traffic congestion on the battery consumption. This paper proposes new methodology and illustrates how it can be applied to solve an electric vehicle routing problem with stochastic and time-dependent travel times where battery recharging along routes is not allowed. First, a new method for generating network-consistent (correlated in time and space) and time-dependent speed scenarios is introduced. Second, a new technique for applying branch and price on instances defined on real street networks is developed. Computational experiments demonstrate the effectiveness of the approach for finding optimal or near-optimal solutions in instances with up to 133 customers and almost 1,500 road links. With a high probability, the routes in the obtained solutions can be performed by EVs without requiring intermediate recharging stops. An execution time control policy to further reduce the chances of stranded EVs is also presented. In addition, we measure the cost of independence, which is the impact on solution feasibility when travel times are assumed statistically independent. Last, we give directions on how to extend the proposed framework to handle recourse actions.
Original languageEnglish
Pages (from-to)238–256
Number of pages19
JournalTransportation Science
Volume55
Issue number1
DOIs
Publication statusPublished - Jan 2021

Keywords

  • Branch-cut-and-price
  • Chance constraints
  • City logistics
  • Scenario generation
  • Stochastic travel times
  • Vehicle routing

Fingerprint Dive into the research topics of 'Routing electric vehicles on congested street networks'. Together they form a unique fingerprint.

Cite this