Routing Electric Vehicles on Congested Street Networks

Alexandre M. Florio (), Nabil Absi () and Dominique Feillet ()
Additional contact information
Alexandre M. Florio: Center microelectronics de Provence Georges Charpak and Laboratoire informatique, modélisation et optimisation des systèmes, Centre national de la recherche scientifique unité mixte de recherche 6158, École des Mines de Saint-Étienne, F-13541 Gardanne, France
Nabil Absi: Center microelectronics de Provence Georges Charpak and Laboratoire informatique, modélisation et optimisation des systèmes, Centre national de la recherche scientifique unité mixte de recherche 6158, École des Mines de Saint-Étienne, F-13541 Gardanne, France
Dominique Feillet: Center microelectronics de Provence Georges Charpak and Laboratoire informatique, modélisation et optimisation des systèmes, Centre national de la recherche scientifique unité mixte de recherche 6158, École des Mines de Saint-Étienne, F-13541 Gardanne, France

Transportation Science, 2021, vol. 55, issue 1, 238-256

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.

Keywords: vehicle routing; >city logistics; stochastic travel times; chance constraints; scenario generation; branch-cut-and-price (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
https://doi.org/10.1287/trsc.2020.1004 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:55:y:2021:i:1:p:238-256

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().