An application of constraint solving for home health care

Issue title: 19th RCRA International Workshop on “Experimental evaluation of algorithms for solving problems with combinatorial explosion”

Article type: Research Article

Authors: Cattafi, Massimiliano | Herrero, Rosa | Gavanelli, Marco^; | Nonato, Maddalena | Malucelli, Federico

Affiliations: Department of Electrical and Electronic Engineering, Imperial College London, London, UK. E-mail: m.cattafi@imperial.ac.uk | Department de Telecomunicació i Enginyeria de Sistemes, Universitat Autònoma de Barcelona, Cerdanyola del Vallès, Spain. E-mail: RHerrero.Math@gmail.com | EnDIF, Università di Ferrara, Ferrara, Italy. E-mails: marco.gavanelli@unife.it, maddalena.nonato@unife.it | Dipartimento di Elettronica e Informazione, Politecnico di Milano, Milano, Italy. E-mail: malucell@elet.polimi.it

Note: [] Corresponding author: Marco Gavanelli, EnDIF (Engineering Department in Ferrara), Università di Ferrara, Via G. Saragat, 1, 44122 Ferrara, Italy. Tel.: +39 0532 974833; Fax: +39 0532 974833; E-mail: marco.gavanelli@unife.it

Abstract: Although sometimes it is necessary, no one likes to stay in a hospital, and patients who need to stay in bed but do not require constant medical surveillance prefer their own bed at home. At the same time, a patient in a hospital has a high cost for the community, that is not acceptable if the patient needs service only a few minutes a day. For these reasons, the current trend in Europe and North-America is to send nurses to visit patients at their home: this choice reduces costs for the community and gives better quality of life to patients. The challenge is to deliver the service in a cost effective manner without a detriment of the service quality. These social and health management issues have interesting implications from the mathematical viewpoint, introducing a challenging combinatorial optimization problem. The problem consists in assigning patients' services to traveling nurses and defining the nurse itineraries so that the following optimization aspects are considered: the nurse workloads (including service as well as travel time) are balanced, patients are preferentially served by a single nurse or just a few ones, and the overall travel time is minimized. These objectives are somehow conflicting and a reasonable trade off must be found. The complexity of the problem calls for suitable optimization-based algorithmic support to decisions, in particular in the perspective of an increasing diffusion of the service. This problem is known in the literature as the Home Health Care (HHC) problem. In this paper, we address the HHC problem in the municipality of Ferrara, a mid-sized city in the North of Italy. The problem is currently solved by hand, starting from a partitioning of patients based on predefined zones. We describe a Constraint Programming model that solves the HHC problem, and show significant improvements with respect to the current manual solution.

Keywords: Constraint programming, nurse scheduling applications, home health care, large neighbourhood search, routing problems, Lagrangian relaxation

DOI: 10.3233/AIC-140632

Journal: AI Communications, vol. 28, no. 2, pp. 215-237, 2015