Optimization Approaches for a Home Healthcare Routing and Scheduling Problem: A Real Case From Medellin, Colombia

Introduction

Welfare community projects, mainly related to health care, are essential for the development of societies. For this reason, the optimization of its resources through methodologies that support decision making becomes of interest for all stakeholders in order to reach the target users. The population aging and the increase in the care requirements for chronic diseases have overtaken the health institutions capacity, generating a growing trend in home care. In Colombia, particularly in the city of Medellin, several social projects are being developed seeking to provide health services to vulnerable populations. One of these projects seeks to deliver attention to low-income disabled citizens, which are called users in the sequel, and their caregivers through four areas of health: psychology, nutrition, physiotherapy and nursing. This social project aims to give health services from each area to each user and the corresponding caregiver during a given horizon period. In that sense, professionals should visit home users by designing adequate routes to be performed by team each day.

In the field of Operations Research this problem is closely related to the Home Health Care Routing and Scheduling Problem (HHCRSP), which can be described as the problem in which a set of patients, dispersed on a geographical area, need care services, that is, home visits, which must be provided by professionals from a health service institution. The problem aims to define a set of routes to manage the group of patients. The objectives can vary and depend on each context and institution. Among the more common are the maximization of the patients served, as well as their level of satisfaction. On the other hand, operational performance measures can be sought such as cost, travel time or waiting times minimization, among others.

The HHCRSP is considered a variation of vehicle routing problem (VRP), which is a combinatorial optimization problem with multiple applications that has been extensively studied in the literature (Vidal et al. 2013). There is a wide range of applications that has led to proposing variants to the problem that include different characteristics and restrictions, which can be called attributes, seeking to obtain more detail of the system or decision making, which is known as multi-attribute vehicle routing problem (MAVRP) (Vidal et al. 2013). Many HHCRSP applications can be considered as MAVRP. The dimensions of this type of problem is an obstacle to the use of exact methods for the solution, so most of the authors propose heuristic methods.

The purpose of this chapter is to deal with a real application of the HHCRSP based on a social project from Medellin, Colombia. In this application a set of health professionals from different specialties of health should visit a set of users. This project has associated around 1,920 users, three teams of four professionals and a time horizon of five months, which applies around 7,680 visits and each professional must attend on average 5,8 users every day. Each user must be visited once by one professional of each of four specialties. The visits, from the different professionals, to each user are performed in such a way that two consecutive visits are separated by a period of at least four weeks. There are no precedence nor specific order between different areas of health. A vehicle is available for each team of professionals and it must leave them and pick them up to user homes. Professional also can move between user homes by walking as long as the distances does not exceed a maximum. A solution also includes to decide which transportation mode must be used. As the time is limited for the project and professionals time is scarcer, here it is used as objective function the minimization of the traveled time and waiting time by professionals, i.e. the time in which they are not on an appointment. Note that the number of professional can vary for every travel and it is not necessarily optimal to transport only one professional every time.

Here it is proposed a mathematical model and a heuristic solution approach. The mathematical model is based on VRP models with Pick up and Deliveries (VRPPD) and additional features coming from selective and resource constrained problem. Note that, as some travels can be done by walking, vehicles do not need to pick up and deliver professionals for every node. In addition, professionals have the role of resources due to they are available until they start a service and cannot be delivered to other user’s homes until they finish the service in process and they have been picked up. The proposed solution methods contribute in the following decision making within the project: