Optimización de ruta de reparto de material sanitario para los centros de salud de Zaragoza

Sevilla Antón, Iván
Esteban Escaño, Luis Mariano (dir.) ; Asensio Chaves, César (dir.)

Universidad de Zaragoza, ALM, 2023
Departamento de Métodos Estadísticos, Área de Estadística e Investigación Operativa

Graduado en Ingeniería de Organización Industrial

Resumen: Este Trabajo Final de Grado (TFG) plantea y comprende la creación
de una aplicación web que permite optimizar la ruta de reparto de
material sanitario para los centros de salud de Zaragoza, incluyendo
como elemento diferenciador en la generación de rutas los algoritmos
genéticos.
El SALUD (Servicio Aragonés de Salud), es el sistema sanitario
público de la comunidad autónoma de Aragón. Está organizado
territorialmente en ocho áreas o sectores de salud, los cuales a su vez
se subdividen en zonas de salud; que albergan los distintos centros de
salud aragoneses.
Actualmente, en la provincia de Zaragoza, existen un total de
sesenta y cinco centros de salud, los cuales son abastecidos desde la
Plataforma Logística del SALUD, situada en la Plataforma Logística de
Zaragoza (PLAZA).
La aplicación creada resuelve y calcula eficientemente la ruta de
reparto necesaria para abastecer los centros de salud requeridos en
cada momento, desde la Plataforma Logística del SALUD.
En este contexto es inevitable mencionar el Problema del Agente
Viajero o en inglés Travelling Salesman Problem (TSP). Se trata de un
problema de combinatoria con alta dificultad que trata de resolver o
calcular la ruta más corta que, dada una lista de ciudades y partiendo
desde una de ellas, visite todas las restantes una sola vez, volviendo a
la ciudad de partida. En este TFG no se visitan ciudades, sino que se
visitan cada uno de los centros de salud que se necesiten abastecer.
Esta complejidad del TSP lo clasifica como un problema NP-Hard,
es decir, no se puede encontrar la solución óptima en tiempo
polinomial, o computacionalmente razonable. Debido a esta situación
los algoritmos exactos son inaplicables ya que para un número
relativamente “grande” de centros de salud, el tiempo de cálculo se
dispara a millones de años.
Como solución a esta complejidad, se utilizan algoritmos
heurísticos. En este TFG, concretamente, se utiliza el algoritmo del
vecino más cercano, el algoritmo del vecino más lejano y un algoritmo
de tipo genético; los cuales, en un tiempo razonable obtienen
soluciones muy próximas a la óptima. En definitiva, el TSP se resuelve
de una manera muy aproximada, y no exacta; ya que es mejor tener
una solución (ruta), que ninguna.
Mientras que el algoritmo del vecino más cercano y el algoritmo del
vecino más lejano, operan de una manera muy intuitiva, eligiendo en
cada paso local la mejor opción (la ciudad más cercana y la más lejana,
a la última incluida en la ruta, respectivamente), el algoritmo genético
tiene una mayor complejidad, realizando una búsqueda mucho más
profunda y exhaustiva de soluciones óptimas.
El algoritmo genético se basa en la teoría de la evolución de las
especies y la selección natural de Charles Darwin. Al igual que los
individuos mejor adaptados de las especies, tienen más posibilidades de
sobrevivir, reproducirse y generar descendencia, transmitiendo sus
características a la posterior generación; las mejores soluciones de cada
generación calculadas por el algoritmo genético tienen más
posibilidades de perdurar, combinarse y obtener mejores “soluciones
hijas”, que pasen de generación en generación, hasta obtener la mejor
solución posible.
Esta metodología en la búsqueda de soluciones óptimas, tal y como
se podrá observar en los resultados de rutas obtenidas, supone una
mejora en las soluciones generadas respecto al algoritmo del vecino
más cercano y del más lejano.
La aplicación creada en este TFG muestra los resultados de las
rutas obtenidas con los tres algoritmos mencionados, por lo que el
usuario que la esté utilizando, podrá elegir la que más le convenga;
seguramente basándose en el criterio de minimizar la distancia
recorrida por la ruta. Además, se representa en un mapa interactivo la
ruta más corta generada, mostrando el recorrido a seguir, a través de
las calles y carreteras que conectan los centros de salud seleccionados.
Con la finalidad de fomentar el uso de software libre, la aplicación
queda depositada en la nube, en un repositorio shiniapps.io para su uso
libre de cualquier interesado.

Tipo de Trabajo Académico: Trabajo Fin de Grado