Algoritmos de búsqueda de vecindario variable para resolver el problema de enrutamiento de vehículos eléctricos con recogida y entrega simultánea
Autores: Yilmaz, Yusuf; Kalayci, Can B.
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Algoritmos de búsqueda de vecindario variable para resolver el problema de enrutamiento de vehículos eléctricos con recogida y entrega simultánea
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Vehículos eléctricos
Problema de enrutamiento
Recogida y entrega simultáneas
Estaciones de carga
Búsqueda de vecindario variable
Calidad de la solución
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 26
Citaciones: Sin citaciones
Este artículo aborda el Problema de Enrutamiento de Vehículos Eléctricos con Recogida y Entrega Simultánea (EVRP-SPD), en el cual los vehículos eléctricos (VE) entregan simultáneamente mercancías a los clientes y recogen mercancías de ellos. Debido a la capacidad limitada de la batería de los VE, su rango es más corto que el de los vehículos de combustión interna. En el EVRP, además del depósito y los clientes, también hay estaciones de carga (CS) porque los VE necesitan cargarse cuando su batería está vacía. El problema se formula como un modelo lineal entero, y se propone una solución eficiente para minimizar la distancia total recorrida. Para crear una solución inicial factible, se utiliza el algoritmo de ahorro de Clarke y Wright. Se prueban varias variantes de búsqueda en vecindarios variables, y se utiliza el algoritmo de búsqueda en vecindarios de variables reducidas para encontrar la mejor solución en un tiempo razonable. Se realizan experimentos computacionales con instancias de referencia para evaluar la efectividad de nuestro enfoque en términos de calidad de la solución y tiempo. Los resultados obtenidos muestran que el método propuesto puede lograr soluciones eficientes en términos de calidad de la solución y tiempo en todas las instancias de referencia.
Descripción
Este artículo aborda el Problema de Enrutamiento de Vehículos Eléctricos con Recogida y Entrega Simultánea (EVRP-SPD), en el cual los vehículos eléctricos (VE) entregan simultáneamente mercancías a los clientes y recogen mercancías de ellos. Debido a la capacidad limitada de la batería de los VE, su rango es más corto que el de los vehículos de combustión interna. En el EVRP, además del depósito y los clientes, también hay estaciones de carga (CS) porque los VE necesitan cargarse cuando su batería está vacía. El problema se formula como un modelo lineal entero, y se propone una solución eficiente para minimizar la distancia total recorrida. Para crear una solución inicial factible, se utiliza el algoritmo de ahorro de Clarke y Wright. Se prueban varias variantes de búsqueda en vecindarios variables, y se utiliza el algoritmo de búsqueda en vecindarios de variables reducidas para encontrar la mejor solución en un tiempo razonable. Se realizan experimentos computacionales con instancias de referencia para evaluar la efectividad de nuestro enfoque en términos de calidad de la solución y tiempo. Los resultados obtenidos muestran que el método propuesto puede lograr soluciones eficientes en términos de calidad de la solución y tiempo en todas las instancias de referencia.