Português English

Tese de Doutorado de Alberto Francisco Kummer Neto

Detalhes do Evento

Aluno: Alberto Francisco Kummer Neto

Orientadora: Profª. Drª. Luciana Salete Buriol
Título: A study on home health care routing and scheduling problem.

Linha de Pesquisa: Algoritmos e Otimização


Data: 20/10/2021
Horário: 11h

Esta banca ocorrerá excepcionalmente de forma totalmente remota. Interessados em assistir a defesa poderão acessar a sala virtual através do link: https://mconf.ufrgs.br/webconf/001555035



Banca Examinadora:

– Prof. Dr. Santiago Valdés Ravelo (UFRGS)

– Profa. Dra. Elena Valentina Gutiérrez (Universidad del Valle – UNIVALLE)

– Profa. Dra. Helena Ramalhinho Dias Lourenço (Universitat Pompeu Fabra – UPF)


Presidente da Banca: Profª. Drª. Luciana Salete Buriol


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 worldwide 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 distinct 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 explores 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 previous 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.


Keywords: Home health care problem. vehicle routing problem. time-window. Route inter-dependency constraints.