Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows

Guy Desaulniers (), Fausto Errico (), Stefan Irnich () and Michael Schneider ()
Additional contact information
Guy Desaulniers: Polytechnique Montréal and GERAD, Montréal, Québec, Canada H3C 3A7
Fausto Errico: École de Technologie Supérieure and GERAD and CIRRELT, Montréal, Québec, Canada H3C 1K3
Stefan Irnich: Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, 55128 Mainz, Germany
Michael Schneider: School of Business and Economics, RWTH Aachen University, 52062 Aachen, Germany

Operations Research, 2016, vol. 64, issue 6, 1388-1405

Abstract: Effective route planning for battery electric commercial vehicle (ECV) fleets has to take into account their limited autonomy and the possibility of visiting recharging stations during the course of a route. In this paper, we consider four variants of the electric vehicle-routing problem with time windows: (i) at most a single recharge per route is allowed, and batteries are fully recharged on visit of a recharging station; (ii) multiple recharges per route, full recharges only; (iii) at most a single recharge per route, and partial battery recharges are possible; and (iv) multiple, partial recharges. For each variant, we present exact branch-price-and-cut algorithms that rely on customized monodirectional and bidirectional labeling algorithms for generating feasible vehicle routes. In computational studies, we find that all four variants are solvable for instances with up to 100 customers and 21 recharging stations. This success can be attributed to the tailored resource extension functions (REFs) that enable efficient labeling with constant time feasibility checking and strong dominance rules, even if these REFs are intricate and rather elaborate to derive. The studies also highlight the superiority of the bidirectional labeling algorithms compared to the monodirectional ones. Finally, we find that allowing multiple as well as partial recharges both help to reduce routing costs and the number of employed vehicles in comparison to the variants with single and with full recharges.

Keywords: vehicle routing; electric vehicles; recharging decisions; branch price and cut; labeling algorithms (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (118)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2016.1535 (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:oropre:v:64:y:2016:i:6:p:1388-1405

Access Statistics for this article

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