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

Autor: Ola Jabali, Gilbert Laporte, Aurélien Froger, Jorge E. Mendoza
Přispěvatelé: Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Politecnico di Milano [Milan] (POLIMI), HEC Montréal (HEC Montréal), ANR-15-CE22-0005,e-VRO,Optimisation des Tournées de Véhicules Electriques(2015), Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), ANR-15-CE22-0005-01,e-VRO,Electric Vehicle Routing Optimization(2015), Froger, Aurélien, Optimisation des Tournées de Véhicules Electriques - - e-VRO2015 - ANR-15-CE22-0005 - AAPG2015 - VALID
Rok vydání: 2019
Předmět:
0209 industrial biotechnology
Mathematical optimization
business.product_category
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO]
General Computer Science
Heuristic (computer science)
Computer science
0211 other engineering and technologies
02 engineering and technology
Management Science and Operations Research
7. Clean energy
020901 industrial engineering & automation
Mixed integer linear programming
Vehicle routing problem
Electric vehicle
Electric vehicle routing problem with nonlinear charging function
Labeling algorithm
Computer Science (all)
Modeling and Simulation
ComputingMilieux_MISCELLANEOUS
021103 operations research
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Nonlinear system
State of charge
Path (graph theory)
Node (circuits)
Routing (electronic design automation)
business
Zdroj: Computers and Operations Research
Computers and Operations Research, Elsevier, 2019, 104, pp.256-294
ISSN: 0305-0548
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: