XXV Workshop de Investigadores en Ciencias de la Computación (WICC 2023) - UNNOBA – Red de Universidades de Carreras de Informática RedUNCI
Libro de actas (ver página 101)
Resolución de problemas regionales NP-duros usando técnicas de optimización
Carolina Salto2,3, Gabriela Minetti2, Hugo Alfonso2,
Carlos Bermúdez2, M.Juliana Dielschneider
Del Bono2,
Luciano Bessoni2,
Javier Vargas2, José Luis Hernandez1, Mercedes Carnero1
1
Facultad de Ingeniería - Universidad
Nacional de Río Cuarto
2
Laboratorio de Investigación en Sistemas
Inteligentes (LISI)
Facultad de Ingeniería - Universidad Nacional de La Pampa – 3 CONICET e-mail: {saltoc, minettig, alfonsoh, bermudezc, juliana, jvargas}@ing.unlpam.edu.ar
{mcarnero,jlh}@ing.unrc.edu.ar
Resumen
En este artículo
se introducen dos de las líneas de investigación que se desarrollan en el
Laboratorio de Sistemas Inteligentes (LISI), relacionadas con problemas de
optimización NP-duros de carácter regional: diseño de redes distribución de
agua y logística de distribución de carga y paquetería. En la actualidad, las
empresas públicas de suministro de agua proporcionan más del 90% del
abastecimiento mundial, por lo que un sistema seguro de distribución de agua es
fundamental para cualquier ciudad. La importancia, el enorme costo de capital
del sistema y el creciente tamaño de las ciudades conducen a la optimización de
la red de distribución de agua. En esta línea de investigación, se proponen y
analizan dos algoritmos metaheurísticos para optimizar el diseño de la red de
agua de un nuevo barrio de la ciudad de General Pico, con el objetivo de
minimizar el costo total de la inversión.
La logística remite a flujos de materiales
y de información; a lugares de manipulación, depósito y transformación de las
mercancías; a redes y nodos de circulación; y a tiempos de movimiento y de
espera que responden a aspectos materiales (las infraestructuras, los
transportes y las cargas) y también a aspectos funcionales (los servicios, las
normativas y regulaciones). En suma, la logística implica un uso del territorio
en el tiempo, una convergencia espacio-temporal, una organización y
sincronización de flujos a través de estrategias sobre los nodos y las redes.
La Provincia de La Pampa cuenta con gran potencial para constituirse en un
centro logístico de distribución a nivel nacional, por ello se considera
importante que esté consolidada en la búsqueda de propuestas innovadoras para
introducir al sector. En consecuencia, la segunda línea de investigación se
enfoca en modelar las características de la logística de distribución de cargas
y paquetería en la región con el objetivo de minimizar los costos operativos y
maximizar la calidad del servicio.
Palabras claves: Optimización, Logística, Inteligencia
Artificial, Diseño de redes
CONTEXTO
Desde su creación en 1998, el Laboratorio de
Investigación de Sistemas Inteligentes (LISI), perteneciente a la Facultad de
Ingeniería (FI) de la Universidad Nacional de La Pampa (UNLPam), se ha abocado
al estudio de algoritmos cada vez más eficientes para la solución de problemas
complejos, tanto de optimización como de diseño. Actualmente, dos de sus líneas
de investigación están relacionadas con la resolución de problemas de
optimización NP-duros de la región de influencia de dicho laboratorio: diseño
óptimo de redes de distribución de agua y optimización de la logística de
distribución de cargas y paquetería. Estas líneas de investigación se
desarrollan en el marco de dos proyectos de investigación: "Big data
optimization con algoritmos metaheurísticos utilizando frameworks de
computación distribuida", acreditado por la FI, y "Optimización de la
logística de distribución utilizando técnicas de la Inteligencia
Artificial" (POIRe), acreditado por la UNLPam.
En ambas líneas, el objetivo
principal consiste en obtener algoritmos inteligentes que, además de brindar
soluciones de calidad a las problemáticas planteadas con poco esfuerzo
computacional, requieran bajo costo de implementación. Cabe destacar que desde
hace varios años, los integrantes de este laboratorio mantienen una importante
vinculación con investigadores de universidades argentinas (Universidad
Nacional de San Luis y Universidad Nacional de Rio Cuarto-UNRC) y de la
Universidad de Málaga (España), con quienes se realizan trabajos conjuntos. En
particular este trabajo se desarrollo con investigadores de la UNRC. La primera
línea de investigación, diseño de redes de agua, se enmarca en la ciudad de
General Pico, donde el agua potable proviene de unas 100 perforaciones para
extracción del acuífero subterráneo que se extiende desde General Pico a la
localidad de Dorila, uno de los pocos recursos hídricos accesibles y aptos para
el consumo. Cada pozo extrae un promedio de 9000 litros/hora. El agua extraída
se transporta hasta una cisterna principal subterránea, que junto a otras cinco
cisternas abastecen a toda la ciudad. Todo esto contribuye a que la
optimización del diseño de redes de distribución de agua para nuevos barrios
sea un problema de alta complejidad.
La segunda línea de investigación, logística de
distribución de carga, se encuadra en la Provincia de La Pampa situada en el
centro geográfico de la República Argentina y considerada la puerta de ingreso
a la Región Patagónica. Por ende, cuenta con gran potencial para constituirse
en un centro logístico de distribución para el territorio argentino. Dado que
los costos de transporte se hallan entre un tercio y dos tercios de los costos
logísticos totales, mejorar la eficiencia mediante la máxima utilización del
equipo de transporte y de su personal es una preocupación importante. Un
problema frecuente en la toma de decisiones es reducir los costos de transporte
y mejorar el servicio al cliente encontrando las mejores rutas.
I. INTRODUCCIÓN
El diseño óptimo de redes de
distribución de agua potable y la optimización de la logística de distribución
de cargas y paquetería son problemas de decisión complejos del mundo real que,
modelados como problemas de optimización, pertenecen a la clase NP-Duros.
El objetivo del problema de optimización del diseño
de redes de distribución de agua (Water Distribution Network Design
Optimization - WDND) es minimizar el costo total de inversión (Total Investment
Cost - TIC) de una red de distribución de agua. Un grafo conexo conformado por
un conjunto de nodos N = {n1,n2,...}, un conjunto de tuberias P = {p1,p2,...},
un conjunto de subredes o loops internos L = {l1,l2,...}, y un conjunto de tipos de tuberías disponibles en el
mercado T = {t1,t2,...} representan la red de agua. A partir de este modelo,
se minimiza el costo total de la inversión, siguiendo la fórmula mostrada en la
Ecuación 1.
(1)
donde ICt es el costo de un tubo p del
tipo t, Lp es
la longitud del tubo y xp,t en una variable binaria que indica si el
tubo p es
del tipo t o
no. Función restringida por las leyes físicas de conservación de masa y
energía, la demanda de presión mínima en cada nodo y la máxima velocidad en la
tubería, en cada momento τ ∈T .
En el campo de la investigación operativa [1], la
optimización de la logística de distribución de cargas y paquetería se agrupa
en la clase de problemas del enrutamiento vehicular (VRP, sus siglas en Inglés)
[2]. El VRP clásico consiste en determinar las rutas que debe tomar una
determinada flota de vehículos para recolectar y/o distribuir artículos en
ubicaciones conocidas de clientes. Cada artículo suele tener asociado un
determinado tamaño o peso. La cantidad total (en términos de tamaño o peso) de
los artículos recolectados por un vehículo no puede exceder su capacidad. En
esta versión de VRP, se supone que todos los datos (demandas del cliente,
tiempos de viaje, ventanas de tiempo, etc.) se conocen de antemano. El
responsable de la toma de decisiones, tanto en grandes compañías como en
pequeñas empresas, debe planificar con anticipación las rutas de los vehículos
para satisfacer las demandas de los clientes a un costo de viaje mínimo. El
costo del viaje puede incluir, entre otros: tiempo de viaje, horas hombre,
viáticos, combustible y peajes [3], [4]. Desafortunadamente, el VRP es
fuertemente NP-duro incluso para un solo objetivo, ya que el problema del
viajante de comercio (TSP, por sus siglas en inglés) [5] puede reducirse
polinomialmente a él [6].
En el VRP clásico se establecen rutas de menor costo desde
un depósito central a un conjunto de puntos dispersos geográficamente
(clientes, tiendas, escuelas, ciudades, almacenes, etc.) con diversas demandas.
Cada cliente debe ser atendido exactamente una vez por un solo vehículo, y cada
vehículo tiene una capacidad limitada. Una extensión más realista es el
Problema de generación de rutas para vehículos con ventanas de tiempos (VRPTW),
que cuenta con muchas aplicaciones en el mundo real; aquí se asocia una ventana
de tiempo a cada cliente. Es decir, además de la restricción de capacidad del
vehículo, cada cliente proporciona un marco de tiempo dentro del cual se debe
completar un servicio o tarea en particular, como cargar o descargar un
vehículo. Un vehículo puede llegar temprano, pero debe esperar hasta que sea
posible la hora de inicio del servicio. El objetivo del VRPTW es minimizar la
cantidad de vehículos y la distancia total recorrida para atender a los
clientes sin violar las limitaciones de capacidad y ventana de tiempo.
La resolución de estos problemas
de alta complejidad requiere de métodos eficaces, confiables y fáciles de usar
que, además de tener en cuenta los costos de capital y operativos, consideren
el rendimiento, la confiabilidad hidráulica y la gestión competente de la
energía en el caso de WDND y la satisfacción del cliente y la fiabilidad del
sistema para el VRPTW. En consecuencia, las técnicas de solución capaces de
producir soluciones de alta calidad en un tiempo limitado, como las heurísticas
y las metaheurísticas [7], son de primordial importancia.Estas técnicas, que
pertenecen a la clase de algoritmos de búsqueda estocásticos, reducen de forma
significativa la complejidad temporal del proceso de búsqueda. Por otro lado,
la paralelización de la búsqueda, además de disminuir los tiempos, permite
aumentar la calidad de las soluciones halladas. Esto implica el estudio de
diferentes plataformas actuales de hardware (procesadores multicores, unidades
de procesamiento gráficas, ambientes cloud) y de software (Hadoop, Spark, MPI,
High Processing Computing en general).
II. LÍNEA
DE INVESTIGACIÓN Y DESARROLLO
En esta sección se presenta el tratamiento dado a los
problemas, WDND y VRP, abordados en cada una de las líneas de investigación
enunciadas anteriormente.
A. Diseño de redes de distribución de agua
Actualmente, las formulaciones de WDND incluyen la
extensión a múltiples períodos, es decir, patrones de demanda que varían en el
tiempo, que son formulaciones de problemas realistas, pero también más
complejas que las tradicionales. Algunos trabajos expresaron el problema de
diseño como un problema de optimización multiobjetivo y aplicaron un algoritmo
evolutivo multiobjetivo [8]. También se desarrolló un algoritmo genético para
resolver seis pequeñas redes [9], considerando la restricción de velocidad del
agua que fluye a través de las tuberías. En [10] también consideraron esta
restricción, pero los autores usaron programación matemática en redes más
grandes y más cercanas a la realidad. Los autores en [11], [12] utilizaron
otras metaheurísticas para abordar formulaciones de WDND más complejas. En la
búsqueda local iterativa (ILS) presentada en [13] se consideró que cada nodo de
demanda tiene un patrón de demanda de agua de 24 horas, incluyendo una nueva
restricción relacionada con el límite de la velocidad máxima del agua a través
de las tuberías.
El crecimiento de las ciudades también requiere de
este complejo proceso de diseño, como es el caso de General Pico (La Pampa,
Argentina). En particular, se necesita optimizar un WDND independiente de un
nuevo barrio de cinco km2, sujeto a demandas
multiperiodo, restricciones hidráulicas, entre otras restricciones. Una
cooperativa pública está a cargo de distribuir este elemento esencial en esta
ciudad, lo que requiere un sistema de optimización para determinar la mejor
solución de ingeniería que cumpla con los criterios de diseño establecidos y
minimice los costos de capital. Nuestro objetivo de investigación es
desarrollar una solución óptima basada en algoritmos de optimización de última
generación, que pretende apoyar la toma de decisiones para diseñar, planificar
y gestionar sistemas de agua complejos.
Proponemos y comparamos metaheurísticas basadas en Tabu Search (TS) y Simulated Annealing (SA) para resolver el problema WDND,
optimizando los diámetros de las tuberías y minimizando el costo total de
inversión. El método basado en TS, llamado SOTS (Strategic Oscillations Tabu Search), adapta la técnica
constructivo-destructiva llamada Oscilación Estratégica [14] para mejorar las
capacidades de intensificación y diversificación de la búsqueda. Se utiliza un
algoritmo de optimización híbrido basado en Simulated
Annealing (HSA) [15] mejorado con un procedimiento de búsqueda local basado
en GRASP [13] para minimizar el costo de la red de agua. Probamos el
rendimiento de SOTS y HSA con una red de distribución de tamaño medio del mundo
real. Las principales contribuciones de este trabajo son las siguientes: i) La adaptación de la técnica SO ad hoc
al problema WDND (fases constructiva y destructiva de SOTS), y ii) Resolución de una red de
distribución del mundo real.
B. Logística de la distribución de cargas y paquetería
Para abordar este problema de
optimización relacionado con la logística de distribución de cargas y
paquetería, se propone el desarrollo de software logístico, que incorpore
herramientas basadas en inteligencia artificial, como soporte para la toma de
decisiones a nivel gerencial y asistido por herramientas que permitan evaluar
la incidencia de la matriz de costos y buscar el equilibrio del sistema. Debe
ser capaz de diseñar rutas de distribución eficientes para incrementar la
eficiencia operacional, reducir costos y aumentar la satisfacción de los
clientes. Además, se pretende determinar los factores de costos relacionados a
cada ruta planificada, su clasificación en cuanto a variabilidad y la
asignación de un valor, para estudiar la incidencia de cada uno de ellos en el
costo total de dicha ruta y contar con información importante para la toma de
decisiones. El VRPTW ha recibido mucha atención debido a la aplicabilidad de
las restricciones de ventana de tiempo en situaciones del mundo real. Se trata
de un problema NP-Completo y las instancias con 100 clientes o más son muy
difíciles de resolver de manera óptima. Representamos el VRPTW como un problema
multiobjetivo, en el que las dos dimensiones objetivas son la cantidad de
vehículos y el costo total (distancia). Una ventaja de este enfoque es que no
es necesario derivar pesos para una fórmula de puntuación de suma ponderada.
Esto evita la introducción de un sesgo de solución hacia cualquiera de las dos
dimensiones.
Muchos investigadores han propuesto técnicas
exactas para resolver este problema, pero ha sido Kohl [16] quien ha
introducido uno de los métodos exactos más eficientes para el VRPTW; al
resolver varias instancias de hasta 100 clientes. Sin embargo, el costo
computacional de estos métodos es muy alto, siendo los métodos aproximados,
como las metaheurísticas, los que han resuelto este inconveniente (algoritmos
genéticos, estrategias evolutivas, enfriamiento simulado, búsqueda tabú, entre
otras) [17], [18], [19]). Debido a que resolver eficientemente las instancias
de VRPTW con más de 100 clientes sigue siendo un desafío, en nuestra línea de
investigación se propone combinar las ventajas de las metaheurísticas
multiobjetivo con heurísticas exactas para obtener soluciones de calidad con
bajo costo computacional.
III. RESULTADOS
ENCONTRADOS Y ESPERADOS
En esta sección se muestran y analizan, en primer
lugar, los resultados hallados a partir de la concreción de los objetivos
propuestos en la primera línea de investigación. En segundo lugar, se describe
qué resultados se esperan obtener en la línea de trabajo orientada a VRP. A. Diseño de redes de distribución de agua
A continuación se analiza el desempeño de los algoritmos
propuestos para optimizar el WDND de un nuevo barrio en la ciudad de General
Pico: SOTS y HSA. El algoritmo SOTS puede iniciar la búsqueda de soluciones con
costos de inversión totales muy altos y alcanza buenas soluciones en las
primeras etapas de la búsqueda, con un esfuerzo computacional relativamente
bajo en comparación con la heurística HSA. Esto se debe principalmente a la
fase de destrucción inteligente implementada. Sin embargo, a medida que avanza
la búsqueda, la disminución de los costos totales de inversión encontrados se
hace menor, la capacidad exploratoria disminuye y aumenta la cantidad de veces
que se ejecuta la función de evaluación. Un comportamiento similar se puede
observar en HSA. Las herramientas disponibles para evitar mínimos locales son
diferentes para los dos métodos: memoria a corto plazo y memoria a largo plazo
en el caso de SOTS, y aceptación de peores soluciones cuando la temperatura es
alta en el caso de HSA. Considerando que el espacio de posibles soluciones para
el problema dado es del orden de 10256,
la posibilidad de explorar diferentes regiones del problema utilizando una sola
técnica de búsqueda es limitada, y los esfuerzos para diseñar algoritmos para
el WDND podrían considerar estrategias cooperativas entre los dos métodos. El
trabajo futuro tiene como objetivo desarrollar algoritmos híbridos, combinando
las ventajas de SOTS y HSA y así minimizar sus debilidades.
B. Logística de la distribución de cargas y paquetería
A partir de las características del VRPTW relevadas en la
región pampeana y del problema modelado en consecuencia, se está en proceso del
diseño e implementar un software logístico como soporte para la toma de
decisiones a nivel gerencial de empresas que incluyan en sus actividades tareas
de distribución de cargas y paquetería. Dicha tecnología permitirá, a partir de
la consideración de las distintas variables y restricciones, conseguir el mayor
rendimiento y eficacia en los procesos logísticos. Para determinar la eficacia
del software logístico desarrollado para resolver el VRPTW, se utilizará un
conjunto de datos de referencia bien conocidos. Se esperan hallar soluciones
competitivas con las más conocidas en la literatura, así como también posibles
nuevas soluciones que no estén sesgadas hacia algunos de los objetivos
(cantidad de vehículos y el costo total).
IV. FORMACIÓN
DE RECURSOS HUMANOS
Cada año se incorporan al LISI
alumnos avanzados en la carrera Ingeniería en Sistemas como becarios de
investigación y también para realizar trabajos finales de carrera. El trabajo
con problemas actuales y regionales favorece la formación de los recursos
humanos en la actividad de transferencia de los resultados de la investigación
desarrollada. También es importante resaltar la interdisciplinariedad en el
tratamiento de las distintas propuestas ya que permite vincular áreas
ingenieriles.Por otra parte, los docentes-investigadores que integran el
proyecto realizan diversos cursos de posgrado relacionados con la temática del
proyecto, con el objetivo de sumar los créditos necesarios para cursar carreras
de posgrado.
REFERENCES
- F. S. Hillier and G. J. Lieberman, Introducción a la investigación de operaciones, 9th ed. McGRAWHILL/INTERAMERICANA EDITORES, 2012.
- G. B. Dantzig and J. H. Ramser, “The truck dispatching problem,” Management Science, vol. 6, no. 1, pp. 80–91, 1959.
- S. Chopra and P. Meindl, Administracion de la Cadena de Suministro: Estrategia Planeacion y Operacion, 5th ed. Pearson, 2013.
- R. Ballou, LOGÍSTICA. Administración de la cadena de suministros, 5th ed. Pearson, 2004.
- G. Dantzig, R. Fulkerson, and S. Johnson, “Solution of a large-scale traveling-salesman problem,” Journal of the Operations Research Society of America, vol. 2, no. 4, pp. 393–410, 1954. [Online]. Available: http://www.jstor.org/stable/166695
- J. K. Lenstra and A. H. G. R. Kan, “Complexity of vehicle routing and scheduling problems,” Networks, vol. 11, no. 2, pp. 221–227, 1981. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230110211
- E. Talbi, Metaheuristics: from Design to Implementation. Wiley, 2009.
- R. Farmani, G. A. Walters, and D. A. Savic, “Trade-off between total cost and reliability for anytown water distribution network,” Journal of Water Resources Planning and Management, vol. 131, no. 3, pp. 161–171, 2005.
- I. Gupta, A. Gupta, and P. Khanna, “Genetic algorithm for optimization of water distribution systems,” Environmental Modelling & Software, vol. 14, no. 5, pp. 437–446, 1999.
- C. Bragalli, C. D’Ambrosio, J. Lee, A. Lodi, and P. Toth, “On the optimal design of water distribution networks: a practical MINLP approach,” Optimization and Engineering, vol. 13, no. 2, pp. 219–246, 2012.
- R. Uma, “Optimal design of water distribution network using differential evolution,” International Journal of Science and Research (IJSR), vol. 5, no. 11, pp. 1515–1520, 2016.
- R. Mansouri and M. Mohamadizadeh, “Optimal design of water distribution system using central force optimization and differential evolution,” vol. 7, no. 3.
- A. De Corte and K. Sörensen, “Hydrogen,” available online:
- M. Carnero, J. Hernández, and M. Sánchez, “A new metaheuristic based approach for the design of sensor networks,” Computers Chemical Engineering, vol. 55, pp. 83 – 96, 2013.
- C. Bermúdez, C. Salto, and G. Minetti, “Designing a multiperiod water distribution network with a hybrid simulated annealing,” in XLVIII JAIIO: XX Simposio Argentino de Inteligencia Artificial (ASAI 2019). Universidad Nacional de Salta, 2019, pp. 39–52.
- N. Kohl, “Exact methods for time constrained routing and related scheduling problems,” 1995.
- B. Ombuki, B. Ross, and F. Hanshar, “Multi-objective genetic algorithms for vehicle routing problem with time windows,” Applied Intelligence, vol. 24, pp. 17–30, 02 2006.
- V. F. Yu, H. Susanto, P. Jodiawan, T.-W. Ho, S.-W. Lin, and Y.-T. Huang, “A simulated annealing algorithm for the vehicle routing problem with parcel lockers,” IEEE Access, vol. 10, pp. 20764–20782, 2022.
- J.-F. Cordeau and G. Laporte, Tabu Search Heuristics for the Vehicle Routing Problem. Boston, MA: Springer US, 2005, pp. 145–163. [Online]. Available: https://doi.org/10.1007/0387-23667-86