A matheuristic for the Multi-period Electric Vehicle Routing Problem

Abstract : The Multi-period Electric Vehicle Routing Problem (MP-E-VRP) consists on designing routes to be performed by a fleet of electric vehicles (EVs) to serve a set of customers over a planning horizon of several periods. EVs are charged at the depot at any time, subject to the charging infrastructure capacity constraints (e.g., number of available chargers, power grid constraints, duration of the charging operations). Due to the impact of charging and routing practices on EVs battery aging, degradation costs are associated with charging operations and routes. The MP-E-VRP integrates EV routing and depot charging scheduling, and has coupling constraints between days. These features make the MP-E-VRP a complex problem to solve. In this talk we present a two-phase matheuristic for the MP-E-VRP. In the first phase it builds a pool of routes via a set of randomized route-first cluster-second heuristics. Routes are then improved by solving a traveling salesman problem. In the second phase, the algorithm uses the routes stored in the pool to assemble a solution to the MP-E-VRP. We discuss computational experiments carried out on small-size instances.
Document type :
Conference papers
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02279106
Contributor : Laura Catalina Echeverri <>
Submitted on : Thursday, September 5, 2019 - 12:27:48 AM
Last modification on : Tuesday, September 17, 2019 - 4:20:06 PM

File

MIC19_Echeverri.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02279106, version 1

Citation

Laura Catalina Echeverri, Aurélien Froger, Jorge E. Mendoza, Emmanuel Néron. A matheuristic for the Multi-period Electric Vehicle Routing Problem. 13th Metaheuristics International Conference, Jul 2019, Cartagena de Indias, Colombia. ⟨hal-02279106⟩

Share

Metrics

Record views

132

Files downloads

78