Combined routing and staff scheduling model for home health care

International audienceThe combined routing and scheduling problem has become a relevant issue in health care logistics as demand for cost effective and quality health services rises. The main challenge of this problem is to combine aspects of routing and staff scheduling. Both composing problems are well known as combinatorial optimization problems and there is an extensive literature of exact and heuristic methods for each of them. Although combined routing and scheduling problems arise in many applications, only few works have been developed in the field of home health care logistics. We consider a set of patients with different geographical locations who require different medical treatments composed by a list of medical procedures. For each patient, the duration, frequency and hours in which the medical treatment must be applied are known. Each medical procedure must be performed by a medical staff who has the adequate qualifications. Medical staff professionals are also located in different geographical points, and each staff member is assigned to work shifts while respecting work legal guidelines. The problem that arises in this system is scheduling the activities of each staff member and sequencing visits to patients such that overall logistic costs are minimized and a high quality service is performed. Desired conditions that must be satisfied in the system include the accomplishment of customer medical treatments in terms of time windows, and precedence and synchronization constraints of medical procedures. In terms of medical staff, work shifts must be respected, geographical location must be considered, assignment of visits must respect required qualifications, and balanced work loads are expected. The overall objective of this work is to propose a formulation of the combined routing and scheduling problem in the context of the home health care services. We propose a mixed integer linear program and demonstrate the high complexity of the resulting problem through computational experiments. Research and improvement opportunities in the field are also detailed