logo móvil
Contáctanos

Un metaheurístico de búsqueda de vecindario grande multiobjetivo para el problema de enrutamiento de vehículos con ventanas de tiempo

Autores: Konstantakopoulos, Grigorios D.; Gayialis, Sotiris P.; Kechagias, Evripidis P.; Papadopoulos, Georgios A.; Tatsiopoulos, Ilias P.

Idioma: Inglés

Editor: MDPI

Año: 2020

Descargar PDF

Acceso abierto

Artículo científico
2020

Un metaheurístico de búsqueda de vecindario grande multiobjetivo para el problema de enrutamiento de vehículos con ventanas de tiempo


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Problema de enrutamiento de vehículos
Ventanas de tiempo
Problema de optimización
Multiobjetivo
Algoritmo
Eficiencia

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 29

Citaciones: Sin citaciones


Descripción
El Problema de Enrutamiento de Vehículos con Ventanas de Tiempo (VRPTW) es un problema de optimización NP-Hard que ha sido ampliamente estudiado por investigadores debido a sus aplicaciones en casos de la vida real en el sector de distribución y logística. En este problema, los clientes definen un intervalo de tiempo, dentro del cual deben ser atendidos por vehículos de capacidad estándar. El objetivo es definir rutas rentables, minimizando tanto el número de vehículos como la distancia total recorrida. Cuando buscamos minimizar ambos atributos al mismo tiempo, el problema se considera como multiobjetivo. Aunque se han desarrollado numerosos algoritmos exactos, heurísticos y metaheurísticos para resolver varios problemas de enrutamiento de vehículos, incluido el VRPTW, solo unos pocos de ellos abordan estos problemas como multiobjetivo. En el presente artículo, se desarrolla un algoritmo de Búsqueda de Vecindario Grande Multiobjetivo (MOLNS) para resolver el VRPTW. El algoritmo se implementa utilizando el lenguaje de programación Python, y se evalúa en 56 instancias de referencia de Solomon con 100 clientes, así como en instancias de referencia de Gehring y Homberger con 1000 clientes. Los resultados obtenidos del algoritmo se comparan con los mejores publicados, con el fin de validar la eficiencia y el rendimiento del algoritmo. Se demuestra que el algoritmo es eficiente tanto en la calidad de los resultados, ya que ofrece tres nuevas soluciones óptimas en el conjunto de datos de Solomon y produce resultados casi óptimos en la mayoría de las instancias, como en términos de tiempo computacional, ya que, incluso en casos con hasta 1000 clientes, se obtienen resultados de buena calidad en menos de 15 minutos. Teniendo el potencial de resolver eficazmente problemas de distribución de la vida real, el presente artículo también discute una aplicación práctica de este algoritmo.

Otros recursos que podrían interesarte

Temas Virtualpro