XXIV Workshop de Investigadores en Ciencias de la Computación (WICC 2022) - Universidad Champagnat (Mendoza)
Libro de actas (ver página 79)
Optimización de la
logística de distribución utilizando técnicas de la Inteligencia Artificial
Gabriela
Minetti, Carolina Salto, Hugo Alfonso, Carlos Bermúdez,
M.Juliana
Dielschneider Del Bono, Javier Vargas
Laboratorio
de Investigación en Sistemas Inteligentes (LISI)
Facultad de
Ingeniería - Universidad Nacional de La Pampa
Calle 110 Esq. 9 (6360)
General Pico - La Pampa - Rep. Argentina
Te. / Fax: (02302)
422780/422372, Int. 6302
e-mail: {saltoc,
minettig, alfonsoh, bermudezc, juliana, jvargas}@ing.unlpam.edu.ar
Resumen
La
logística en Argentina está influida por el decisivo peso de la producción
primaria en la organización del sistema, por una orientación prevalente hacia
las exportaciones globales y las dirigidas al mercado regional sudamericano, y
por una matriz de transporte dominada por el transporte automotor de cargas y
la concentración portuaria. 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 no movimiento 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. Esta aproximación
resalta las limitaciones de miradas parciales y destaca la necesidad de
considerar una perspectiva integral que incluya, además, los aspectos
organizacionales y de coordinación. La consideración de infraestructuras de
circulación; servicios de transporte; infraestructuras de comunicaciones;
servicios de almacenamiento y agregado de valor; normativas y regulaciones y
costos operativos, entre otros, da cuenta del desafío que involucra una
coordinación amplia de políticas estatales de diferente tipo y a cargo de
estructuras administrativas diversas. El despliegue de la logística como uno de
los “usos del territorio”, abre la posibilidad de acentuar el enfoque
territorial. En esta línea de investigación se aborda la optimización de la
logística de distribución de cargas y paquetería. Para tal fin 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. Se considera que el
abordaje de la optimización de la logística de distribución centrada en la
provincia de La Pampa tendría impacto en la matriz productiva y de servicios de
toda la región.
Palabras
claves: Optimización, Logística de distribución, Inteligencia Artificial
Contexto
Esta
línea de investigación surge como una proyección del Proyecto "Big data
optimization con algoritmos metaheurísticos utilizando frameworks de
computación distribuida" que se desarrolla desde el 2021 en la Facultad de
Ingeniería de la UNLPam. Este proyecto se lleva adelante en el Laboratorio de
Investigación de Sistemas Inteligentes (LISI) de la Facultad de Ingeniería y es
dirigido por la Dra. Salto.
En
el LISI, desde su creación en 1998, nos hemos 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. En este dominio, el objetivo consiste en obtener
algoritmos nuevos que den solución al problema y que necesiten un esfuerzo
computacional más pequeño que los algoritmos existentes, así como caracterizar
su comportamiento para las clases de problemas que demanda la comunidad
científica e industrial en general. Cabe destacar que desde hace varios años,
los integrantes de este laboratorio mantienen una importante vinculación con
investigadores de las universidades argentinas, Universidad Nacional de San
Luis y Universidad Nacional de Rio Cuarto, y de la Universidad de Málaga
(España), con quienes se realizan trabajos conjuntos.
Introducción
La
optimización de la logística de distribución de cargas y paquetería, conocida
en el ámbito de la investigación operativa [1] como el problema del
enrutamiento de vehículos (VRP, sus siglas en Inglés) [2], es posiblemente uno
de los problemas de optimización combinatoria más clásicos que surgen en la
cadena logística. El VRP 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 peso o tamaño) de
las cantidades recolectadas por un solo vehículo no puede exceder su capacidad.
En la versión más clásica del 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, el tiempo de viaje, las horas
hombre, los viáticos, el combustible y los peajes [3], [4]. Desafortunadamente,
el VRP es fuertemente NPduro incluso para un solo objetivo, ya que el problema
del viajante de comercio (TSP) [5] puede reducirse polinomialmente a él [6].
Los avances en la tecnología de la comunicación y de la información permiten
que las flotas de vehículos sean manejadas en tiempo real. Esto implica usar
conjuntamente sistemas de información geográfica, sistemas de posicionamiento
global, sensores de flujo de tráfico y teléfonos celulares para obtener datos
en tiempo real. Por ejemplo, la ubicación actual de los vehículos,
requerimientos de los nuevos consumidores, el tiempo de viaje en ruta, entre
otros. En este contexto, al introducir diversas características dinámicas el
VRP clásico se convierte en dinámico (DVRP, por sus siglas en Inglés) [7], [8],
representando una parte importante de muchos sistemas de distribución y
transporte actuales. El dinamismo puede darse en el bloqueo de la ruta entre
dos clientes, en órdenes modificadas por los consumidores, incremento en el
tiempo de viaje debido a las malas condiciones climáticas, etc. A estas dos
versiones de VRP se suman los requerimientos de nuevos servicios como una mayor
atención pública sostenible [9], las restricciones de acceso urbano [10], [11],
el aumento de los volúmenes de entrega [12], el uso de instalaciones de
transbordo que surgen en la logística de la ciudad [13], la integración de
producción, inventario, distribución y enrutamiento de múltiples viajes con
ventanas de tiempo [14], la utilización de una flota heterogénea con backhaul
(viaje de vuelta) [15], entre otros. Al ser todos estos servicios variantes de
VRP pertenecen a la clase de problemas NPduro. El VRP ha sido objeto de
intensos esfuerzos de investigación en el área de la Inteligencia Artificial,
considerando enfoques de optimización tanto exactos como heurísticos. Los
primeros estudios de solución para el VRP, centrados en técnicas exactas, se
pueden encontrar en [16], [17], [18], [19], entre otros. Debido al alto nivel
de complejidad de este problema y su amplia aplicabilidad a situaciones de la vida
real, 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 [20], son de
primordial importancia, como lo muestran estas contribuciones: [13], [21],
[22], [23], [24], entre muchos otras. 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 aun cuando se ejecutan
secuencialmente. Pero la paralelización de este proceso, además de disminuir
los tiempos, permite aumentar la calidad de las soluciones halladas. En este
sentido, resulta necesario el análisis de las distintas plataformas de hardware
(procesadores multicores, unidades de procesamiento gráficas, ambientes cloud)
y de software (Hadoop, Spark, MPI, High Processing Computing -HPC- en general)
actuales que permiten desarrollar técnicas de computación paralelas que mejoran
la resolución de problemas con menores tiempos de cómputo. Además de, medir
objetivamente el algoritmo en términos de calidad de la solución y tiempo
computacional sobre los problemas de los que no se conoce una solución óptima.
El desarrollo de estas técnicas, por ser estocásticas, presenta un tercer
desafío igual de importante: el uso de métodos y de técnicas estadísticas para
valorar la robustez del algoritmo en un amplio rango de casos. Esto conlleva a
una mayor usabilidad de esta clase de algoritmos al incorporarlos como módulos
de optimización dentro de los sistemas de soporte de decisiones gerenciales
[25]. Desde el LISI hemos abordado algunas variantes de este problema [26] así
como también del conocido problema del viajante de comercio [27]. Además, hemos
resuelto una gran variedad de problemas combinatorios NP-duros con herramientas
inteligentes, a saber: diseño de redes de distribución de agua [28], [29],
diseño de redes de sensores [30], [31], [32], de planificación de trabajos
[33], [34], de ensamblado de fragmentos de ADN [35], [36], corte y empaquetado
[37], entre otros. Así como también, la paralelización de estas herramientas en
ambientes HPC [38], [29]. La experiencia que hemos alcanzado en la resolución
de esta variedad de problemas, nos permitiría aplicar y adaptar estas técnicas
en la resolución del problema de optimización de la logística de distribución
de cargas y paquetería en la Provincia de La Pampa y su región aledaña. Se
trabajará con datos de prueba brindados por la comunidad científica
(benchmarks) que nos permitirá contrastar y evaluar nuestra propuesta con
algoritmos de la literatura, con el objetivo de medir el desempeño de los
algoritmos desarrollados. A partir de esto, podremos utilizar nuestra propuesta
algorítmica para optimizar escenarios de distribución reales, incorporando el
análisis del impacto de los costos fijos (aquellos que son constantes durante
el volumen “normal” de operación del transportista) y variables (aquellos que
varían con los servicios o el volumen) propios de nuestra provincia y región
aledaña.
Línea
de investigación y desarrollo
Para abordar este puntual problema de optimización
de la logística de distribución de cargas y paquetería, se propuso 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. Luego de la identificación
y enunciado del VRP y sus variantes, se procede con la formulación de las
hipótesis que guiará nuestro trabajo de investigación: H1- La herramienta de
software, basada en las técnicas estocásticas de la inteligencia artificial, es
capaz de diseñar rutas de distribución eficientes para incrementar la
eficiencia operacional, reducir costos y aumentar la satisfacción de los
clientes. H2- La determinación de los factores de costos relacionados a cada
ruta planificada, su clasificación en cuanto a variabilidad y la asignación de
un valor, permiten 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. Con el fin de demostrar las hipótesis, el objetivo general de este
proyecto es brindar herramientas de software sólidas para la toma de
decisiones, que permitan optimizar la logística de distribución de carga y
paquetería que minimicen costos e incrementen la eficiencia operacional, no
solo en relación al tiempo, sino también en cuanto a los costos en que se
incurrirán necesariamente. De esta manera se proporcionan soluciones de alta calidad
al problema VRP y sus variantes presentes en nuestra región. Este problema
tiene varias aristas a considerar tales como capacidad de carga de los
vehículos, una flota heterogénea, rutas abiertas, zonas geográficas de
distribución, prioridades de entrega, ventanas de tiempo para contactar a
clientes, backhaul, entre otras. También se contempla que dichas situaciones se
puedan producir o variar dinámicamente. En función de la alta complejidad de
los VRPs es que no se pueden encontrar soluciones exactas en tiempos
razonables. Dado lo anterior, los problemas de este tipo se resuelven
utilizando técnicas provenientes de la inteligencia artificial como lo son las
metaheurísticas, que buscan encontrar la mejor solución posible en un tiempo
acotado. Por lo tanto, el software logístico a desarrollar en este proyecto
para la toma de decisiones seguirá tales lineamientos. Para alcanzar el
objetivo general propuesto se establecen los siguientes objetivos específicos:
1- Relevar las características que presenta el VRP en entornos reales de
nuestra región. 2- Modelar el problema y formularlo matemáticamente,
identificando variables, objetivos y restricciones. 3- Seleccionar el método
metaheurístico más adecuado en base al cual se desarrollará el sistema de
logística de distribución inteligente. 4- Diseñar e implementar el software
logístico que optimizará la logística de distribución. 5- Estudiar el costo de
cada ruta de distribución obtenida por el software para verificar su viabilidad
en situaciones reales y facilitar la toma de decisiones en forma proactiva. 6-
Analizar posibles extensiones distribuidas y/o paralelas de esta herramienta
para reducir su tiempo de respuesta.
Resultados
esperados
El resultado final de este proyecto es diseñar 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. Por ello el impacto potencial de esta propuesta cubrirá distintas aristas. Por un lado permitirá la formación específica de un grupo de profesionales y de estudiantes avanzados de las carreras en el abordaje de este complejo problema tan importante para la región. Por otro lado, se desarrollarán aplicaciones apropiadas para potenciales centros de logística y distribución a instalarse en la provincia. La Facultad de Ingeniería se beneficiará, pues este aprendizaje favorece la formación de los recursos humanos en una actividad de transferencia de los resultados de la investigación desarrollada para una futura aplicación del software logístico en una empresa de la región. También es importante resaltar la interdisciplinariedad en el tratamiento de la propuesta ya que permite vincular áreas ingenieriles: Sistemas Inteligentes, Sistemas Distribuidos, Bases de Datos, Ingeniería de Software, Costos Industriales e Investigación Operativa, que provienen de la Ingeniería en Sistemas y de la Ingeniería Industrial.
Formación
de recursos humanos
La
realización de este proyecto brindaría el marco adecuado para continuar con la
formación de los integrantes del mismo y propiciar un ambiente para la
cooperación entre ellos y empresas de la región interesadas en el abordaje de
la problemática abordada. Se contempla la incorporación de dos alumnos
avanzados de las carreras de Ing. en Sistemas y de Ing. Industrial para que se
inicien en la tarea de investigación y sea esta un área propicia para
desarrollar sus trabajos de tesis, o bien recientes graduados de las
mencionadas carreras que se deseen incorporar a la actividad académica o de
investigación. Las tareas a asignar consistirán en: 1 - el desarrollo de una
aplicación para interactuar con el software logístico, 2 - la implementación de
un entorno gráfico para visualizar las rutas obtenidas en la optimización del
problema, 3 - el relevamiento de datos actualizados correspondientes a los
costos fijos y variables determinados, y 4 - la verificación de las rutas de
distribución obtenidas por la metaheurística con los datos relevados.
REFERENCES
[1]
F. S. Hillier and
G. J. Lieberman, Introducción a la
investigación de operaciones, 9th ed. McGRAWHILL/INTERAMERICANA EDITORES,
2012.
[2]
G. B. Dantzig and J. H. Ramser, “The truck dispatching
problem,” Management Science, vol. 6,
no. 1, pp. 80–91,
1959. [Online]. Available:
https://doi.org/10.1287/mnsc.6.1.80
[3]
S. Chopra and P.
Meindl, Administracion de la Cadena de
Suministro: Estrategia Planeacion y Operacion, 5th ed. Pearson, 2013.
[4]
R. Ballou, LOGÍSTICA. Administración de la cadena de
suministros, 5th ed. Pearson, 2004.
[5]
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
[6]
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
[7]
H. Psaraftis, Dynamic
Vehicle Routing Problems. NorthHolland, 1988, pp. 223–248.
[8]
O. Madsen, A. Larsen, and M. Solomon, Recent developments in dynamic vehicle
routing systems, 1st ed. Springer, 2008,
vol. 43, pp. 199–220.
[9]
M. Savelsbergh and T. Van Woensel, “50th anniversary
invited article—city logistics: Challenges and opportunities,” Transportation Science, vol. 50, no. 2,
pp. 579–590, 2016. [Online]. Available:
https://doi.org/10.1287/trsc.2016.0675
[10] S. Ville, J.
Gonzalez-Feliu, and L. Dablanc, “The limits of public policy intervention in
urban logistics: Lessons from vicenza (italy),” European Planning Studies, vol. 21, no. 10, pp. 1528–1541, 2013. [Online]. Available:
https://doi.org/10.1080/09654313.2012.722954
[11]
R. Elbert and C. Friedrich, “Simulation-based
evaluation of urban consolidation centers considering urban access
regulations,” in 2018 Winter Simulation
Conference (WSC), 2018, pp. 2827–2838.
[12]
Comisión-Europea, “Directorate general for mobility
and transport,” 2019. [Online].
Available: https://www.amt-autoridade.pt/media/1934/2019transport-in-the-eu-current-trends-and-issues.pdf
[13]
C. Friedrich and R. Elbert, “Adaptive large
neighborhood search for vehicle routing problems with transshipment facilities
arising in city logistics,” Computers
Operations Research, vol. 137, p. 105491, 2022.
[14]
B. Ramos, C. Alves, and J. Valério de Carvalho, “An
arc flow formulation to the multitrip production, inventory, distribution, and
routing problem with time windows,” International Transactions in Operational
Research, vol. 29, no. 1, pp. 526–553, 2022. [Online]. Available:https://onlinelibrary.wiley.com/doi/abs/10.1111/itor.12765
[15]
W. Wu, Y. Tian, and T. Jin, “A label based ant colony
algorithm for heterogeneous vehicle routing with mixed backhaul,” Applied Soft Computing, vol. 47, pp.
224–234, 2016.
[16] B. L. Golden and
A. A. Assad, “Perspectives on vehicle routing: Exciting new developments,” Operations Research, vol. 34, no. 5, pp.
803–810, 1986. [Online]. Available:
http://www.jstor.org/stable/170738
[17]
——, Vehicle
Routing: Methods and Studies, Amsterdam: North - Holland, 1988.
[18]
M. Desrochers, J. Lenstra, M. Savelsbergh, and F.
Soumis, “Vehicle routing with time windows: Optimization and approximation,” Vehicle Routing: Methods and Studies,
vol. 16, 01 1988.
[19] M. M. SOLOMON and
J. DESROSIERS, “Time window constrained routing and scheduling problems,” Transportation Science, vol. 22, no. 1,
pp. 1–13, 1988. [Online]. Available:
http://www.jstor.org/stable/25768291
[20] E. Talbi, Metaheuristics: from Design to
Implementation. Wiley, 2009.
[21]
E. Demir, T. Bektas¸, and G. Laporte, “An adaptive
large neighborhood search heuristic for the pollution-routing problem,” European Journal of Operational Research,
vol. 223, no. 2, pp. 346–359, 2012.
[22]
G. Dueck, “New optimization heuristics: The great
deluge algorithm and the record-to-record travel,” Journal of Computational Physics, vol. 104, no. 1, pp. 86–92, 1993.
[23]
G. Dueck and T. Scheuer, “Threshold accepting: A
general purpose optimization algorithm appearing superior to simulated
annealing,” Journal of Computational
Physics, vol. 90, no. 1, pp. 161–175, 1990.
[24]
D. Dumez, F. Lehuédé, and O. Péton, “A large neighborhood
search approach to the vehicle routing problem with delivery options,” Transportation Research Part B:
Methodological, vol. 144, pp. 103–132, 2021.
[25] E. Alba, C. Blum,
P. Asasi, C. Leon, and J. Gomez, Eds., Optimization
Techniques for Solving Complex Problems. Wiley, 2009.
[26] C. Bermudez, P.
Graglia, N. Stark, C. Salto, and H. Alfonso, “Comparison of recombination
operators in panmictic and cellular gas to solve a vehicle routing problem,” Inteligencia Artificial. Revista
Iberoamericana de Inteligencia Artificial,
2010.
[27] G. F. Minetti, G.
Luque, and E. Alba, “The problem aware local search algorithm: an efficient
technique for permutation-based problems,” Soft
Comput., vol. 21, no. 18, pp. 5193–5206, 2017. [Online]. Available:
https://doi.org/10.1007/s00500-017-2515-9
[28]
C. Bermúdez, C. Salto, and G. Minetti, Communications in Computer and Information
Science, 2019, ch. Solving the Multi-Period Water Distribution Network
Design Problem with a Hybrid Simulated Anealling, pp. 3–16.
[29]
C. Bermudez, H. Alfonso, G. Minetti, and C. Salto, “A
parallel optimization solver for the multi-period wdnd problem,” Springer, Cham, vol. 12886, Sep. 2021.
[30]
J. Hernandez, C. Salto, G. Minetti, M. Carnero, and M.
C. Sanchez, “Hybrid simulated annealing for optimal cost instrumentation in
chemical plants,” Chemical Engineering
Transactions, vol. 74, pp. 709–714, May 2019.
[31]
G. Minetti, J. Hernandez, M. Carnero, C. Salto, C.
Bermúdez, and M. Sánchez, “Tuning a hybrid sa based algorithm applied to
optimal sensor network design,” Journal
of Computer Science and Technology, vol. 20, p. e03, 05 2020.
[32]
J. Hernandez, C. Salto, G. Minetti, M. Carnero, and M.
Sánchez, “Reliability estimation for sensor networks in chemical plants using
monte carlo methods,” Computer Aided
Chemical Engineering, vol. 48, pp. 439–444, 01 2020.
[33]
C. Salto, F. Morero, and C. Bermúdez, “Parallelism and
hybridization in differential evolution to solve the flexible job shop
scheduling problem,” Journal of Computer
Science and Technology, vol. 20, p. e04, 05 2020.
[34]
G. Minetti, G. Luque, and E. Alba, “The problem aware
local search algorithm: an efficient technique for permutation-based problems,”
Soft Computing, vol. 21, 09 2017.
[35] G. Minetti, E.
Alba, and G. Luque, “Seeding strategies and recombination operators for solving
the dna fragment assembly problem,” Inf. Process. Lett., vol. 108, no. 3, pp. 94–100, 2008.
[36]
G. Minetti and E. Alba, “Metaheuristic assemblers of
dna strands: Noiseless and noisy cases,” 07 2010, pp. 1–8.
[37] C. Salto, M. G. Leguizamón, and E. Alba, “Parallel aco
algorithms for 2d strip packing,” 2010.
[38]
C. Salto, G. Minetti, E. Alba, and G. Luque, Developing Genetic Algorithms Using
Different MapReduce Frameworks: MPI vs. Hadoop: 18th Conference of the Spanish
Association for Artificial Intelligence, CAEPIA 2018, Granada, Spain, October
23–26, 2018, Proceedings, 01 2018, pp. 262–272.