Developing a framework for home healthcare routing and scheduling system and a heuristic solution approach

Abstract

Bu tez çalışmasının amacı, Evde Bakım Rotalama ve Çizelgeleme Problemi için bir çerçeve oluşturmaktır. Bu problem, literatürde NP-zor kombinatoryal optimizasyon problemleri olarak bilinen Zaman Pencereli Araç Rotalama ve Hemşire Çizelgeleme Problemlerinin birtakım özelliklerini içerir. Evde Bakım Rotalama ve Çizelgeleme Problemi için bir çerçeve geliştirilirken, önerilen modelde hemşirelerin, hastaların ve aynı zamanda sağlık kuruluşlarının talepleri/ özellikleri dikkate alınmıştır. Bu sebeple, problemin çözümü için iki aşamalı çözüm yaklaşımı önerilmiştir. İki aşamalı çözüm yaklaşımının ilk bölümü için kümele-atama algoritması geliştirilmiştir. Bu aşama, çalışanların ve hizmet alanların koordinatlarını ve hizmet almak istedikleri zaman pencerelerini göz önüne alarak kümeler oluşturmaktadır. İkinci aşamada oluşturulan kümeler kullanılarak sezgisel algoritma ile çizelgeler ve rotalar oluşturulur. Bu aşamada ilk önce çözüm kurucu algoritmalardan herhangi biri ile çözümü oluşturur ve sonrasında Değişken Komşu Arama ve Değişken Komşu İniş sezgiselleri üretilen çözümleri iyileştirmek için kullanılır. İyileştirme sezgiseli sahip olduğu komşuluk yapısıyla yerel aramada farklı bölgelerin taranmasına imkân sağlamaktadır. Ayrıca gerçek ve büyük ölçekli veri setinde yaklaşım test edilmiştir. Elde edilen sonuçlar göz önüne alındığında, önerilen yaklaşım insan kaynağı etkinliğini artırmış ve toplam çalışma saatini azaltmıştır.

The purpose of this dissertation is to introduce a framework for a Home Healthcare Routing and Scheduling Problem (HHCRSP). This problem comprises the aspects of the Vehicle Routing Problem with Time Windows (VRPTW) and Nurse Rostering Problem (NRP), both of which are two well-known hard combinatorial optimization problems. While developing a framework for the HHCRSP, the considerations/ features of nurses, clients, and also healthcare institutions are taken into account within the developed mathematical models. Therefore, a two-stage solution approach is developed to tackle with the HHCRSP. In the first part of the two-stage solution approach, a cluster-assign algorithm is employed based on the home location and time to obtain feasible clusters. In the second stage, using these clusters, a heuristic starts to create schedules and routes considering the side constraints of the mathematical model. In this stage, three different construction algorithms are employed to generate solutions and then Variable Neighbourhood Search (VNS) and Variable Neighbourhood Descent (VND) heuristics are used to improve these generated solutions. By means of the novelty of this two-stage solution approach has higher diversification ability is achieved by a series of newly developed cross movement strategies. The two-stage solution approach is tested on a set of real large-scale data. The computational results show that our solution approach provides certain advantages, such as an increase in the efficiency of human resources, and a decrease in the working time of nurses.