Dra. Diana Lucía Huerta Muñoz

diana.huerta.lm@gmail.com

Diana Lucía Huerta Muñoz es Maestra en Ciencias en Ingeniería de Sistemas por la Universidad Autónoma de Nuevo León y Doctora en Estadística e Investigación Operativa por la Universidad Politécnica de Cataluña, España, obteniendo su grado en 2018. Además, realizó una estancia posdoctoral en la universidad de Brescia, Italia en el periodo 2018-2019. Actualmente realiza una estancia posdoctoral en el Posgrado en Ingeniería de Sistemas de la Facultad de Ingeniería Mecánica y Eléctrica de la UANL. Sus áreas de investigación incluyen métodos mate-heurísticos y modelos unificados para el problema de rutas de vehículos (VRP por sus siglas en inglés).

   

A solution algorithm for the integration of Vehicle Routing Problems

 13/agosto/2021  Seminario PISIS-UANL 2021      Asistencia : 21

Introducción

El Vehicle Routing Problem (VRP) es un problema clásico en la optimización combinatoria y tiene por objetivo determinar el mejor diseño de rutas de vehículos que minimicen los costos totales de distribución sujetos a restricciones de demanda y capacidad. En esta charla, la Dra. Diana Lucía Huerta Muñoz nos presenta los resultados preliminares de la aplicación de un método novedoso llamado Kernel Search (KS) perteneciente a las mate-heurísticas con el que se intenta resolver cinco de las variantes más populares del VRP al resolver un modelo de Programación Lineal Entera Mixta (MILP) unificado en cada iteración del algoritmo. A pesar de ser un método de solución relativamente nuevo, los resultados revelan que el método tiene mucho potencial para resolver problemas combinatorios como el VRP.

Resumen

Al inicio de la charla, la Dra. Diana Lucía Huerta Muñoz inicia presentando cinco variantes del VRP, las que incluyen: ruteo capacitado (CVRP), ruteo con ventanas de tiempo (VRPTW), ruteo con múltiples entregas a clientes (SDVRP), ruteo multi-periodo (PVRP) y ruteo de inventarios (IRP). Posteriormente, presenta un modelo unificado de tipo MILP que agrupa estas cinco restricciones.
El modelo presentado es resuelto mediante un método mate-heurístico denominado KS. Este método, que originalmente fue creado para resolver el problema de la mochila multidimensional, se ha extendido a resolver otros tipos de problemas como es el caso del VRP. La idea del método de KS es crear subconjuntos de variables enteras o binarias del problema. Uno de los subconjuntos será llamado kernel, el cual contiene aquellas variables que tienen una mayor probabilidad de ser parte de la solución óptima, los demás subconjuntos, llamados buckets, contienen el resto de las variables ordenadas mediante algún criterio. La idea de la partición es resolver un problema reducido que se conformará del kernel y de algunos de los buckets, los cuales son evaluados de manera iterativa usando como criterio de ordenamiento los costos reducidos. En cada iteración un bucket distinto es evaluado y, si este mejora la solución actual, el kernel se actualiza agregando las variables del bucket que mejoraron la solución mientras que el resto se descarta. El método de solución termina cuando todos los buckets son evaluados o se alcanza un tiempo límite de optimización.
Algunas de las ventajas del método, en palabras de la doctora, es que presenta una fácil implementación y un número reducido de parámetros, además de una estructura flexible. Sin embargo, también mencionó que la calidad de la solución depende de la formación de los subconjuntos antes mencionados, por ejemplo, hacer kernels y buckets grandes son computacionalmente más costosos; por el contrario, si el kernel y buckets son de tamaño muy pequeño puede proporcionar soluciones en menor tiempo pero posiblemente de menor calidad. El método requirió algunas implementaciones específicas para adaptarse al problema unificado de las cinco variantes del VRP, cada uno de ellas recibió diferentes tratamientos con el objetivo de hacerlos coincidir con el CVRP, para ello se adaptaron los datos de entrada del SDVRP, VRPTW, PVRP e IRP, así mismo se agregaron variables de decisión y restricciones al VRPTW, PVRP e IRP. Por último, se agregó una nueva función objetivo al IRP, ya que esta es la variante que más se diferencia del resto.
El método fue probado con instancias tomadas de literatura, resolviendo cada una de las cinco variantes del VRP modificando el tamaño del kernel y de los buckets, así como comparando contra la mejor solución reportada en la literatura. Se estableció un tiempo límite de optimización de 7200 segundos, el lenguaje de programación utilizado fue C++ y el solver de optimización con el cual se resolvieron los MILPs fue CPLEX.

Conclusiones

Los resultados reportados nos señalan que existen aún áreas de oportunidad para mejorar esta metodología pues las soluciones obtenidas en comparación con las reportadas discrepan en no más de un 5%, además, existe una diferencia en los tiempos de cómputo entre el tiempo en el que se obtiene la mejor solución y el tiempo en el que acaba el solver, tiempo que era considerablemente menor al criterio de paro establecido.
Algunas estrategias de mejora detectadas son analizar detenidamente el comportamiento de algunas instancias, reforzar el MILP del problema, considerar reducir el tamaño del kernel después de n-iteraciones, así como buscar estrategias que ayuden a reducir el kernel de manera adecuada.

Enlaces relevantes

Reseñas anteriores