Branch-Price-and-Cut for the Electric Vehicle Routing Problem with Heterogeneous Recharging Technologies and Nonlinear Recharging Functions

Gaute Messel Nafstad (), Guy Desaulniers () and Magnus Stålhane ()
Additional contact information
Gaute Messel Nafstad: Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, 7491 Trondheim, Norway
Guy Desaulniers: Department of Mathematics and Industrial Engineering, Polytechnique Montreal, Montreal, Quebec H3T 1J4, Canada; and Group for Research in Decision Analysis, HEC Montréal, Montreal, Quebec H3T 2A7, Canada
Magnus Stålhane: Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, 7491 Trondheim, Norway

Transportation Science, 2025, vol. 59, issue 3, 628-646

Abstract: As electric vehicles become increasingly prevalent, effective planning of their use becomes paramount. The electric vehicle routing problem, characterized by limited driving range and the need for recharging, poses unique challenges compared with traditional vehicle routing problems. This paper proposes a branch-price-and-cut solution method tailored for the electric vehicle routing problem with time windows, heterogeneous recharging technologies, and nonlinear charging functions (E-VRPTW-NL). The methodology differs from previous methods proposed in the literature by handling nonlinear recharging functions in the pricing problem. The pricing problem is solved by a bidirectional labeling algorithm that efficiently handles the complex interdependency between time and state of charge during recharge scheduling. The proposed solution method is tested on both benchmark instances from the literature as well as new instances. Tests show that the solution method is competitive with well-known solution methods from the literature on simpler variants of the problem. The computational results also indicate that the proposed method can solve new E-VRPTW-NL instances with up to 100 customers and 21 recharge locations within one hour. Further analysis explores how simplifying the modeling of the recharging process affects solution feasibility and cost. The results show that keeping the heterogeneity of the recharging functions is crucial, whereas simplifying the shape of each recharging function has limited impact.

Keywords: electric vehicle routing; branch-price-and-cut (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2024.0725 (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:59:y:2025:i:3:p:628-646

Access Statistics for this article

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