Matheuristic for multi-period home healthcare routing and scheduling problem : a real life case study

Abstract

The aging population's exponential growth has exerted considerable pressure on healthcare systems, necessitating the provision of enhanced healthcare services tailored to meet the unique needs of older adults, individuals with disabilities, and chronic patients. As a result, healthcare providers aim to offer varying healthcare services to patients in their homes, with the objective of improving the quality of care and optimizing the management of health systems. This thesis studies a home healthcare routing and scheduling problem (HHCRSP) over a multi-period planning horizon, considering caregivers' lunch breaks, prior service type, and patients' preferences. In this HHCRSP, some patients needing blood draw, and they have to be visited before noon, guaranteeing the corresponding caregiver's return to the hospital's lab before noon. Additionally, patients have preferred time windows for each day, corresponding to times due to reasons such as the need for someone to support them with the patients. In the thesis, the objective function is minimizing the total routing costs of caregivers' vehicles and the penalty costs incurred when patients cannot receive services within their preferred time windows. Our study is motivated by a real-life hospital that provides home healthcare service (HHCS). We develop a mixed-integer linear programming (MILP) model and propose a simulated annealingbased matheuristic algorithm (SAMA) that decomposes the original problem into two phases. Furthermore, we conduct a comparative analysis of the k-nearest-neighbour (KNN) algorithm, utilizing various k values to predict service times. The results of our study demonstrate significant improvements, up to 98.64% in cost-effectiveness achieved by the MILP in small-sized instances, and 98.58% by the SAMA in medium and large-sized instances, compared to the existing system in the motivational hospital. The numerical analysis provides insights for healthcare providers and policymakers in their efforts to optimize HHCS.

Yaşlanan nüfusun hızla büyümesi; yaşlıların, engelli bireylerin ve kronik hastaların ihtiyaçlarını karşılamaya yönelik geliştirilmiş sağlık hizmetlerinin sağlanmasını zorunlu kılarak sağlık sistemlerine önemli bir baskı uygulamıştır. Sonuç olarak, sağlık hizmeti sağlayıcıları, hasta bakımında çeşitli sağlık hizmetleri sunmayı, bakım kalitesini artırmayı ve sağlık sistemlerinin yönetimini optimize etmeyi amaçlamaktadır. Bu tez, sağlık hizmeti sağlayıcılarının öğle aralarını dikkate alan çok dönemli bir planlama sürecindeki evde sağlık hizmeti rotalama ve çizelgeleme problemi üzerinde çalışmaktadır. Bu evde sağlık hizmeti rotalama ve çizelgeleme probleminde, bazı hastalardan kan alınması gerekmektedir ve bu hastalar öğleden önce ziyaret edilmeli ve ilgili hizmet sağlayıcıların öğleden önce hastanedeki laboratuvara dönmesi gerekmektedir. Ayrıca, hastaların zaman pencereleri, onlara hizmet sırasında destek olması için refakatçi ihtiyacı gibi nedenlerle her gün için tercih edilen zaman aralıklarını ifade eder. Tezde, amaç fonksiyonu, hizmet sağlayıcıların araçlarının toplam rotalama maliyetlerini ve hastaların belirlenmiş zaman pencerelerinde hizmet alamadıklarında ortaya çıkan ceza maliyetlerini minimize etmektir. Çalışmamız, evde sağlık hizmeti sunan gerçek bir hastaneden esinlenilmektedir. Problemi çözmek için, karışık tamsayılı lineer programlama modeli geliştirilir ve orijinal problemi iki aşamaya ayıran benzetilmiş tavlama tabanlı matematiksel sezgisel algoritma önerilir. Ayrıca, hizmet sürelerini tahmin etmek için çeşitli k değerlerini kullanan k-en yakın komşu algoritmasının karşılaştırmalı analizi yapılır. Çalışmamızın sonuçları, mevcut sisteme kıyasla, küçük boyutlu örneklerde karışık tamsayılı lineer programlama modeli tarafından %98.64'e ve orta ve büyük boyutlu örneklerde benzetilmiş tavlama tabanlı matematiksel sezgisel algoritma tarafından %98.58'e varan maliyet etkinliğinde önemli iyileştirmeler sağlandığını göstermektedir. Sayısal analizler, sağlık hizmeti sağlayıcıları ve politika yapıcıları için evde sağlık hizmetini optimize etme çabalarında değerli içgörüler sağlar.