We address an Electric Vehicle Routing Problem with Time Windows (E-VRPTW) considering several real-like factors in the energy consumption model, e.g., the payload and the vehicle speed. We model E-VRPTW as a Mixed Integer Linear Program (MILP) where the speeds of vehicles are continuous variables that can vary between a minimum and a maximum value. Moreover, the proposed MILP formulation is cloneless since it allows using more than once the same recharging station without introducing dummy copies of it. To efficiently solve large-sized instances of the problem, we design a Random Kernel Search (RKS) matheuristic approach, based on the cloneless MILP formulation, that in turn exploits another matheuristic, called Random k-Degree Search (RkDS), to generate an initial feasible solution. We compare the results produced by a MILP solver using the MILP formulation with the ones obtained by the RKS on instances up to 100 customers derived from the benchmark instances of E-VRPTW. We show that the proposed matheuristic outperforms the cloneless MILP formulation on the medium/large-sized instances and also that it is robust, being not significantly sensitive to the values of the parameters used by the RkDS to generate the initial solution and to the initial time limit for the restricted MILP models.

A matheuristic for the electric vehicle routing problem with time windows and a realistic energy consumption model

Paolucci M.;
2023-01-01

Abstract

We address an Electric Vehicle Routing Problem with Time Windows (E-VRPTW) considering several real-like factors in the energy consumption model, e.g., the payload and the vehicle speed. We model E-VRPTW as a Mixed Integer Linear Program (MILP) where the speeds of vehicles are continuous variables that can vary between a minimum and a maximum value. Moreover, the proposed MILP formulation is cloneless since it allows using more than once the same recharging station without introducing dummy copies of it. To efficiently solve large-sized instances of the problem, we design a Random Kernel Search (RKS) matheuristic approach, based on the cloneless MILP formulation, that in turn exploits another matheuristic, called Random k-Degree Search (RkDS), to generate an initial feasible solution. We compare the results produced by a MILP solver using the MILP formulation with the ones obtained by the RKS on instances up to 100 customers derived from the benchmark instances of E-VRPTW. We show that the proposed matheuristic outperforms the cloneless MILP formulation on the medium/large-sized instances and also that it is robust, being not significantly sensitive to the values of the parameters used by the RkDS to generate the initial solution and to the initial time limit for the restricted MILP models.
File in questo prodotto:
File Dimensione Formato  
COR_2023.pdf

accesso chiuso

Tipologia: Documento in versione editoriale
Dimensione 1.12 MB
Formato Adobe PDF
1.12 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11567/1120395
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 8
social impact