A study on the home care routing and scheduling problem

Abstract

This thesis approaches the home health care problem, focusing on the routing problems surrounding such systems. These problems are especially important due to the world wide tendency of increased life expectancy and, consequently, global aging. In Brazil, such a system is key regarding the government’s objective of implementing the so-called de-hospitalization. Home health care services positively impacts the patients’ mental well-being and comfort and helps prevent contamination by common pathogens of hospital environments. Such a characteristic is also very desirable in scenarios like the current COVID-19 pandemic. The problem we study consists of developing routes for every caregiver in the problem while scheduling the patients’ visits by such caregivers. Such routes must be crafted while observing the working regulations, minimizing costs, and maximizing the service levels and satisfaction of both caregivers and patients. Some additional constraints are set for patients requiring multiple visits by caregivers with dis tinct qualifications. We propose three techniques to solve the problem, and we study several strategies for obtaining stronger lower bounds for such a routing problem. The first solution method consists of a fix-and-optimize matheuristic that employs a mixed integer programming solver to iteratively optimize routes of pairs of caregivers. Due to problems to scale the matheuristic in larger instances, we also propose two meta-heuristic algorithms. The first meta-heuristic consists of a biased random-key genetic algorithm, which allows us to indirectly explore the problem’s solution space. The third technique–our second meta-heuristic proposal–extends our genetic algorithm with additional components to improve algorithms’ intensification and diversification capabilities. To obtain strong lower bounds, we propose several scenarios for employing a MIP solver, and we describe a technique based on combinatorial lower bounds of the problem. Results for a literature dataset indicate that the proposed techniques are effective and efficient compared to pre vious methods. We also propose a methodology for generating new realistic instances for a home health care system. We introduce a new dataset, and we provide both lower and upper bounds for these new instances. We also report computational results for our best-performing meta-heuristic in these test cases.

Esta tese aborda o problema de atendimento de saúde domiciliar, e foca nos problemas de roteamento ao redor destes sistemas. Esses problemas são especialmente importantes por conta da tendência mundial do aumento da expectativa de vida humana, e consequente mente, o envelhecimento global. Para o governo do Brasil, esse tipo de sistema é muito importante, contribuíndo com a implementação de políticas de desospitalização. Serviços de atendimento domiciliar impactam positivamente no bem estar mental e conforto dos pacientes, e ajudam a prevenir contaminação por patógenos comuns a ambientes hospita lares assim como na atual pandemia de COVID-19. O problema que estudamos consiste no desenvolvimento de rotas para cada médico do problema, e simultaneamente definir o agendamento das visitas. Essas rotas devem ser construídas com observância às regras trabalhistas vigentes, minimizando custos e maximizando o nível dos serviços e satisfação de ambos médicos e pacientes. Algumas restrições adicionais são impostas quando um paciente requer múltiplas visitas por médicos de especialidades distintas. Propuseram-se três técnicas de resolução do problema, e estudaram-se diversas estratégias para obtenção de limites inferiores fortes para tal problema de roteamento. O primeiro método consiste em uma matheurística fix-and-optimize que usa um resolvedor de programação inteira para otimizar iterativamente, rotas de pares de médicos. Por conta de dificuldades de escalabilidade, também propuseram-se duas meta-heurísticas. A primeira meta-heurística consiste em um algoritmo genético com chaves aleatórias viciadas, que permite explorar indiretamente o espaço de soluções do problema. A terceira técnica de resolução estende o algoritmo genético através de componentes adicionais de intensificação e diversificação. Para obter limitantes inferiores fortes, propuseram-se diversos cenários de aplicação de um resolvedor MIP, e descreveu-se uma técnica de limitantes inferiores combinatórios. Resultados experimentais para instâncias da literatura indicam que as técnicas propostas são efetivas e eficientes quando comparadas com métodos anteriores. Também propôs-se uma metodologia para geração de novas instâncias, e propuseram-se limitantes inferiores e superiores para estas. Também reportaram-se seus resultados computacionais frente ao método de solução mais eficiente proposto.