The location routing problem using electric vehicles with constrained distance

Abstract

The introduction of Electric Vehicles (EVs) in modern fleets facilitates a shift towards greener road transportation practices. However, the driving ranges of EVs are limited by the duration of their batteries, which raises some operational challenges. This paper discusses the Location Routing Problem with a Constrained Distance (LRPCD), which is a natural extension of the Location Routing Problem when EVs are utilized. A fast multi-start heuristic and a metaheuristic are proposed to solve the LRPCD. The former combines biased-randomization techniques with the well-known Tillman’s heuristic for the Multi-Depot Vehicle Routing Problem. The latter incorporates the biased-randomized approach into the Variable Neighborhood Search (VNS) framework. A series of computational experiments show that the multi-start heuristic is able to generate good-quality solutions in just a few seconds, while the biased-rendomized VNS metaheuristic provides higher-quality solutions by employing more computational time.

La introducción de vehículos eléctricos (EV) en flotas modernas facilita un cambio hacia prácticas de transporte por carretera más ecológicas. Sin embargo, la autonomía de conducción de los vehículos eléctricos está limitada por la duración de sus baterías, lo que plantea algunos desafíos operativos. Este documento analiza el problema de enrutamiento de ubicación con una distancia restringida (LRPCD), que es una extensión natural del problema de enrutamiento de ubicación cuando se utilizan vehículos eléctricos. Se propone una heurística rápida de inicio múltiple y una metaheurística para resolver el LRPCD. El primero combina técnicas de aleatorización sesgada con la conocida heurística de Tillman para el problema de enrutamiento de vehículos de varios depósitos. Este último incorpora el enfoque aleatorizado sesgado en la búsqueda de vecindario variable .(VNS) marco. Una serie de experimentos computacionales muestran que la heurística de inicio múltiple puede generar soluciones de buena calidad en solo unos segundos, mientras que la metaheurística VNS aleatoria y sesgada proporciona soluciones de mayor calidad al emplear más tiempo computacional.