Publication: Técnicas de clustering aplicadas a la resolución de problemas de optimización combinatoria con restricciones espaciales y temporales
Loading...
Identifiers
Publication date
2018-09
Defense date
2018-12-18
Authors
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
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.
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.
Description
Keywords
Home Care Scheduling Problem (HCSP), Clustering, Ant colony optimization, Planificación heurística, Análisis cluster, Optimización basada en colonias de hormigas, Optimización combinatoria, Asistencia domiciliaria