Técnicas de clustering aplicadas a la resolución de problemas de optimización combinatoria con restricciones espaciales y temporales

• Autores: Emilio Martin Gallardo
• Directores de la Tesis: Pedro Isasi Viñuela (dir. tes.) , Yago Sáez Achaerandio (codir. tes.)
• Lectura: En la Universidad Carlos III de Madrid ( España ) en 2018
• Idioma: español
• Tribunal Calificador de la Tesis: Inés María Galván León (presid.) , Francisco Luna Valero (secret.) , Diego Pérez (voc.)
• Enlaces
  • Tesis en acceso abierto en: e-Archivo
• Resumen

  • En esta investigación se aborda la resolución de la familia de problemas denominada problemas de planificación de asistentes de atención domiciliaria, conocida por sus siglas en inglés HCSP (Home Care Scheduling Problem). La importancia en la resolución de esta familia de problemas ha ido en aumento durante los últimos años, importancia que también se ha visto reflejada en el mundo académico con un creciente número de publicaciones tal y como reflejan dos recientes revisiones sobre estado del arte Fikar y Hirsch (2017); Cisse et al. (2017). Este interés está motivado principalmente por dos factores, a saber, el envejecimiento de nuestra población y la necesidad de buscar alternativas más eficientes en la prestación de servicios de atención domiciliaria. El envejecimiento progresivo de nuestra población, es quizás uno de los retos más importantes que deberemos afrontar como sociedad, reto que ha sido señalado por diversos organismos tanto europeos como internacionales (World Health Organization, 2015). En dicho contexto demográfico, y con una creciente demanda de peticiones de asistencia domiciliaria, las empresas prestadoras de servicios de atención domiciliaria deben buscar formas más eficientes y alternativas de satisfacer la creciente demanda, preservando la calidad del servicio y garantizando unos servicios de atención domiciliaria de calidad y sostenibles para nuestros mayores. Esta investigación se centra en la resolución de un problema real y de fácil transferencia a la industria, reportado por la compañía EULEN. Dicha compañía presta servicios de atención domiciliaria en la Comunidad de Madrid y debe atender anualmente alrededor de 1.5 millones de servicios, lo que se traduce en 2.1 millones de horas de trabajo, no incluyendo estas cifras las ineficiencias inherentes a la prestación de servicios, como son los desplazamientos y los tiempos de espera incurridos por los asistentes. El problema es abordado semanalmente, debiendo atender a 13.344 servicios cada semana. Estos servicios a su vez están formados por tareas, que deben prestarse a una hora concreta y en una localización particular. De estos servicios, el 80% debe ser atendido de lunes a viernes en horario matinal (07:00 a 14:30) con lo que alrededor de 10.700 servicios deben ser planificados y asignados a la vez. El tamaño del problema abordado, el cual está un orden de magnitud por encima de los abordados en el estado del arte, junto con la imposibilidad de dividir el problema en instancias más pequeñas ha requerido el diseño e implementación de técnicas específicas, a fin de poderlo resolver en un tiempo y con un coste que posibilite la operativa diaria de la compañía prestadora de servicio. El problema se aborda desde la perspectiva del clustering, consistiendo su resolución en la agrupación de servicios dentro de grupos de servicios o clústers, los cuales conformarán el horario de trabajo de cada asistente de atención domiciliaria. La utilización de dicha perspectiva presenta varios desafíos que han sido resueltos a lo largo de la presente investigación, entre ellas destacan: el inusual tamaño de las instancias a resolver, las restricciones a respetar que contemplan aspectos espaciales y temporales, así como la necesidad de definir un concepto de similitud o distancia entre. Dicho concepto de similitud es definido a fin de tener en cuenta las componentes espaciales y temporales del problema. Una vez definido, el problema se aborda con tres técnicas novedosas: la primera de ellas es un método de clustering jerárquico inspirado en el método de Ward (1963), mientras que las dos aproximaciones restantes se basan en la metaheurística conocida como optimización basada en colonias de hormigas Dorigo y Gambardella (1997) y se denominan ACS-HCSP y IACS-HCSP. Todas las técnicas son evaluadas experimentalmente de un modo exhaustivo, con un total de 96 configuraciones distintas adaptadas a diferentes entornos. En primer lugar, se comparan las técnicas propuestas entre sí a fin de determinar su rendimiento, tanto como en calidad como en tiempo de ejecución, realizándose los pertinentes análisis de significación estadística. Una vez determinada las técnicas que tienen un mejor rendimiento se pasa a comparar de modo exhaustivo las técnicas ACS-HCSP y IACS-HCSP a fin de determinar si las modificaciones propuestas para la técnica IACS-HCSP producen mejoras significativas, obteniéndose un resultado positivo. Finalmente y con el objetivo de comparar las técnicas propuestas con técnicas existentes en el estado del arte, las técnicas propuestas son comparadas con las heurísticas propuestas por Quintana et al. (2017) y con la solución actual de la compañía, obteniendo la técnica IACS-HCSP mejores resultados y permitiendo un ahorro económico estimado de 3.7 millones de euros anuales.