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

The authors 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. The authors 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, the authors 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. The authors 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. The authors 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.

• Record URL:
  • https://doi.org/10.1016/j.cor.2023.106261
• Record URL:
  • http://www.sciencedirect.com/science/article/pii/S0305054823001259
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1793974
• Supplemental Notes:
  • © 2023 Elsevier Ltd. All rights reserved. Abstract reprinted with permission of Elsevier.
• Authors:
  • Bruglieri, M
  • 0000-0002-4517-873X
  • Paolucci, M
  • Pisacane, O
• Publication Date: 2023-9

Language

• English

Media Info

• Media Type: Web
• Features: References;
• Pagination: 106261
• Serial:
  • Computers & Operations Research
  • Volume: 157
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 0305-0548
  • Serial URL: https://www.sciencedirect.com/journal/computers-and-operations-research

Subject/Index Terms

• TRT Terms: Delivery vehicles; Electric vehicles; Energy consumption; Mixed integer programming; Routing; Time windows
• Identifier Terms: Vehicle Routing Problem
• Subject Areas: Freight Transportation; Operations and Traffic Management; Planning and Forecasting;

Filing Info

• Accession Number: 01886204
• Record Type: Publication
• Files: TRIS
• Created Date: Jun 28 2023 4:29PM