A home hospitalization assignment and routing problem with multiple time windows, mandatory returns and perishable biological samples : A Chilean case study

Abstract

The increase in life expectancy and formal care has fostered the demand for home care services, including home hospitalization. For this service, decision-makers must allocate the staff and route the visits as efficiently as possible. To tackle this problem, in this paper, we devise a new mixed-integer programming formulation that incorporates several industry-specific features, including matching patients to medical specialties and synchronized visits of multiple specialists. Moreover, the proposed formulation also includes three features that have not been tackled simultaneously in the previous literature: multiple time windows, mandatory lunch breaks at the hospital, and fast delivery of perishable biological samples. The proposed model can be reduced to a vehicle routing problem with multiple times windows, known as NP-hard. Therefore, for solving large instances, we design a heuristic procedure composed of a constructive heuristic coupled with an improvement heuristic, which builds on a local branching scheme. To test the applicability of our approach, we conduct a case study focusing on the actual operations of Hospital Padre Hurtado of Santiago, Chile. Our computational experiments show that the model provides fully implementable solutions. Moreover, the heuristic procedure provides high-quality routes (regarding quality and solution times), making it a promising alternative to experience-based scheduling methods and state-of-the-art solvers.