Electric vehicle routing problems (E-VRPs) are receiving growing attention from the operations research community. Electric vehicles differ substantially from internal combustion engine vehicles, the main difference lying in their limited autonomy, which can be recovered at charging stations. Modeling the charging functions is a focal point of E-VRPs. Most of the research has focused on constant or linear charging functions. The E-VRP with nonlinear charging function (E-VRP-NL) was recently introduced to account for the more realistic nonlinear relationship between the time spent charging and the amount of energy charged. We propose two new formulations for this problem. We first develop an arc-based tracking of the time and the state of charge which, according to our experiments, outperforms the classical node-based tracking of these values. To avoid replicating the charging stations nodes, as done for both node and arc based formulations, we also introduce a path-based model. We develop an algorithm to generate a tractable number of these paths. This path-based model outperforms the classical models in our experiments. We also propose a new model, a heuristic, and an exact labeling algorithm for the problem of finding the optimal charging decisions for a given route. Extensive computational results show that charging decisions considerably impact the quality of the E-VRP-NL solutions. Indeed, we improve 23 out of 120 best known E-VRP-NL solutions by solely revising the charging decisions.

Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions

Jabali, Ola;
2019-01-01

Abstract

Electric vehicle routing problems (E-VRPs) are receiving growing attention from the operations research community. Electric vehicles differ substantially from internal combustion engine vehicles, the main difference lying in their limited autonomy, which can be recovered at charging stations. Modeling the charging functions is a focal point of E-VRPs. Most of the research has focused on constant or linear charging functions. The E-VRP with nonlinear charging function (E-VRP-NL) was recently introduced to account for the more realistic nonlinear relationship between the time spent charging and the amount of energy charged. We propose two new formulations for this problem. We first develop an arc-based tracking of the time and the state of charge which, according to our experiments, outperforms the classical node-based tracking of these values. To avoid replicating the charging stations nodes, as done for both node and arc based formulations, we also introduce a path-based model. We develop an algorithm to generate a tractable number of these paths. This path-based model outperforms the classical models in our experiments. We also propose a new model, a heuristic, and an exact labeling algorithm for the problem of finding the optimal charging decisions for a given route. Extensive computational results show that charging decisions considerably impact the quality of the E-VRP-NL solutions. Indeed, we improve 23 out of 120 best known E-VRP-NL solutions by solely revising the charging decisions.
2019
Electric vehicle routing problem with nonlinear charging function; Labeling algorithm; Mixed integer linear programming; Vehicle routing problem; Computer Science (all); Modeling and Simulation; Management Science and Operations Research
File in questo prodotto:
File Dimensione Formato  
paper2.pdf

Accesso riservato

Dimensione 1.67 MB
Formato Adobe PDF
1.67 MB Adobe PDF   Visualizza/Apri
11311-1087446_Jabali.pdf

Open Access dal 20/12/2020

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 799.42 kB
Formato Adobe PDF
799.42 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1087446
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 128
  • ???jsp.display-item.citation.isi??? 111
social impact