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

Autor: Martín Gallardo, Emilio
Přispěvatelé: Isasi, Pedro, Sáez Achaerandio, Yago, UC3M. Departamento de Informática, Universidad Carlos III de Madrid. Departamento de Informática
Jazyk: Spanish; Castilian
Rok vydání: 2018
Předmět:
Zdroj: e-Archivo. Repositorio Institucional de la Universidad Carlos III de Madrid
instname
Popis: 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 inspirabasada 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. Palabras clave: Clustering, metaheurísticas, problemas de optimización combinatoria, optimización basada en colonias de hormigas, problemas de planificación de asistentes de atención domiciliaria.do 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. This research addresses the resolution of the family of problems called Home Care Scheduling Problem (HCSP) problems. The importance of solving this family of problems has been increasing in recent years, an importance that has also been reflected in the academic world with a growing number of publications Fikar y Hirsch (2017); Cisse et al. (2017). This interest is motivated mainly by two factors, namely, the ageing of our population and the need to seek more efficient alternatives in the provision of home care services. The progressive ageing of our population is perhaps one of the most important challenges that we will face as a society, a challenge that has been identified both by European and international bodies World Health Organization (2015). In this demographic context, and with the growing demand for home-based care requests, home-based care service providers must look for more efficient and alternative ways to meet the growing demand, while preserving the quality of service and ensuring quality and sustainable home-based care services for our elderly. This research addresses a real and easily transferable problem to the industry, faced by the company EULEN. The company provides home care services in the Community of Madrid and must provide around 1.5 million services per year, which amounts 2.1 million working hours, not including the inefficiencies inherent in the provision of services, such as travel and waiting times incurred by caregivers. The problem is addressed on a weekly basis, with 13344 services to be scheduled to each week. These services in turn consist of tasks, which must be provided at a specific time and at a particular location. Of these services, 80 percent must be provided Monday through Friday in morning shift (07:00 to 14:30) so that about 10,700 services must be planned and assigned at the same time. The size of the problem addressed is one order of magnitude higher than those addressed in the state of the art, along with the impossibility of dividing the problem into smaller instances has required the design and implementation of specific techniques for its resolution. The problem is tackled from the perspective of clustering, consisting of resolving it by grouping services into groups of services or clusters, which will confom the timetable of each assistant. The main difficulty of tackling the problem from the perspective of clustering, in addition to its unusual size, are its restrictions and the concept of similarity or distance between clusters. This concept is defined to take into account the spatial and temporal components of the problem. Once defined, the problem is tackled with three novel techniques: the first is a hierarchical clustering method inspired by the Ward Ward (1963) method, while the other two approaches are based on the metaheuristics Ant Colony Optimization proposed by (Dorigo y Gambardella, 1997) and are called ACS-HCSP and IACS-HCSP. All techniques are evaluated experimentally in a comprehensive manner, with a total of 96 different configurations adapted to different environments. First, the proposed techniques are compared with each other in order to determine their performance, both in terms of quality and execution time, and the relevant analyses of statistical significance are carried out. Once the techniques with the best performance have been determined, a comprehensive comparison of the ACS-HCSP and IACS-HCSP techniques is made to determine whether the proposed modifications to the IACS-HCSP technique produce significant improvements, with a positive result. Finally, and with the aim of comparing the techniques proposed with existing state-of-the-art techniques, the proposed techniques are compared with the heuristic techniques proposed by Quintana et al. (2017) and with the company’s current solution, obtaining the IACS-HCSP technique with better results and allowing an estimated economic yearly saving of 3.7 million euros. Keywords: Clustering, metaherustics, combinatorial optimization problems, ant colony optimization, home care scheduling problems. Programa Oficial de Doctorado en Ciencia y Tecnología Informática Presidente: Inés María Galván León.- Secretario: Francisco Luna Valero.- Vocal: Diego Pérez Liébana
Databáze: OpenAIRE
Externí odkaz: