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
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
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.
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.