Dra. Iris Abril Martínez Salazar

La doctora Iris Abril Martínez Salazar es egresada del Instituto Tecnológico de Estudios Superiores de Monterrey en el año 2005 como ingeniera en la especialidad de industrial y de sistemas, en el año 2007 obtiene una maestría en calidad en productividad y calidad de sistemas, y finalmente en el año 2011 recibe el título de doctora en ciencias de la ingeniería. La doctora cuenta con un perfil PROMEP y es miembro del Sistema Nacional de Investigadores (SNI) nivel 1. Actualmente es docente del programa de posgrado de Ingeniería de Sistemas en la Universidad Autónoma de Nuevo León (UANL), y sus intereses de investigación son los problemas de secuenciación, calendarización, transporte y logística, metaheurísticas y optimización multiobjetivo.

Problemas de diseño de rutas centrados en el cliente

  19/noviembre/2021  Seminario PISIS-UANL 2021      Asistencia : 20

Introducción

En esta sesión la Dra. Iris nos habla sobre la estructura y características de los problemas de ruteo de vehículos centrados en el cliente, con el objetivo de minimizar los tiempos de espera de los clientes para recibir su servicio. Este tipo de problemas presentan retos computacionales adicionales al tradicional objetivo de minimizar costos económicos o distancia de viaje de un problema de enrutamiento de vehículos clásico.

Resumen

El problema de enrutamiento de vehículos (VRP, por su siglas en inglés) es un problema de optimización combinatoria y de programación entera que busca la programación óptima de rutas para una flota de vehículos, satisfaciendo la demanda de un conjunto de clientes. También es considerado una generalización del problema del agente viajero (TSP, por sus siglas en inglés). Los elementos de un VRP son los clientes, depósitos y una flota de vehículos. De acuerdo a las características particulares del problema pueden aparecer diferentes restricciones, entre ellas: capacidad limitada de los vehículos; clientes deben ser visitados dentro de una ventana de tiempo; múltiples depósitos o puntos de suministro; clientes atendidos por varios vehículos o suministro dividido. Además, algunas de las variables del problema son aleatorias, tales como el número de clientes, sus demandas, etc.
El problema de mínima latencia (MLP) también es conocido como un problema de ruteo centrado en los clientes. Un objetivo centrado en el cliente aplica cuando la prioridad es llegar a un lugar de manera rápida y equitativa para todos los clientes. Algunas aplicaciones de uso del MLP son la distribución de suministros en caso de catástrofes y de ayuda humanitaria, además de distribución de alimentos perecederos, entre otras.
Un MLP busca satisfacer a todos los clientes estableciendo un camino hamiltoniano, partiendo del nodo raíz que minimice la suma de las longitudes de los caminos a cada uno de los vértices. La latencia es la medida de tiempo de espera de un sistema y en una red está asociada a la métrica usada para evaluar la longitud de un camino desde un vértice raíz hasta cada uno de los vértices en la misma.
El trabajo de investigación presentado está relacionado con resolver una extensión del problema de ruteo de k-reparadores (kTPR), con el objetivo de mínima latencia. Este problema es una generalización del MLP donde se debe de diseñar más de una ruta. La extensión estudiada es el denominado mdk-TRP, en este tipo de problemas se tienen dos decisiones más que tomar. Se tienen dos conjuntos de nodos que se pueden activar para que salgan los vehículos si es que se tienen que utilizar todos, además de decidir dónde se deben sitúan estos vehículos. El objetivo es minimizar el tiempo de visita a cada cliente en un nodo.
Para resolver el problema en instancias grandes se usó el marco de un algoritmo genético con operadores de mejoramiento y mutación. Para este proceso se hizo una cruza, seleccionando un padre al azar de 50 de las mejores soluciones, un segundo padre se selecciona al azar de entre toda la población, y por último se consideran 3 tipos de cruzamiento para generar a los hijos.

Se realiza una búsqueda local con intercambio de dos clientes y la estrategia del primer mejoramiento. Este algoritmo incluye una etapa de diversificación donde las soluciones que no pertenecen al conjunto elite son generadas de nuevo de manera aleatoria.

Conclusiones

En la charla se presenta un conjunto de problemas de ruteo centrados en las necesidades del cliente, y se mencionan ejemplos de cómo representar la función objetivo y sus restricciones en un modelo matemático de programación.

Se observó que el enfoque de centrar el problema de ruteo en el cliente aumenta dramáticamente la complejidad del problema que lo hace un problema difícil de resolver para instancias de gran tamaño. Las formulaciones presentadas, basadas en una red multinivel muestran efectividad para resolver problemas de este tipo en instancias medianas y pequeñas .

Se presentó la generalización de un problema de k-TRP a un mdk-TRP, y para resolverlo se usaron algoritmos genéticos. El algoritmo aproximado mostró buenos resultados y logró obtener al menos una solución factible de todas las instancias de prueba.