The Electric Vehicle Routing and Overnight Charging Scheduling Problem on a Multigraph

Daniel Yamín (), Guy Desaulniers () and Jorge E. Mendoza ()
Additional contact information
Daniel Yamín: Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá 111711, Colombia
Guy Desaulniers: Polytechnique Montréal and GERAD, Montreal, Quebec H3C 3A7, Canada
Jorge E. Mendoza: HEC Montréal, Montreal, Quebec H3T 2A7, Canada

INFORMS Journal on Computing, 2025, vol. 37, issue 4, 808-830

Abstract: In the electric vehicle (EV) routing and overnight charging scheduling problem, a fleet of EVs must serve the demand of a set of customers with time windows. The problem consists in finding a set of minimum cost routes and determining an overnight EV charging schedule that ensures the routes’ feasibility. Because (i) travel time and energy consumption are conflicting resources, (ii) the overnight charging operations take considerable time, and (iii) the charging infrastructure at the depot is limited, we model the problem on a multigraph where each arc between two vertices represents a path with a different resource consumption trade-off. To solve the problem, we design a branch-price-and-cut algorithm that implements state-of-the-art techniques, including the ng -path relaxation, subset-row inequalities, and a specialized labeling algorithm. We report computational results showing that the method solves to optimality instances with up to 50 customers. We also present experiments evaluating the benefits of modeling the problem on a multigraph rather than on the more classical 1-graph representation.

Keywords: electric vehicle routing; charging scheduling; multigraph; branch-price-and-cut; labeling algorithm; city logistics (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0404 (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:orijoc:v:37:y:2025:i:4:p:808-830

Access Statistics for this article

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