Clustering technique for large-scale home care crew scheduling problems

Abstract

The Home Health Care Scheduling Problem involves allocating professional caregivers to patients' places of residence to meet service demands. These services are regular in nature and must be provided at specific times during the week. In this paper, we present a heuristic with two tie-breaking mechanisms suitable for large-scale versions of the problem. The greedy algorithm merges service lots to minimize the accumulated unproductive time. As a result, the solution is restructured in such a way as to increase its efficiency. The approach is tested on a real-world large instance of the problem for a company whose current resource allocation is inefficient. The solutions are benchmarked against the current service assignment and those obtained by a Ward clustering algorithm, and the results show an improvement in efficiency and cost.