[1]keywords: #1

CEDoc SIDD
Research Laboratory : SI2M

Doctoral thesis
Presented to obtain the degree of doctor
in Applied Mathematics

Presented by:

Mohammed Bazirha

Mathematical models and heuristics
for the home health care routing
and scheduling problem

Supervised by:

Pr. | Abdeslam Kadrani
---|---
Pr. | Rachid Benmansour

Defended on December 29, 2022 at INSEA-Rabat

Jury:

Pr. Adil | Kabbaj | PES at INSEA-Rabat | President
---|---|---|---
Pr. Abdeslam | Kadrani | PES at INSEA-Rabat | Thesis Supervisor
Pr. Rachid | Benmansour | PH at INSEA-Rabat | Thesis Co-Supervisor
Pr. Rachid | Ellaia | PES at EMI-Rabat | Reviewer
Pr. Souad | El Bernoussi | PES at Faculty of Sciences Rabat | Reviewer
Pr. Youssef | Benadada | PES at ENSIAS-Rabat | Reviewer

###### Abstract

This thesis addressed the Home Health Care Routing and Scheduling Problem
(HHCRSP), which is a class of workforce scheduling problems. The HHCRSP is an
extension of the Vehicle Routing Problem with Time Windows  (VRPTW) to which
the constraints related to the Home Health Care (HHC) context are added. It
aims to provide care services to patients at their homes instead of going to
the hospital. We dealt with three different problems from the optimization
viewpoint. In the first one, we considered a deterministic model to tackle the
HHCRSP with multiple time windows, multiple services, their synchronization if
they are required to be simultaneous and skill requirements. We proposed a new
mathematical to solve this problem along with a General Variable Neighborhood
Search (GVNS) based heuristic to solve large instances. In the second problem,
we extended the deterministic model to cope with uncertainties in terms travel
and service times. We proposed two Stochastic Programming with Recourse (SPR)
models. In the first SPR model, we defined the recourse as a penalty cost for
the tardiness of services and a remuneration for caregivers’ overtime. In the
second SPR model, we defined the recourse as skipping patients if their time
windows should be violated. We embedded Monte Carlo simulation, which is used
to estimate the expected value of recourse, into a Genetic Algorithm (GA)
based heuristic to solve SPR models. In the last problem, we kept the multi-
objective aspect of the deterministic model without aggregating its objective
functions, and we used algorithms based on Pareto dominance to find the non-
dominated solutions and then involve the decision-maker to select which one he
prefers. Two approaches, Pareto and decomposition based, with multi-objective
evolutionary algorithms are adopted to solve the HHCRSP. Three algorithms are
implemented: Non-Dominated Sorting Genetic Algorithm II  (NSGA-II), Multi-
Objective Evolutionary Algorithm based on Decomposition (MOEA/D) and a hybrid
NSGA-II with MOEA/D (hybrid) algorithm. Computational results highlighted the
efficiency of GVNS to solve the deterministic model and the adequacy of the GA
to be used with the simulation to solve the SPR model. For the multi-objective
HHCRSP, computational results and performance measures inferred that the
hybrid algorithm found solutions that better approximate the Pareto front
while the MOEA/D algorithm solved instances faster in terms of CPU running
times.

Doctoral Studies Center "SCIENCE, ENGINEERING AND SUSTAINABLE DEVELOPMENT"
(CEDoc SIDD)

Research Laboratory : SI2M

Doctoral thesis in Applied Mathematics

Under the theme:

Mathematical models and heuristics
for the home health care routing
and scheduling problem

Prepared by:

Mohammed Bazirha

Supervised by:

Pr. | Abdeslam Kadrani
---|---
Pr. | Rachid Benmansour

Defended on December 29, 2022 at INSEA-Rabat

Jury:

Pr. Adil | Kabbaj | PES at INSEA-Rabat | President
---|---|---|---
Pr. Abdeslam | Kadrani | PES at INSEA-Rabat | Thesis Supervisor
Pr. Rachid | Benmansour | PH at INSEA-Rabat | Thesis Co-Supervisor
Pr. Rachid | Ellaia | PES at EMI-Rabat | Reviewer
Pr. Souad | El Bernoussi | PES at Faculty of Sciences Rabat | Reviewer
Pr. Youssef | Benadada | PES at ENSIAS-Rabat | Reviewer

Academic year: 2021-2022.

Acknowledgment

Words cannot express my gratitude to my thesis supervisor Pr. Abdeslam Kadrani
and my thesis co-supervisor Pr. Rachid Benmansour for their supervision as
well as for their support, their relevant remarks and their encouragement.

Also, I have the honor to express my sincere thanks to the President Pr. Adil
Kabbaj. I am also grateful to reviewers Pr. Rachid Ellaia, Pr. Souad El
Bernoussi and Pr. Youssef Benadada for agreeing to be members of the jury, for
the time they devoted to reading the report and for their remarks and comments
that helped to improve the quality of the report.

Lastly, I would be remiss in not mentioning my family, especially my parents.
Their belief in me has kept my spirits and motivation high during this
process. I would also like to thank my friends and everyone who has encouraged
me.

Dedication

To my parents

No words can express my love, respect and gratitude for your tenderness and
the sacrifices you have made for my education and well-being.

To all my family members

For the love and affection they have given me throughout my life, for their
sacrifice, their trust and their patience.

To anyone

Who has taught me to appreciate the essence of life.

I dedicate this work.

List of Abbreviations

HHC

    Home Health Care
HHCRSP

    Home Health Care Routing and Scheduling Problem
GA

    Genetic Algorithm
GVNS

    General Variable Neighborhood Search
NSGA-II

    Non-Dominated Sorting Genetic Algorithm II
MOEA/D

    Multi-Objective Evolutionary Algorithm based on Decomposition
VRPTW

    Vehicle Routing Problem with Time Windows
SPR

    Stochastic Programming with Recourse
VRP

    Vehicle Routing Problem
VNS

    Variable Neighborhood Search
TS

    Tabu Search
SA

    Simulated Annealing
MOEAs

    Multi-Objective Evolutionary Algorithms

Mathematical modeling; Stochastic optimization; Multi-objective optimization;
Home health care; Routing and scheduling; Multiple time windows;
Synchronization; Meta-heuristics.

utf8

ملخص

تتناول هذه الأطروحة مشكل تحديد المسارات والجدولة الزمنية للرعاية الصحية
المنزلية (HHCRSP)، وهي فئة من مشاكل الجدولة الزمنية للقوى العاملة. يعد HHCRSP
امتدادًا لمشكل تحديد مسارات السيارات مع النوافذ الزمنية (VRPTW) والتي تُضاف
إليها قيود تتعلق بسياق الرعاية المنزلية. يهدف HHCRSP إلى تقديم خدمات الرعاية
للمرضى في منازلهم وتجنب التنقل إلى المستشفيات. تعاملنا مع ثلاث مشاكل مختلفة من
منظور البحث عن الحل الأمثل. في الأول، اعتبرنا نموذجًا حتميا لمعالجة HHCRSP
بنوافذ زمنية متعددة، المهارات المطلوبة، وخدمات متعددة، ومزامنتها إذا كان
مطلوبًا أن تكون الخدمات في أن واحد. لقد اقترحنا نموذجًا رياضيًا جديدًا و
خوارزمية إرشادية تعتمد على البحث العام متغير الجوار (GVNS) لحل الحالات الكبيرة
للمشكل. في المشكلة الثانية، قمنا بتوسيع النموذج الحتمي للتعامل مع عشوائية
أوقات السفر والخدمة. اقترحنا نموذجين للبرمجة العشوائية مع الرجوع (SPR). في
نموذج SPR الأول، حددنا الرجوع على أنه تكلفة جزائية لتأخر الخدمات ومكافأة عن
العمل الإضافي لمقدمي الرعاية. في نموذج SPR الثاني، قمنا بتعريف اللجوء على أنه
إلغاء زيارات المرضى الذين انتهكت نوافذهم الزمنية. قمنا بتضمين محاكاة مونت
كارلو، والتي تُستخدم لتقدير القيمة المتوقعة للرجوع، في خوارزمية إرشادية تعتمد
على الخوارزميات الجينية(GA) لحل النموذجينSPR. في المشكلة الأخيرة، احتفظنا
بطبيعة النموذج الحتمي متعدد الأهداف دون تجميع دواله الهدف، واستخدمنا
الخوارزميات القائمة على سيادة باريتو لإيجاد حلول غير مسودة وإشراك صانع القرار
في اختيار الحل الذي يفضل. تم اعتماد نهجين، قائمين على باريتو وعلى التقسيم، مع
خوارزميات تطورية متعددة الأهداف لحل HHCRSP. تم تنفيذ ثلاث خوارزميات: التصنيف
الجيني الغير المسود(NSGA-II)، الخوارزمية التطورية متعددة الأهداف القائمة على
التقسيم (MOEA/D) وخوارزمية هجينة بين NSGA-II و MOEA/D. أبرزت النتائج الحسابية
كفاءة GVNS في حل النموذج الحتمي ومدى ملاءمة GA لاستخدامها مع المحاكاة لحل
نموذج SPR. بالنسبة إلى HHCRSP متعدد الاهداف، ابرزت النتائج الحسابية ومقاييس
الأداء أن الخوارزمية الهجينة وجدت حلولًا تقارب بشكل أفضل حدود باريتو بينما
قامت خوارزمية MOEA/Dبحل الحالات بشكل أسرع من حيث مدة تشغيل وحدة المعالجة
المركزية.

الكلمات الرئيسية:  النمذجة الرياضية؛ الأمثلة العشوائية؛ الأمثلة متعددة
الأهداف؛ الرعاية الصحية المنزلية ؛ تحديد المسارات والجدولة الزمنية ؛ نوافذ
زمنية متعددة؛ التزامن؛ طرق إرشادية.

Résumé

Cette thèse traite le problème de routage et de planification des soins de
santé à domicile (HHCRSP), qui est une classe de problèmes de planification de
la main-d’œuvre. Le HHCRSP est une extension du problème de tournées de
véhicules avec fenêtres de temps (VRPTW) auquel sont ajoutées des contraintes
liées au contexte des soins à domicile. Il vise à fournir des services de
soins aux patients à leur domicile et à éviter les déplacements vers les
hôpitaux. Nous avons traité trois problèmes différents du point de vue de
l’optimisation. Dans le premier, nous avons considéré un modèle déterministe
pour traiter le HHCRSP avec des fenêtres de temps multiples, des services
multiples, leur synchronisation s’ils doivent être simultanés et des
compétences requises. Nous avons proposé un nouveau modèle mathématique et une
heuristique basée sur la recherche générale à voisinage variable (GVNS) pour
résoudre les grandes instances. Dans le deuxième problème, nous avons étendu
le modèle déterministe pour faire face aux incertitudes en termes de temps de
déplacement et de service. Nous avons proposé deux modèles de programmation
stochastique avec recours (SPR). Dans le premier modèle SPR, nous avons défini
le recours comme un coût de pénalité pour le retard des services et une
rémunération pour les heures supplémentaires des soignants. Dans le second
modèle SPR, nous avons défini le recours comme le fait de sauter des patients
si leurs fenêtres de temps ne sont pas respectées. Nous avons intégré la
simulation de Monte-Carlo, qui est utilisée pour estimer l’espérance du
recours, dans l’heuristique basée sur l’algorithme génétique (AG) pour
résoudre les modèles SPR. Dans le dernier problème, nous avons gardé la nature
du modèle multi-objectif, sans agréger ses fonctions objectifs, et nous avons
utilisé les algorithmes basés sur la dominance de Pareto pour trouver les
solutions non dominées et impliquer par la suite le décideur pour choisir
celle qu’il préfère. Deux approches, basées sur Pareto et sur la
décomposition, avec des algorithmes évolutionnaires multi objectifs sont
adoptés pour résoudre le HHCRSP. Trois algorithmes sont mis en œuvre :
l’algorithme génétique de tri non dominé II (NSGA-II), l’algorithme
évolutionnaire multi objectifs basé sur la décomposition (MOEA/D) et un
algorithme hybride NSGA-II avec MOEA/D (hybride). Les résultats de calcul ont
mis en évidence l’efficacité du GVNS pour résoudre le modèle déterministe et
l’adéquation de l’AG à être utilisé avec la simulation pour résoudre le modèle
SPR. Pour le modèle multi objectifs, les résultats de calcul et les mesures de
performance ont montré que l’algorithme hybride a trouvé des solutions qui
s’approchent mieux de la frontière de Pareto, tandis que l’algorithme MOEA/D a
résolu les instances plus rapidement en termes de temps d’exécution du CPU.

Mots clés : Modélisation mathématique; Optimisation stochastique; Optimisation
multi-objectifs; Soin à domicile; Routage et planification; Fenêtres de temps
multiples; Synchronisation; Méta-heuristiques.

Résumé substantiel

Le domaine des soins de santé à domicile (HHC) est un domaine de recherche qui
a pris ces dernières années un énorme essor et a fait l’objet d’une attention
croissante en raison de l’augmentation de l’espérance de vie et du faible taux
de natalité. Les HHC visent à fournir un large éventail de services aux
patients à leur domicile, dans un environnement personnel [31]. Ces services
permettront aux patients de vivre de manière autonome le plus longtemps
possible, même en cas de blessure, de maladie, de vieillissement ou de maladie
invalidante. Ils couvrent des soins médicaux, comme les soins infirmiers, la
physiothérapie et l’orthophonie. Les services de HHC peuvent même concerner
des tâches dans d’autres activités de la vie quotidienne des personnes âgées
telles que les aider à manger, à s’habiller et se laver et autres tâches
ménagères.

Le HHC est l’une des alternatives aux traitements hospitaliers classiques qui
ont vu le jour grâce aux progrès techniques, organisationnels et
thérapeutiques. Il était initialement destiné à réduire l’engorgement des
hôpitaux pour certains patients. Ce type de soins est en plein développement
et est de plus en plus demandé par les patients puisqu’il leur permet d’être
traités à domicile. Le HHC devrait générer au moins trois avantages qui sont :
la diminution des admissions à l’hôpital, la diminution de la durée
d’hospitalisation et la possibilité pour les patients de rester à leur
domicile et de recevoir des soins et de l’assistance [31].

Dans le rapport mondial sur le vieillissement et la santé de 2015, il était
mentionné que les gens devraient vivre en moyenne jusqu’à 77 ans, dont 15
seraient passés avec une forme de handicap. Le rapport mentionne également que
dans l’un des plus grands hôpitaux français, 20 % de tous les patients âgés de
plus de 70 ans étaient significativement moins capables d’effectuer les tâches
de base nécessaires à la vie quotidienne. En outre, la proportion de personnes
âgées ne cesse d’augmenter dans les pays européens et devrait encore
s’accroître dans les décennies à venir [94]; de même, les membres de la
famille vivent plus souvent séparés les uns des autres [74].

Ces dernières années, les questions liées à la santé ont attiré l’attention
d’un grand nombre de chercheurs. Leurs études sont menées non seulement du
point de vue des techniques sociales et médicales, mais aussi du point de vue
de l’optimisation. L’optimisation a concerné un large éventail de
caractéristiques et de contraintes des opérations de soins de santé à
domicile. Ces caractéristiques concernent l’organisation des soins à domicile,
les soignants et les patients. Le HHCRSP est considéré comme une version
étendue du problème de tournés de véhicules avec fenêtres de temps (VRPTW)
auquel sont ajoutées des contraintes liées au contexte des HHC. Outre la
définition des itinéraires des soignants, il s’agit également de définir leur
affectation aux patients et de planifier leurs visites pour fournir les
services demandés. Bien que les études précédentes aient traité un grand
nombre de caractéristiques et de modèles, elles présentent encore certaines
limites. La première limite dans les modèles déterministes qui sont bien
étudiés par la communauté des chercheurs, est la non prise en compte des
fenêtres des temps multiples. De plus, dans la plupart des études, les
services multiples et leur synchronisation ne sont considérés que comme des
services doubles par patient. De toute évidence, la combinaison de ces deux
caractéristiques dans un même modèle n’a pas été envisagée jusqu’à présent.
Par conséquent, les modèles précédents (eg. [74, 1, 84, 49, 68]) deviennent
impuissants de traiter le cas où les patients peuvent être disponibles dans
différentes périodes et qu’ils demandent des services multiples.

La deuxième limite est l’incertitude des paramètres, tels que les temps de
voyage et de service, qui sont rarement pris en compte dans le contexte des
soins à domicile. Dans le monde réel, ces deux paramètres ne peuvent être
déterministes et sont soumis à l’incertitude. Par conséquent, le calendrier
prédéfini doit être révisé à chaque fois qu’un changement imprévu dans les
situations pratiques est survenu. Autrement, si aucune action d’adaptation n’y
est apportée, il est probable qu’il y aura des retards dans les services
surtout pour les patients qui n’ont pas encore été visités. Cela qualifiera le
service par de qualité médiocre, voire même un service à risque.

Une autre reproche pour ces modèles concerne leurs approches de résolution,
qui utilisent souvent les techniques d’agrégation pour traiter le problème
d’optimisation multi-objectif. Le souci concerne essentiellement les
pondérations des fonctions objectifs qui doivent être connues a priori.
L’affectation des poids à des objectifs contradictoires est une tâche confuse,
le décideur doit être impliqué a posteriori pour sélectionner une solution
préférée parmi l’ensemble des solutions non dominées.

Cette thèse vise à proposer de nouveaux modèles et approaches pour surmonter
les limitations susmentionnées dans le HHCRSP. Le premier objectif est de
proposer un modèle déterministe général qui peut traiter simultanément un
nombre arbitraire de services ainsi qu’un nombre arbitraire de fenêtres de
temps pour chaque patient. Le second objectif est lié à l’incertitude des
paramètres. Il vise à proposer une solution qui prend en compte l’incertitude
des temps de déplacement et de service pour établir une planification robuste.
Le troisième objectif est de développer des algorithmes qui peuvent fournir
l’ensemble des solutions non dominées, puis impliquer le décideur a posteriori
pour sélectionner la solution qu’il préfère.

La première contribution traite une version déterministe du HHCRSP où des
nouvelles contraintes sont considérées, telles que les fenêtres de temps
multiples, les services multiples par patient, leur synchronisation s’ils
doivent être fournis simultanément, et les compétences requises. Dans une
première version, on étudie le problème uniquement avec des fenêtres de temps
multiples considérées comme flexibles, et on montre par une comparaison les
avantages de l’utilisation de fenêtres de temps multiples. Ensuite, dans la
version étendue, on propose un nouveau modèle où chaque patient peut demander
plusieurs services qui peuvent être simultanés, ce qui implique la
synchronisation des visites des soignants. Compte tenu de la complexité du
problème, qui est NP-difficile, nous proposons une heuristique basée sur la
recherche générale à voisinage variable (GVNS) pour résoudre les grandes
instances dans un temps de calcul raisonnable.

La deuxième contribution aborde l’incertitude des temps de déplacement et de
services qui peuvent survenir à tout moment dans les tournées des soignants.
Deux modèles de programmation stochastique avec recours (SPR) sont proposés
pour établir une planification robuste qui prend en compte de l’incertitude
des paramètres. Dans le premier modèle, le recours est défini comme un coût de
pénalité pour le retard des opérations de services et une rémunération pour
les heures supplémentaires des soignants. Ce modèle tient compte de plusieurs
services par patient et de leur synchronisation s’ils doivent être simultanés.
Dans le deuxième modèle, le recours est défini comme le fait de sauter un
patient si ses périodes de disponibilité ne sont pas respectées. Ce modèle
suppose que les patients peuvent spécifier plusieurs fenêtres de temps, qui
sont considérées comme fixes. La simulation de Monte Carlo est utilisée pour
estimer la valeur de recours attendue pour les deux modèles, qui est intégrée
dans l’algorithme génétique pour résoudre les deux modèles SPR.

La troisième contribution concerne le HHCRSP avec multi-objectifs résolu par
les algorithmes conçus pour approcher la frontière de Pareto. On suppose que
le décideur doit intervenir a posteriori pour sélectionner une solution parmi
un ensemble de solutions non dominées. Trois objectifs sont optimisés
simultanément. Il s’agit de minimiser les temps de déplacement et d’attente
des soignants et d’équilibrer leur charge de travail. Des approches basées sur
Pareto et la décomposition avec des algorithmes évolutionnaires multi-
objectifs sont adoptées pour résoudre le HHCRSP avec des fenêtres de temps
multiples. Trois algorithmes sont mis en œuvre à savoir: l’algorithme
génétique de tri non dominé II (NSGA-II), l’algorithme évolutionnaire multi-
objectif basé sur la décomposition (MOEA/D) et un algorithme hybride.

###### Contents

  1. Introduction
  2. 1  Literature review
    1. 1.1 Introduction
    2. 1.2  Home health care routing and scheduling problem
      1. 1.2.1 Related problems
      2. 1.2.2 Criteria considered in the home health care models
      3. 1.2.3 Constraints considered in the home health care models
      4. 1.2.4 Resolution methods
      5. 1.2.5 Positioning our contributions with respect to the state of art
    3. 1.3 Conclusion
  3. 2 Deterministic home health care routing and scheduling problem
    1. 2.1 Introduction
    2. 2.2 Home health care routing and scheduling problem with multiple soft time windows
      1. 2.2.1 Problem statement
      2. 2.2.2 Mathematical formulation
      3. 2.2.3 Variable neighborhood search
      4. 2.2.4 Numerical experiments
    3. 2.3 Home health care routing and scheduling problem with multiple hard time windows and multiple synchronized services
      1. 2.3.1 Problem statement
      2. 2.3.2 Mathematical formulation
      3. 2.3.3 Variable neighborhood search
      4. 2.3.4 Numerical experiments
    4. 2.4 Conclusion
  4. 3 Stochastic home health care routing and scheduling problem
    1. 3.1 Introduction
    2. 3.2 Stochastic home health care routing and scheduling problem with multiple synchronized services
      1. 3.2.1 Problem statement
      2. 3.2.2 Mathematical formulation
      3. 3.2.3 Genetic algorithm
      4. 3.2.4 Variable neighborhood search
      5. 3.2.5 Numerical experiments
    3. 3.3 Stochastic home health care routing and scheduling problem with multiple hard time windows
      1. 3.3.1 Problem statement
      2. 3.3.2 Mathematical formulation
      3. 3.3.3 Genetic algorithm
      4. 3.3.4 Numerical experiments
    4. 3.4 Conclusion
  5. 4 Multi-objective home health care routing and scheduling problem
    1. 4.1 Introduction
    2. 4.2 Multi-objective home health care routing and scheduling problem with multiple time windows
      1. 4.2.1 Problem statement
      2. 4.2.2 Solution approaches: multi-objective evolutionary algorithms
      3. 4.2.3 Numerical experiments
    3. 4.3 Conclusion
  6. General conclusion and perspectives

###### List of Tables

  1. 1.1  Constraints and assumptions considered in home health care problems.
  2. 1.2  Stochastic parameters considered in  and  problems
  3. 2.1 Example of solution encoding
  4. 2.2 Example of visiting order
  5. 2.3 example of caregivers’ assignment to patients
  6. 2.4 Numerical results of tested instances
  7. 2.5 Example of solution encoding
  8. 2.6 Example of infeasible solution under the synchronization constraint
  9. 2.7  Tested instances details
  10. 2.8 Numerical results for instances with single service and single time window.
  11. 2.9 Numerical results for instances with multiple services and single time window.
  12. 2.10 Numerical results for instances with single service and multiple time windows.
  13. 2.11 Numerical results for instances with multiple services and multiple time windows.
  14. 2.12 Numerical results for small instances with varying the number of time windows from 1 to 3 and the percentage of patients requresting multiple services from 20% to 60%.
  15. 2.13 Numerical results for large instances with multiple services and multiple time windows.
  16. 2.14  Comparison between solutions found by the CPLEX solver and
  17. 3.1 Example of a solution
  18. 3.2 Example of mutation operators
  19. 3.3 Example of visiting order
  20. 3.4 example of caregivers’ assignment to patients
  21. 3.5 Tuning parameters
  22. 3.6  Tested instances details
  23. 3.7 Results of solving the set $SS$ instances with deterministic parameters.
  24. 3.8 Results of solving the set $MSS$ instances with deterministic parameters.
  25. 3.9 Results of solving small instances (subsets $A$ and $D$) with stochastic parameters using  and  based heuristics.
  26. 3.10 Results of solving medium and large instances with stochastic parameters using  based heuristic.
  27. 3.11 Deterministic solutions with stochastic parameters and solutions found by the SPR model for the small instances.
  28. 3.12  Tested instances details
  29. 3.13 Numerical results of tested instances with single time window and deterministic parameters
  30. 3.14 Numerical results of tested instances with multiple time windows and deterministic parameters
  31. 3.15 Numerical results of tested instances with stochastic parameters
  32. 3.16 Solution of instance $A5$ with single time window and deterministic parameters
  33. 3.17 Solution of instance $A5$ with single time window and stochastic parameters
  34. 3.18 Caregiver 1 starting and completion times for assigned patients considering the solution found by the deterministic model for instances $A5$ with single time window
  35. 3.19 Caregiver 1 starting and completion times for assigned patients considering the solution found by the SPR model for instances $A5$ with single time window
  36. 4.1 Example of visiting order
  37. 4.2 example of caregivers’ assignment to patients
  38. 4.3  Tuning parameters
  39. 4.4 Comparison between instances with one and two availability periods according to coverage set indicator
  40. 4.5 Comparison of algorithms according to hypervolume indicator, front size and CPU time.
  41. 4.6  Comparison of algorithms according to coverage set indicator.

###### List of Figures

  1. 2.1 Example of switch neighborhood moves
  2. 2.2 Example of inter-swap neighborhood moves
  3. 2.3 Example of intra-shift neighborhood moves
  4. 2.4 Example of intra-swap neighborhood moves
  5. 2.5 Objective function values according to the number of time windows (TW)
  6. 3.1 Example of parents and an offspring
  7. 3.2 Example of caregivers’ crossover operator
  8. 3.3 Example of patients’ crossover operator
  9. 3.4 Comparison of solutions found by CPLEX,  and  for the instances of the set $SS$ with deterministic parameters.
  10. 3.7 CPU running times elapsed to solve the first instance of each subset using the simulation embedded into  for a single iteration.
  11. 3.8 Example of a parent and an offspring
  12. 3.9 Example of patients’ crossover operator
  13. 3.10 Example of caregivers’ crossover operator
  14. 3.11 CPLEX and  solutions comparison for instances of the set $STW$ with deterministic parameters.
  15. 3.14 Comparison of the best-found solutions for the SPR model according to time windows
  16. 4.1 Hypervolume indicator for  algorithm according to time windows (TW)
  17. 4.4  Comparison of algorithms for instances with one availability period according to hypervolume indicator

## Introduction

The HHC is an evolving research area that has received growing consideration
in the recent years due to increasing life expectancy and low birth rates. It
aims to provide a wide range of services to patients at their homes in a
personal environment [31]. It will allow them to live autonomously for as long
as possible even with an injury, illness, aging or disabling disease. It
covers a wide range of services that may involve medical care, such as
nursing, physical therapy, and speech therapy. It may include helping elderly
individuals with activities of daily living such as eating, dressing, and
bathing. It can also involve assistance with cooking, cleaning, and other
housekeeping.

The HHC is one of the alternatives to classical hospital treatments that have
arisen thanks to technical, organizational, and therapeutic progress. It was
initially intended to reduce hospital overcrowding for some patients. This
type of care is in full development and is increasingly requested by patients
since it allows them to be treated at home. The HHC is expected to generate at
least three advantages which are: a decrease in hospital admissions, a
decrease in hospitalization duration and the ability for patients to remain in
their homes and receive care and assistance [31].

Background and motivation

In the world report on ageing and health of 2015, it was mentioned that people
are expected to live on average to 77 years, of which 15 would be spent with
some form of disability. The report also mentions that in one of France’s
largest hospitals, 20 percent of all patients over the age of 70 were
significantly less able to perform the basic tasks necessary for daily living.
In addition, the proportion of older people is increasing steadily in European
countries and is predicted to rise still further in the coming decades [94] as
well as family members live more often separated from each other [74].

HHC issues have attracted the attention of a large number of researchers in
recent years. Their studies are not only from the perspective of social and
medical techniques, but also from the optimization viewpoint. The optimization
has concerned a wide range of characteristics and constraints of HHC
operations. These features concern the HHC organization, caregivers, and
patients. The HHCRSP is considered as an extended version of the VRPTW to
which constraints related to the HHC context are added. In addition to
defining caregivers’ routes, it also involves their assignment to patients and
scheduling their visits to provide the requested services.

We choose to deal with the HHCRSP to contribute in improving health care
systems and patients’ daily living. Thus, allowing people requiring care to be
treated at home in order to avoid moving to hospitals and overcrowding them.
The HHCRSP is considered as one of the constrained problems where limited
resources must be optimized to satisfy the maximum of constraints. To achieve
that, we aim to propose new models and heuristics to efficiently assign the
limited number of caregivers to patients by optimizing one or more criteria
taking into account many real-life constraints.

Research context

Although previous studies have dealt with a large number of features and
models, they still have some limitations. The first limitation concerns
deterministic models, which are well studied by the research community. In
these models, multiple time windows are not considered. According to [31], it
is interesting to define all periods in which patients will be available to
receive care services. Furthermore, multiple services and their
synchronization in most studies considered them only as double services per
patient. In [85], the authors have conducted a survey of many French home care
structures, which showed that patients need several care services per day.
Therefore, the synchronization of services should be considered if a patient
needs more than a caregiver to provide one or multiple simultaneous services
such as dressing, bathing, getting out of bed and dosing medicine [84].
Obviously, combining the two features in the same model has not been
considered so far. These previous models are powerless to deal with cases
where patients can be available in many periods as well as if he requested
multiple services. The second limitation is the uncertainty of parameters,
such as travel and service times, which are less considered in the HHC
context. In the real world, these two parameters cannot be deterministic and
are exposed to uncertainty. Therefore, the predefined schedule should be
revised whenever an unforeseen change in practical situations has occurred.
Otherwise, if no adaptation action is taken, there will be delays in services,
especially for patients who have not yet been visited. This could qualify the
service as a poor quality, or even risky service. The last limitation for
these models is related to their resolution approaches, which often use
aggregation techniques in most studies to deal with the multi-objective
optimization problem. The issue mainly concerns the weights of the objective
functions that should be known a priori. Assigning weights to conflicting
objectives is a difficult task, the decision maker needs to be involved a
posteriori to select a preferred solution from the non-dominated solutions
set.

Objectives, research questions and contributions

This thesis aims to propose new models and methods to overcome the
aforementioned limitations in the HHCRSP. The first objective is to propose a
general deterministic model that can simultaneously deal with an arbitrary
number of services as well as an arbitrary number of time windows for each
patient. The second one is related to the uncertainty of parameters. It aims
to propose a solution that takes into account the uncertainty of travel and
service times to establish a robust planning. The third objective is to
develop algorithms than can provide the non-dominated solutions set, then
involve the decision maker a posteriori to select which solution he prefers.

In the first contribution, we dealt with a deterministic model where we
considered new complicated constraints. In [7], we developed a new
mathematical model to deal with multiple soft time windows with a maximum of
earliness ($E_{max}$) and a maximum tardiness ($T_{max}$) of services.
Patients could define all periods in which they are available to receive care
services. A soft/flexible time windows would increase the chance of finding a
feasible schedule as delays are accepted. However, any delay that occurs, in
the case of hard/fixed time windows, the schedule becomes impractical and the
company must resort to more caregivers (i.e. an additional cost) to keep a
reasonable quality of service. The soft/flexible time windows proposed with
$E_{max}$ and $T_{max}$ is a general case of hard/fixed time windows
($E_{max}=0$ , $T_{max}=0$) and of soft/flexible time
windows($E_{max}=\infty$, $T_{max}=\infty$). We developed a GVNS based
heuristic to reduce the computational time needed to solve the model.
Computational results show that instances with multiple time windows are
better optimized since the decision maker has many possibilities to schedule
the visits. Since patients need several care activities per day [85], we
extended the model to allow them to request many services with a possible
synchronization of several ones. A strategy to select a time window for each
patient and to ensure synchronization of simultaneous services, is proposed
and combined with the GVNS-based heuristic. This strategy is mandatory since,
for each patient, the selection of a time window could not be done
independently of his availability periods. In fact, since a single period
should be chosen to provide multiple services, this choice may be suitable for
one caregiver but not for another. GVNS generates solutions (caregivers’
routes and their assignment) while this strategy selects, for each patient, a
time window and ensures the synchronization of simultaneous services.

In the second contribution [8, 9, 10], we dealt with two stochastic models
where we considered the uncertainty of travel and service times parameters. We
proposed two stochastic programming models with recourse to deal with the
uncertainty. We estimated the expected value of recourse using Monte Carlo
simulation since computing the expected real value by an explicit mathematical
formula is very complex. We proposed a new stopping condition for the
simulation, instead of just running it for a maximum number of iterations (100
iterations as in [91]), to find a good estimation of the expected real value.
We embedded it into GA and GVNS based heuristics to solve the models with
stochastic parameters. In the first SPR model [9], we dealt with the HHCRSP
with multiple synchronized services. The objective is to minimize the
transportation cost and the expected value of recourse. The recourse is
defined as a penalty cost for patients’ delayed services and a remuneration
for caregivers’ overtime. We show through numerical tests that GVNS is not
suitable to be combined with the simulation to solve the SPR model and the
adequacy of the GA since its parameters do not depend the problem parameters.
In the second SPR model [10], we assumed that time windows are hard/fixed,
which must be respected without any earliness or tardiness. To ensure that the
requested services are provided within patients’ time windows, the recourse is
defined as skipping patients when their time windows will be violated. To
increase the chance of providing the maximum of services, patients can specify
multiple time windows. The objective is to minimize the transportation cost
and the expected value of recourse, which expressed as the average number of
unvisited patients.

Dealing with multi-objectives using aggregation techniques imply involving the
decision maker a priori to assign weights, which is a difficult task. To
overcome this issue, the last contribution is related to the multi-objectives
case where the decision maker is assumed to be involved a posteriori to select
the solution he prefers from then non-dominated solutions set. We use Pareto
and decomposition bases approaches with multi-objective evolutionary
algorithms to simultaneously optimize three objectives trying to approximate
the Pareto set. Minimizing caregivers’ total traveling times ($f_{1}$) is more
important than minimizing their transportation cost since the traveling time
depends on road conditions, which will be higher if such conditions are poor.
Waiting time ($f_{2}$) is considered to be unproductive [85] and must be
minimized. It is assumed that caregivers are paid for their regular working
time regardless of the amount of care they do [19]. To ensure fairness among
caregivers, their workload must be balanced ($f_{3}$). Three algorithms are
implemented: NSGA-II , MOEA/D and a hybrid NSGA-II with MOEA/D (hybrid)
algorithm.

Road map

This manuscript is divided into four chapters. Chapter 1 gives a literature
review of the studies dealing with the routing and scheduling in home health
care. We first focus on the travelling salesman problem and then the Vehicle
Routing Problem (VRP) and its variants since it is extended by the HHCRSP to
cover the additional constraints related to health care. A review of the
HHCRSP is done with a focus on objectives, constraints and resolution methods
considered in the literature. The constraints are notably divided into three
groups according to whether they concern the HHC organization, patients, or
caregivers. Finally, we show some limitations in models and methods proposed
by researchers and tackle it.

Chapter 2 deals with a deterministic version of the HHCRSP where new
constraints are considered, such as multiple time windows, multiple services
per patients, and the synchronization. In section 2.2, we study the problem
only with multiple time widows, which are considered as soft/flexible, and we
show through a comparison the advantages of using multiple time windows. Then
in section 2.3, an extended version of the model is proposed where each
patient can request many services that can be simultaneous, which involve the
synchronization of caregivers’ visits. Given the complexity of the problem,
which is NP-hard, we propose a GVNS based heuristic to solve large instances
in a reasonable computation time.

Chapter 3 addresses the uncertainty of travel and services times that may
arise anytime in caregivers’ routes. Two SPR models are proposed to establish
a robust planning that takes into consideration the uncertainty of parameters.
In section 3.2, the recourse is defined as a penalty cost for the tardiness of
services operations and a remuneration for caregivers’ overtime. This model
takes into consideration multiple services per patient and their
synchronization if they are required to be simultaneous. In section 3.3, the
recourse is defined as skipping a patient if his availability periods will not
be respected. This model assumes that patients can specify multiple time
windows, which are considered hard/fixed. Monte Carlo simulation is used to
estimate the expected recourse value for both models, which is embedded into
the GA to solve the two SPR models.

Chapter 4 deals with the multi-objective HHCRSP using algorithms designed to
approach the Pareto front. It is assumed that the decision maker is to be
involved a posteriori to select a solution from not dominated solutions set.
Three objectives are simultaneously optimized which are: minimizing
caregivers’ travel and waiting times as well as balancing their workload.
Approaches based on Pareto and decomposition with multi-objective evolutionary
algorithms are adopted to solve the HHCRSP with multiple time windows. Three
algorithms are implemented: NSGA-II, MOEA/D and a hybrid NSGA-II with MOEA/D
(hybrid) algorithm.

This thesis is concluded by a general conclusion in which we summarize the
work accomplished and the results obtained. Research perspectives are also
proposed for the pursuit of our research works.

Publication and research activities

The following is a summary of the papers produced and published in the course
of this thesis, listed in chronological order.

  * •

M. Bazirha, A. Kadrani, and R. Benmansour. Optimization of the stochastic home
health care routing and scheduling problem with multiple hard time windows.
International Journal of Supply and Operations Management, 9(2):235–250, 2022.

  * •

M. Bazirha, A. Kadrani, and R. Benmansour. Stochastic home health care routing
and scheduling problem with multiple synchronized services. Annals of
Operations Research, pages 1–29, 2021.

  * •

M. Bazirha, A. Kadrani, and R. Benmansour. Scheduling optimization of the home
health care problem with stochastic travel and care times. In 2020 5th
International Conference on Logistics Operations Management (GOL), pages 1–8.
IEEE, 2020.

  * •

M. Bazirha, A. Kadrani, and R. Benmansour. Daily scheduling and routing of
home health care with multiple availability periods of patients. In
International Conference on Variable Neighborhood Search, pages 178–193.
Springer, 2020.

  * •

Bazirha, M., Kadrani, A., Benmansour, R.. Home Health Care Routing and
Scheduling Problem with Multiple Time Windows and Multiple Synchronized
Services. (Preprint: submitted)

  * •

Bazirha, M., Kadrani, A., Benmansour, R.. Pareto and Decomposition Based
Approaches for the Multi-Objective Home Health Care Routing and Scheduling
Problem. (Preprint: submitted)

##  Chapter 1  Literature review

###  1.1 Introduction

Workforce scheduling problems consist of defining the schedules of hourly
workers to meet the demands in a workplace such as a restaurant, a hospital,
or a retail store. It is also a matter of defining schedules so that the
transition from one shift to another is smooth and the work remains
continuous. In many scenarios in which workers must carry out tasks at
different locations they require some form of transportation.

The workforce scheduling problem extends the travel salesman problem and VRP
to include also scheduling of workforce in the case that workers must travel
to carry out tasks at different locations. In [28], the authors presented four
types of workforce scheduling problems that require some form of workers’
transportation, which are: security personnel routing and rostering,
scheduling technicians, manpower allocation and home health care. The HHCRSP
is a type of workforce scheduling problem that is well-known and studied in
the last years due to its importance for people in need of daily living
services, our contributions are related to this problem.

###  1.2  Home health care routing and scheduling problem

The HHCRSP is class of workforce scheduling and routing problems (WSRPs) that
extend the VRP to also include the scheduling of caregivers’ visits to provide
patients’ requested services at different locations. Classical models and
methods studied in the VRP are not suitable to be used in general for the
WRSPs and in particular for the HHCRSP because it contains additional
characteristics related to workers such as skills requirements, dependencies
among tasks, working overtime and workload balancing… etc.

In the following we will present characteristics and constraints considered in
the literature for the HHCRSP and then show some limitations related to the
studies to tackle it. We start with related problems to the HHCRSP, then the
most criteria considered in the literature, and then the constraints and
features considered by researchers. The constraints are notably divided into
three groups according to whether they concern the HHC organization, patients,
or caregivers.

####  1.2.1 Related problems

Before going into greater detail about our contributions in the HHC context,
it is important to situate the HHC problem in the global context of the
vehicle routing problem. The latter problem is extended by the HHCRSP to cover
the additional constraints related to health care context.

#####  1.2.1.1 Travel salesman problem

The traveling salesman problem (also called TSP) is a combinatorial
optimization problem, studied since the 19th century, is one of the most well-
known in the field of operations research. It can be described as follows:
Given a set of cities and the distance between every pair of cities, the
problem is the challenge of finding the shortest and the most efficient route
(Hamiltonian Cycle) for a person to take given a list of specific destinations
(cities).

The TSP was mathematically formulated in the 1800s by the Irish mathematician
W.R. Hamilton and by the British mathematician Thomas Kirkman. In 1954,
Dantzig et al. [33] proposed a Mixed-integer linear program to solve the TSP.
Garey et al. [51] have proved that the TSP is NP-hard. The TSP is divided into
two categories. If the distance from one node to another is different from the
inverse distance, the TSP is called asymmetric (ATSP). In symmetric TSP
(STSP), this distance is the same. Sub-tours elimination constraints are the
hardest to satisfy since their number increases exponentially and equals
$2^{n-1}-2$. Miller et al. [78] have proposed a new formulation to reduce the
complexity of sub-tours constraints from $O(2^{n})$ to $O(n^{2})$.

#####  1.2.1.2 Vehicle routing problem

The VRP is an extension of the TSP, where it deals with many vehicles. The
problem is to define a tour for each vehicle to visit assigned customers. Each
one has a start and an end location, which typically is the depot.

According to Braekers et al. [20], Dantzig et al. [33] were the first to
introduce the VRP called "Truck Dispatching Problem". They proposed a
formulation of the problem to optimize the total traveled distance that
involves a fleet of homogeneous vehicle to serve the demand for oil of a
number of gas stations from a central hub. A few years later, Clarke et al.
[32] generalized this problem to a linear optimization problem commonly
encountered in the field of logistics and transportation. It is defined as
follows: a set of customers geographically scattered around a central depot
must be served by a fleet of vehicle with varying capacities.

The classical VRP, also known as the capacitated VRP (CVRP), it has been
extended in many ways to cover additional real-life constraints or features,
which has led to a large number of variants of VRP. In the case of vehicles
with varying capacities, the extended version is described in the literature
as the heterogeneous fleet VRP (HFVRP), also known as the mixed fleet VRP.
Each vehicle has a different capacity, the problem is how to assign customers
to vehicles in such way that the constraint of vehicle capacity is respected
along its route.

Another well-studied variant is the VRP with time windows (VRPTW). This
variant assumes that deliveries to a given customer must occur within a
certain time interval, which varies from customer to another. These time
windows could be considered as hard/fixed or soft/flexible. In the first case,
deliveries must respect the time interval, which the customer has specified
without any earliness or tardiness. However, in the second case, time windows
could not be respected, and delays can be accepted with a penalty cost. Others
studies such as [12, 45] have considered Multiple Time Windows for the VRP,
customers are supposed to be available in many periods, which they prefer.

The VRP with deliveries and pickups (VRPDP) [88] extends the VRP in such way
to allow the transportation of goods from a depot to customers as well as from
customers to the depot. It is defined in [88] as follows: A fleet of vehicles
is available with a given capacities, a start location, and an end location.
Each request is defined by the size of load to be transported, the origins and
the destinations. The origins denote the locations where goods will be picked
up and the destinations denote where the goods will be delivered. Each load
has to be transported by one vehicle from its origin location to its
destination location without any transshipment to others locations. VRPDP is
an important logistics problem that has many applications, mainly in reverse
logistics. An increasingly environment-friendly population implies more
collection of recyclable goods. Also, companies are increasingly aware of the
savings that can made by combining deliveries and collections.

The VRPDP has also many variants such as: The VRP with backhauling (VRPB),
also known as the linehaul-backhaul problem. Linehaul (delivery) points are
locations that will receive a quantity of goods. Backhaul (pickup) points are
locations that send a quantity of goods. The critical assumption is that all
deliveries must be made on each route before any pickups can be made. The VRP
with mixed deliveries and pickups (VRPMDP) does not make the above assumption
and allows deliveries and pickups to occur in any order on a vehicle route. In
the VRP with simultaneous deliveries and pickups (VRPSDP), the customers
simultaneously have delivery and pickup demand and the vehicles makes a single
stop to both deliver and pick up goods.

The multiple depot VRP (MDVRP) is an extension of the classic VRP. In its
original version, VRP considers only one depot from which a fleet of vehicles
departs and ends its tour. In the MDVRP, the fleet of vehicles is assigned to
multiple depot locations. Each vehicle comes from a depot to serve assigned
customers will return to the same depot.

The periodic VRP (PVRP) is a variation of the classic VRP in which delivery
routes are constructed for over a period of time (for example, multiple days).
The PVRP was introduced by Beltrami et al. [13] and has evolved into a large
body of works, with many interesting variants and applications emerging in
recent years. The PVRP occur in a wide range of applications, such as elevator
maintenance and repair, courier services, vending machine replenishment and
the collection of waste [47].

Despite a vast literature concerning the VRP and its variants, it is however
very difficult, if not impossible, to apply studied cited above on workforce
scheduling problems in general and particularly for the home health care
routing and scheduling problem. Indeed, workforce scheduling problems is a
specific case of application bringing new constraints, which requires an
adapted modeling and methods of resolution.

In the following, we will present the scientific literature specific to
workforce scheduling problem that involve the transportation of workers in the
HHC context addressed in this work.

####  1.2.2 Criteria considered in the home health care models

Finding the optimal program with respect to a set of constraints implies the
optimization of one or more criteria. Otherwise, the problem is reduced to
constraint satisfaction, which seeks a feasible solution according to a set of
constraints to be satisfied. According to [31], four main types of criteria
are the most objective functions tackled in the literature, which are:
minimize caregivers’ transportation cost, minimize the number of unassigned
services, minimize the number of caregivers and maximize satisfaction.

Approximately 90% of papers [31] consider the transportation cost as a
criteria to be optimized, which often is expressed as the sum of distances
traveled or the travel time incurred by caregivers. Minimize the number of
unassigned services arises when the HHC company may not have sufficient
caregivers to provide all services requested by patients. To overcome this
issue, the company can subcontract to another HHC company these unassigned
services with a cost, which is always higher than the cost incurred by the
provider if it is performed internally. Some studies such as [58, 3, 61]
considered minimizing the number of caregivers as a criteria. The HHC company
must be flexible to adjust the number of caregivers on the routes each day
[31].

Maximize the satisfaction involve both caregivers and patients. For patients,
this goal can be achieved, for example, by respecting their availability
periods, which could be as hard/fixed time windows [2, 5, 70, 85], or
soft/flexible [59, 74, 80, 99]. In the first case, providing services to
patients must be done without any earliness or tardiness. In the second case,
a penalty cost is considered for any earliness or tardiness. Another example
of considering patients’ satisfaction is related to their preferences
regarding caregivers. A patient may prefer a caregiver over others, especially
in the case of continuity of care where patient may be visited several times.
Therefore, he can prefer visited by the same caregiver. Gender and language
are some examples of preferences.

Caregivers’ satisfaction is modeled as balancing their workload, which is the
main criterion considered in the literature [31]. The decision maker has to
ensure that caregivers have worked in a balanced way by avoiding gap between
them in terms of workload. This goal could be achieved by balancing the number
of services assigned to each caregiver or balancing the working time in such
way that amount of time worked by each caregiver must be close to each other.
Balancing the number of services assigned to each caregiver would only be
effective if all services have very close processing times. The decision maker
also should consider the unavailability of caregivers, especially in the case
of a medium- or long-planning horizon [80, 105, 6]. Workday preferences,
vacations, days off or sick leaves are some examples used in the literature
that motivate using the unavailability of caregivers constraint in the studies
[31].

When many criteria are considered and must be simultaneously optimized,
aggregation techniques are the most used in the literature. In [40], a
lexicographical order is used to solve a bi-objective problem that aims to
maximize the service level and to minimize caregivers’ traveling distance.
This approach is based on a priori knowledge of some decision maker
preferences to establish the lexicographic order, which is not a simple task.
Few studied adopted Pareto approach to deal with the multi-criteria such as
[44, 37, 19]. As far as we know approaches based on indicator and
decomposition are not used so far in the HHC context.

####  1.2.3 Constraints considered in the home health care models

HHC issues have attracted the attention of a large number of researchers in
recent years. Their studies are not only from the perspective of social and
medical techniques, but also from the optimization viewpoint [91]. A
significant diversity among features are considered in the existing HHCRSP
models to deal with the characteristics and constraints of HHC operations.
According to [31], these features can be divided into three groups, depending
on whether they are related to the HHC service organization, patients, or
caregivers.

#####  1.2.3.1 Constraints related to the HHC organization

The constraints related to the HHC organization could be divided into three
groups according to [31], which are: temporal, assignment, and geographic
constraints.

In temporal constraints, two characteristics are to be considered when the
decision maker defines caregivers’ schedule. The first one is the planning
horizon that could be considered as short, medium, or long term. The length of
the planning horizon considered in the HHCRSP models has been often one day
[74, 84, 2, 99] or one week [5, 6]. In [105], a planning horizon of four weeks
has been considered. The second one is the frequency of routing decision,
which refers to how many times the decision maker repeat the routing decision
within the planning horizon. The long-term horizon is affected by new patients
entering the system continuously and therefore the conditions of previously
admitted patients and the availability of caregivers change. Therefore, either
the routing decisions can be changed at fixed time intervals or the update can
be done when certain conditions are met [31].

In assignment constraints, which are largely related to the continuity of
care, also called patient–nurse loyalty in [80] or employee regularity [50],
patients must be visited by the same caregiver and during approximately the
same time. Care services can be performed for patients under full, partial or
no continuity of care, which avoid losses of information among caregivers [31]
and builds a relationship of confidence with patients [48]. In the first case,
a patient assigned to one and only one caregiver who is responsible for
his/her care. The second case usually occurs when a patient requires more than
one type of care. A reference caregiver can be affected, as in the case of
full continuity of care, to coordinate providing the requested services by
other caregivers. In the last case, the decision maker does not need to
consider the previous information related to the caregiver–patient assignment.

The dispersion of patients in a geographic area may let the decision maker to
cluster the existing teams into districts based on relevant criteria such as
territory, caregiver skills, and patient needs. Such a district-based approach
allows to reduce travel times in caregivers’ routes within an assigned
district and lets to form smaller care teams that can be easily managed. In
the single-district case, the decision maker does not split caregivers into
smaller clusters, which is the simplest way of managing teams and is
considered in [74]. However, in the case of multiple districts [40, 43, 65], a
caregiver is assigned to a geographical area or a subset of areas and may only
serve patients within districts in which he is assigned.

Other types of HHC services rather than classical ones have been considered in
the literature, which are related to geographic constraints. These services
include collecting biological samples and/or delivery of drugs or materials.
Problems including these type of services such as [63, 22, 69] are similar to
VRP with pickup and delivery. Locations where pickup and delivery services are
performed must be included int the parameters considered in the HHCRSP models,
where routes are optimized considering these locations. The HHC center,
medical laboratories, pharmacies and chemotherapy/radiotherapy centers are
some examples of these locations [31] that deliver these services.

#####  1.2.3.2 Constraints related to patients

HHC companies deal with a wide range of service types, each one define the
nature and frequency of its visit. In the literature, regarding constraints on
the frequency of visits, some authors assume that a patient needs to be
visited once a day [59] or once a week [5]. However, other studies consider a
patient can be visited several times a day [84] or a week [80]. These later
cases arise when patients usually require multiple services. The services may
have a temporal dependency (e.g. [85, 74, 84]) if they must be provided on the
same day. Some studies consider synchronized services, which arise when a
patient need more than a caregiver to perform his requested services. For
instance, overweight patient requires two caregivers to lift him/her. Other
studies consider also disjunction among services, which must not performed
simultaneously. For example, physical therapy cannot be delivered while a
blood sample is collected.

Most studies consider a single availability period for each patient in which
he will be available to receive caregiver(s). As described in the VRPTW,
studies in HHCRSP also consider time windows as hard/fixed time [2, 5, 70, 85]
or soft/flexible [59, 74, 80, 99]. In the first case, patients’ availability
periods must be respected without any violation while in the second case,
these time windows can be violated with a penalty cost. In [16], the authors
assign to each patient two time windows, the first one is soft/flexible that
is included the second one, which is hard/fixed. Some studies such as [105,
98] consider patients’ preferences where a caregiver cannot be assigned to a
patient for gender incompatibility or personal reasons.

In terms of geographic constraints, most studies consider Euclidean distances
between patients’ locations for experiments [31]. Some studies compute travel
times based on a geographic information system [11]. Studies such as [59, 86]
have considered a multi-modal transportation network, where caregivers can
take three main modes of transportation between patients’ homes, which are:
car, walking and public transportation. Travel times between patients can
change significantly according to the time of day, e.g., rush hour or off-peak
times. Therefore, Rest and Hirsch [87] have considered a model that takes into
account time-dependent travel times.

#####  1.2.3.3 Constraints related to caregivers

Most HHCRSP studies consider a predefined working time for caregivers during
which they will visit patients to provide their requested care services in
their homes. Caregivers’ availability is either considered as hard/fixed [85,
70, 19] or soft/flexible [98]. In the first case, caregivers’ overtime is not
allowed and exceeding the predefined working time of a caregiver is considered
as an infeasible solution. However, in the soft/flexible case, caregivers’
extra working times is allowed with a penalty cost in the objective function.

Breaks are also considered in the literature for caregivers, for instance, to
take lunch and some rest. They should be programmed into the caregivers’
routes by defining the start and end of the break as well as its duration. The
break can be considered by forcing the caregiver to take a break either within
a specific time interval [99, 70], or when a certain route length is reached
[97].

Caregivers’ assignment must respect skill (also called qualification)
requirements [74, 19, 68, 59, 40] while providing a specific service. Three
formulations are used in the literature: The first one is to assign a single
qualification for each caregiver. The second approach is to assign several
skills for each caregiver, which is more general. And the third case that is
based on level of qualification, which represents the minimum level for a
caregiver to provide a requested service.

Caregivers are paid for their regular working time regardless of the amount of
care they do. To ensure equity among them, the decision maker may consider
caregivers’ workload balancing while assigning them to patients. Ensure a
perfect balance of the workload among caregivers is difficult if it not
impossible task, thus this constraint is considered as a soft and generally
embedded in the objective function.

Like the MDVRP, the HHCRSP studies also consider multiple HHC centers, but
most of them assume a single center from which caregivers begin and end their
tours. In [98], the authors proposed three types of starting and ending
locations for caregivers which are: 1) caregivers start and finish at the HHC
center; 2) caregivers start and end their tours at home; 3) and caregivers
start and end their tours at home, but working time do not include travel
times between caregivers’ homes and patients. In [5], the authors dissociated
the starting and ending depots for each caregiver, which is more generic and
cover both single and multiple depots.

####  1.2.4 Resolution methods

In the following, we will present the different solution methods used in the
literature to solve the HHCRSP.

#####  1.2.4.1 Exact methods

Exact methods guarantee to reach the optimal solution for a given problem.
However, the solving algorithms have an exponential complexity, which
increases with the problem size. Therefore, they can only solve instances of
limited size, depending on the nature of the problem. In addition, they are
used to benchmark approximate methods and analyze their behavior on optimal
solutions. In the literature, studies that used exacts methods are: branch-
and-price [84], column generation [106] and branch-and-cut-and-price [100].

#####  1.2.4.2 Approximate methods

Since exacts methods are powerless to reach the optimal solution or even a
feasible one for large instances, approximate methods have been used widely by
the community of researchers to overcome exact methods limitation. The
approximate methods are more flexible as they allow to control the stopping
criteria: maximum number of iterations, maximum CPU running time or maximum
number of no-improvement over the best solution. However, they do not
guarantee to reach the optimal solution, but at least they are able to find a
feasible one in a reasonable computational time.

In the literature, there are a wide variety of approximate solution methods.
Heuristics that are problem-dependent and meta-heuristics are problem-
independent techniques that can be applied to a broad range of problems.

Regarding heuristics used in the literature, Redjem et al. [85] defined a
heuristic with two-phases. The first one is to search the optimal tours by
calculating for each caregiver the shortest travel duration. The second one is
to introduce the precedence and the synchronization constraints. Cire et al.
[30] proposed a heuristic adaptation of logic-based Benders decomposition to
solve the HHC problem. A greedy heuristic enhanced by constraint programming
(CP) is used to solve the Benders master problem. Bowers et al. [18] modified
the Clarke-Wright algorithm [32] to include additional components in the
“saving”, which are the continuity of care and the satisfaction of patients’
preferences

Concerning meta-heuristics, a very large number of them are applied to the HHC
problem. These methods can broadly divided into three groups: 1) single
solution methods such as Variable Neighborhood Search (VNS), Tabu Search (TS)
and Simulated Annealing (SA) [74, 1, 49, 98, 69]; 2) population-based methods
such as GA, particle swarm optimization (PSO) [2, 69] and 3) hybrid methods
such as [69, 23, 16, 19]. The first group is very good in exploitation, which
ensures the searching of optimal solutions within the given region while the
second group is known to be good in exploration, which allows the algorithm to
reach different promising regions of the search space. The third group try to
combine several methods to benefice from their advantages such as combining
exacts methods with heuristics or combine single solutions methods with
population-based methods to have both a good exploration and exploitation.

####  1.2.5 Positioning our contributions with respect to the state of art

We have summarized above the criteria and constraints considered in the HHCRSP
studies. These features are further detailed in the following literature
reviews [31, 56, 46]. In [81], the authors presented a review of the general
problem of resource constrained routing and scheduling, which has a wide range
of applications, such as: forest management, installations maintenance and
repairs, airport operations and home health care.

In addition, the HHCRSP extends the VRPTW to cover the additional constraints
related to HHC. Drexl et al. [39] reviewed the different type of
synchronization constraints in the VRP. Vidal et al. [103] presented a survey
of heuristics used in the literature for multi-attribute vehicle routing
problems. In the following, we focus on studies that have considered time
windows, multiple services, their synchronization if they are to be performed
simultaneously. Then, we propose three types of models: deterministic,
stochastic, and multi-objectives to address the HHCRSP.

#####  1.2.5.1 A deterministic version of the HHCRSP

Table 1.1:  Constraints and assumptions considered in home health care
problems.

Reference | App |  $\\#$ objs | Skills | TW | MTW | Syn | Horizon
---|---|---|---|---|---|---|---
Duque et al. [40] | LO | 2 | – | – | – | – | Long
Breakers et al. [19] | PA | 2 | ✓ | ✓ | – | – | Short
Fathollahi et al.[44] | PA | 2 | – | ✓ | – | – | Long
Liu et al. [70] | LA | 2 | – | ✓ | – | – | Short
Nickel et al. [80] | LA | 4 | ✓ | ✓ | – | – | Long
Trautsamwieser et al. [99] | LA | 7 | ✓ | ✓ | – | – | Short
Hiermann et al. [59] | LA | 13 | ✓ | ✓ | – | – | Short
Shi et al. [90] | LA | 2 | ✓ | ✓ | – | – | Short
Frifita et al. [49] | – | 1 | – | ✓ | – | ✓ | Short
Lin et al. [68] | LO | 5 | ✓ | ✓ | – | ✓ | Short
Decerle et al. [36] | LA | 2 | – | ✓ | – | ✓ | Short
Bredstrom et al. [23] | LA | 2 | – | ✓ | – | ✓ | Short
Redjem et al. [85] | LA | 2 | – | ✓ | – | ✓ | Short
Mankowska et al. [74] | LA | 3 | ✓ | ✓ | – | ✓ | Short
Rasmussen et al. [84] | LA | 3 | ✓ | ✓ | – | ✓ | Short
Afifi et al. [1] | LA | 3 | ✓ | ✓ | – | ✓ | Short
Parragh et al. [83] | LA | 2 | ✓ | ✓ | – | ✓ | Short
Hà et al. [57] | – | 1 | – | ✓ | – | ✓ | Short
Dohn et al. [38] | – | 1 | – | ✓ | – | ✓ | Short
Our model | LA | 2 | ✓ | ✓ | ✓ | ✓ | Short

  * •

Abbreviations: App (Approaches), LA (Linear aggregation), PA (Pareto based),
LO (Lexicographical order), "$\\#$ objs" is the number of objectives
considered. Columns: Skills, TW (time windows), MTW (multiple time windows)
and sync (synchronization of services) express if these constraints are
considered in studies (✓) or not(-).

Requested services must be provided within patients’ time windows to respect
their availability periods. The decision maker should respect as much as
possible these periods when scheduling patients’ visits. Two types of time
windows are considered in the literature: hard/fixed time windows [2, 5, 70,
85], or soft/flexible [59, 74, 80, 99]. In the first case, the decision maker
has to schedule the visit within the time window without any earliness or
tardiness of services. In the second case, time windows could not be
respected, and delays can be accepted with a penalty cost. Some services are
bound to specific times of the day (e.g. serving meals or medicine intakes)
and are considered as mandatory requests with hard/fixed time windows.
However, some services, such as cleaning or bathing, could be considered soft
or flexible services, thus allowing the patient to specify multiple time
windows in which he will be available to receive them. But, most studies in
HHC context, consider only a single time window per patient and it is
interesting to consider them as multiple defining all periods in which
patients will be available to receive care services [31].

Redjem et al. [85] conducted a survey of many French home care structures,
which showed that patients need several care services per day. Therefore, the
synchronization of services should be considered if a patient needs more than
a caregiver to provide one or multiple simultaneous services such as dressing,
bathing, getting out of bed and dosing medicine [84]. For example, an
overweight patient might need two people to lift her or him. Moreover, the
arrival of caregivers at different times will disrupt patients and increase
the time needed to provide requested services. However, starting at the same
time could provide the requested services within an optimal time, which is
obviously equal to the time devoted to process the longest of these services.
The synchronization becomes more complicated with the limited number of
caregivers. Starting time of visits cannot be independently scheduled from the
other routes [31], which increases the complexity of the problem.

For the deterministic version, we focus on studies dealing with multiple
services, their synchronization and multiple time windows. Table 1.1 shows
that only few studies that consider synchronization of services [85, 74, 84,
23, 37, 49, 68]. However, most of these studies consider the synchronization
only for double services. Redjem et al. [85] considered the synchronization
between multiple services, but patients are supposed to be assigned to
caregivers. Moreover, most studies assign to each patient a single time window
in which he would be available to receive care services.

In the first step, we consider the HHCRSP with multiple times windows. We
propose a new mathematical model as well as a GVNS based heuristic to solve
large instances. We show through a comparison the advantage of using multiple
time windows for patients then we generalize the model to deal with multiple
services and their synchronization if they are required to be simultaneous.

#####  1.2.5.2 A stochastic version of the HHCRSP

Several models and methods have been proposed in the literature to deal with
the HHCRSP but most of them are deterministic and generally less robust. The
predefined schedule should be adapted for any change in practical situations.
Otherwise, there will probably be delays in the services for patients who have
not yet been visited, which will cause their dissatisfaction. Travel and
service times are critical elements in the planning, any change could affect
the overall planning and service quality would be poor or even risky. The
uncertainty in travel times may be due to common factors such as varying road
conditions, driving skills and weather conditions [90]. However, the service
time is not always fixed as estimated due to practical reasons, such as
diagnosing time and parking situations [90].

Most previous efforts have been focused on studying the VRP with stochastic
parameters such as demands, travel and service times [66, 67, 95, 96, 72, 42,
75, 77]. But there are only a few works that have dealt with the HHCRSP with
stochastic parameters (e.g., [91, 90, 106, 8]) (see Table 1.2). These studies
only consider a single availability period as well as a single service
operation per patient and no study, as far as we know, has used multiple time
windows or multiple services for patients for the stochastic HHCRSP. In the
following we propose two SPR models to deal with the uncertainty in travel and
service times.

In the first SPR model, we assume that patients can request multiple services,
which involve assignment of several caregivers to perform these services. In
addition, if a patient requested simultaneous services, caregivers must start
at the same time, which involve the synchronization. It will be hard to
respect patients’ time windows, especially if simultaneously services are
requested. Therefore, the recourse is defined as penalty cost for patients’
delayed services and a remuneration for caregivers’ overtime.

In the second SPR model, we assume that time windows are hard/fixed, which
must be respected without any earliness or tardiness. To ensure that that
requested services are provided within patients’ time windows, the recourse is
fixed as skipping patients when their time windows will be violated. To
increase the chance of providing the maximum of services, patients are allowed
to specify multiple time windows.

Table 1.2:  Stochastic parameters considered in VRP and HHCRSP problems  Reference | Stochastic parameters | Problem
---|---|---
Laporte et al. [66] | Travel times | VRP
Li et al. [67] | Travel and service times | VRP
Taş et al. [95, 96] | Travel times | VRP
Errico et al.[42] | Service times | VRP
Marinaki et al.[75] | Demands | VRP
Luo et al.[72] | Demands | VRP
Mendoza et al.[77] | Demands | VRP
Yuan et al. [106] | Service times | HHCRSP
Shi et al.[91, 90] | Travel and service times | HHCRSP

#####  1.2.5.3 A multi-objective version of the HHCRSP

Most studies transform multi-objective problems into a mono-objective case
using aggregation techniques (see Table 1.1). Assigning weights to conflicting
objectives is a confusing task and requires the decision maker’ experience and
knowledge of the problem. In addition, a sensitivity analysis of weights
should be conducted, which makes the process of solving multi-objective
problems more complicated. Duque et al. [40] used a lexicographical order to
solve a bi-objective problem that aims to maximize the service level and to
minimize caregivers’ traveling distance. This approach is based on a priori
knowledge of some decision-maker preferences to establish the lexicographic
order, which is not a simple task.

Few studies [19, 37, 44] have dealt with the multi-objectives case in the HHC
context by using methods based on the concept of Pareto dominance to
approximate the Pareto front. Decerle et al. [37] proposed a memetic algorithm
for multi-objective optimization of the HHC problem, which is a hybridization
of NSGA-II with the multi-directional local search (MDLS) [101]. Three
objectives were proposed to be optimized, which are minimizing caregivers’
total working time , maximizing the quality of service and minimizing the
maximal working time difference among caregivers. Braekers et al. [19]
proposed a heuristic embedding a large neighborhood search heuristic in a MDLS
framework to solve a bi-objective problem. The two objectives considered are
the costs and clients’ inconvenience. Fathollahi et al. [44] worked on the bi-
objective HHCRSP considering patients’ satisfaction for a fuzzy environment.
Jimenez’s approach is used to deal with the fuzzy parameters in the objectives
and constraints. The authors implemented NSGA-II, social engineering optimizer
(SEO) and simulated annealing algorithms to solve the bi-objective HHCRSP.

As presented above, there is so far no work that has been proposed to solve
multi-objective problems in the HHC context using the MOEA/D algorithm. In
this work, we adopt the Pareto and decomposition based approaches to deal with
the multi-objective HHCRSP. According to [107], it is very time-consuming, if
not impossible, to obtain the entire Pareto front for most multi-objective
problems. In addition, the decision maker may not be interested in having all
Pareto optimal solutions. MOEA/D algorithm solves multi-objective problems
faster since ranking solutions based on Pareto dominance is not used. This
study deals with three objectives so NSGA-II algorithm remains efficient for
this kind of optimization problems. According to [102], efficiently combining
dominance and decomposition based approaches can result in high performance
many objective optimizers. MOEA/D, NSGA-II and the hybrid NSGA-II with MOEA/D
algorithms are used to approximate the Pareto front, in other words, find the
non dominated solutions set.

###  1.3 Conclusion

In this chapter, we have presented a review of the extensive literature
related to the VRP as well as the home health care routing and scheduling
problem.

The literature review shows that studies have been not considered the multiple
time windows for patients as well as most of them have dealt with the
synchronization only of double services. Most models proposed in studies are
deterministic and powerless to deal with the uncertainty that can arise any
time in parameters such as demand, travel and service times. In addition,
aggregation techniques are used by most of researchers when multi-objectives
need to be simultaneously optimized.

Finally, we presented our contributions in relation to the existing
literature. To give more flexibility to decision makers, we dealt with three
different problems from the optimization viewpoint: deterministic, stochastic,
and multi-objectives. The next three chapters of this thesis are devoted to
present our contributions.

##  Chapter 2 Deterministic home health care routing and scheduling problem

###  2.1 Introduction

In this chapter, we study the HHCRSP with particular interest in time windows,
skills requirement and synchronization constraints. As presented in the
previous chapter, the HHCRSP is subject to many variants and extensions. Among
the most frequently considered constraints are time window and synchronization
constraints.

In the literature, most studies assign a single time window for each patient
in which he is available to be visited. Some services are bound to specific
times of the day (e.g. serving meals or medicine intakes) and are considered
as mandatory requests with hard/fixed time windows. However, some services,
such as cleaning or bathing, could be considered soft or flexible services,
thus allowing the patient to specify multiple time windows in which he will be
available to receive them. But, most studies in HHC context, consider only a
single time window per patient and it is interesting to consider them as
multiple defining all periods in which patients will be available to receive
care services.

In addition, Redjem et al. [85] conducted a survey of many French home care
structures, which showed that patients need several care services per day.
Therefore, the synchronization of services should be considered if a patient
needs more than caregiver to provide one or multiple simultaneous services
such as dressing, bathing, getting out of bed and dosing medicine [84].

We propose a new mathematical model to simultaneously deal with multiple
services, their synchronization if they are required to be simultaneous,
multiple time windows per patient and skills requirements. Although exact
methods provide the optimal solution, the computation time increases
monotonically with the size of the problem. Due to the weakness of local
search methods that fall into a local optimum and cannot escape it, several
heuristics extending the local search methods have been proposed such as a
variable neighborhood search [79]. We apply the GVNS based heuristic to solve
large instances of the problem since its performance is proven on the HHCRSP
[74, 99, 90, 7]. Furthermore, the proposed solution coding takes into account
both caregivers‘ routes and their assignment. VNS is more suitable since
several neighborhood structures could be used to better explore the search
space.

In the first step, we consider the HHCRSP with multiple soft/flexible times
windows. We propose a new mathematical model as well as a GVNS based heuristic
to solve large instances. We aim to minimize earliness and tardiness of
providing services as well as to minimize caregivers’ waiting times. Then, we
show through a comparison the advantage of using multiple time windows for
patients.

In the second step, we generalize the model to deal with multiple services and
their synchronization if they are required to be simultaneous by considering
two new objective functions and hard/fixed time windows. A strategy to select
a time window for each patient and to ensure synchronization of simultaneous
services, is proposed and combined with GVNS based heuristic. This strategy is
mandatory since, for each patient, the selection of a time window could not be
done independently of his availability periods. In fact, since a single period
should be chosen to provide multiple services, this choice may be suitable for
one caregiver but not for another. GVNS generates solutions (caregivers’
routes and their assignment) while this strategy selects, for each patient, a
time window and ensures the synchronization of simultaneous services.

This chapter is organized as follows: The definition of the problems studied
are described in sections 2.2.1 and 2.3.1. In sections 2.2.2 and 2.3.2, the
problems are formulated as mixed integer linear programming models with a
description of the different parameters, variables and constraints taken into
account. Sections 2.2.3 and 2.3.3 describe the GVNS. The test instances, the
experimental settings and the performance of the GVNS are presented in
sections 2.2.4 and 2.3.4. Finally, the chapter ends with some remarks and
conclusions in section 2.4.

###  2.2 Home health care routing and scheduling problem with multiple soft
time windows

####  2.2.1 Problem statement

Given a set of patients $N=\\{1,2,\ldots,n\\}$ where $n$ is the number of
patients to visit on a day. They request services among S the set of services,
$S=\\{1,2,\ldots,q\\}$ where $q$ is the number of services that a HHC company
could provide. Each service $s$ requested by a patient $i$ has a service
duration $t_{is}$. Each patient $i$ possesses one or multiple time windows
$\\{[a_{il},b_{il}],l\in L=\\{1,2,\ldots,p\\}\\}$ in which he is available to
receive caregivers. Parameters $a_{il}$ and $b_{il}$ are respectively, the
earliest and latest service times of the availability period $l$ for the
patient $i$ and $p$ is the number of time windows in the day. However, only
one period should be selected to provide the patient with the requested
services. Travel times between patients $i$ and $j$ are denoted by $T_{ij}$.
Patients’ requested services are expressed by a matrix of binary parameters
$\delta_{is}$ where each patient is assumed requesting a single service
operation.

The set of available caregivers is denoted $K=\\{1,2,\cdots,c\\}$ with $c$ is
their total number; $S$ denotes also the set of different skills of
caregivers. Each caregiver has a duty length $[d_{k},e_{k}]$, where $d_{k}$
and $e_{k}$ are, respectively, the earliest and latest service times. All
caregivers start and finish their tours at the center of the HHC company,
which is represented by artificial nodes $0$ and $n+1$. They use the same mode
of transport and are not allowed to work overtime. Their skills are expressed
by a matrix of binary parameters $\Delta_{ks}$.

The goal is to define a daily schedule that minimizes caregivers’ waiting
times and respect as much as possible the selected time window for each
patient. Caregivers leaving the HHC center must return within their duty
length without exceeding the maximum of earliness and tardiness for providing
services as well as the maximum of the waiting time fixed by the decision
maker. Their assignment to patients must respect skills requirement.

The main hypotheses of this problem are:

  1. 1.

The HHC company provides a set of services;

  2. 2.

Caregivers start and finish tours at the HHC center. They use the same mode of
transportation and the overtime is not allowed;

  3. 3.

Each caregiver has a time window and a subset of skills;

  4. 4.

Processing times of service operations are known and cannot be preempted;

  5. 5.

Travel times between patients are known;

  6. 6.

Each patient has multiple time widows, but only one period will be selected;

  7. 7.

Each patient requests a single service;

  8. 8.

Caregivers depart as they are available from the HHC center, i.e. waiting at
HHC center is not allowed;

  9. 9.

Patients’ time windows are soft/flexible, it can be violated with a penalty
cost;

  10. 10.

Each service must be provided without exceeding the maximum of earliness and
tardiness;

  11. 11.

Each caregiver’s waiting time must not exceed the maximum value.

####  2.2.2 Mathematical formulation

In the following, we first present the notations used in the sequel and then
the proposed mathematical formulation for the HHCRSP with multiple time
windows.

#####  2.2.2.1 Sets

  * •

$N=\\{1,2,\ldots,n\\}$: set of patients;

  * •

$N^{0}=N\cup\\{0\\}$ and $N^{n+1}=N\cup\\{n+1\\}$: set of patients including
the HHC center, which is represented by artificial nodes $0$ and $n+1$;

  * •

$K=\\{1,2,\ldots,c\\}$: set of caregivers;

  * •

$L=\\{1,2,\ldots,p\\}$: set of patients’ time windows (availability periods).
Each patient $i$ has $p$ periods of availability: Actually, there are $L_{i}$
valid periods, the others (i.e. $p-L_{i}$) are null;

  * •

$S=\\{1,2,\ldots,q\\}$: set of services (skills).

#####  2.2.2.2 Parameters

  * •

$\alpha,\beta,\gamma$: the weights respectively, of total earliness and total
tardiness of service operations, and caregivers’ total waiting time where
$\alpha+\beta+\gamma=1$;

  * •

$M$: large number;

  * •

$[a_{il},b_{il}]$: the $l^{th}$ availability period of the patient i;

  * •

$[d_{k},e_{k}]$: caregivers’ time windows;

  * •

$T_{max}$: maximal tardiness of a service operation;

  * •

$E_{max}$: maximal earliness of a service operation;

  * •

$W_{max}$: maximal waiting time for each caregiver;

  * •

$T_{ij}$: travel time from the patient $i$ to the patient $j$;

  * •

$t_{is}$: processing time of the service operation $s$ at the patient $i\in
N$;

  * •

$\delta_{is}$:equals to 1 if a patient $i\in N$ requires service the operation
$s\in S$;

  * •

$\Delta_{ks}$:equals to 1 if the caregiver $k\in K$ is qualified to provide
the service operation $s\in S$.

#####  2.2.2.3 Decision variables

  * •

$x_{ijk}$: binary, 1 if the caregiver $k$ visits the patient $j$ after the
patient i, 0 otherwise;

  * •

$y_{iks}$: binary, 1 if the service operation $s$ is provided by the caregiver
k to the patient i, 0 otherwise;

  * •

$z_{il}$: binary, 1 if the $l^{th}$ availability period will be chosen for the
patient $i$, 0 otherwise;

  * •

$u_{i}$: earliness of a service operation at the patient $i$;

  * •

$v_{i}$: tardiness of a service operation at the patient $i$;

  * •

$A_{ik}$: arrival time of the caregiver $k$ to the patient $i$;

  * •

$S_{ik}$: start time of a service operation at the patient $i$ provided by the
caregiver $k$;

  * •

$W_{k}$: total waiting time of the caregiver $k$.

#####  2.2.2.4 Mathematical model

The MILP formulation of the problem statement, is an extension of VRPTW [92]
adapted and augmented by constraints that are specific to the HHC context, is
defined as follows:

$\displaystyle\min\quad Z=\sum_{i=1}^{n}(\alpha u_{i}+\beta
v_{i})+\sum_{k=1}^{c}\gamma(S_{ik}-A_{ik})$

s.t.

$\displaystyle\sum_{i=0}^{n}\sum_{k=1}^{c}x_{ijk}=1$ $\displaystyle\forall
j\in N$ (2.1)

$\displaystyle\sum_{j=1}^{n+1}\sum_{k=1}^{c}x_{ijk}=1$ $\displaystyle\forall
i\in N$ (2.2)

$\displaystyle\sum_{i=0}^{n}x_{i(n+1)k}=1$ $\displaystyle\forall k\in K$ (2.3)

$\displaystyle\sum_{j=1}^{n+1}x_{0jk}=1$ $\displaystyle\forall k\in K$ (2.4)

$\displaystyle\sum_{i=0}^{n}x_{imk}=\sum_{j=1}^{n+1}x_{mjk}$
$\displaystyle\forall m\in N,k\in K$ (2.5)

$\displaystyle S_{ik}+\sum_{s=1}^{q}t_{is}y_{iks}+T_{ij}\leq
S_{jk}+(1-x_{ijk})M$ $\displaystyle\forall i\in N^{0},j\in N^{n+1},k\in K$
(2.6)

$\displaystyle S_{ik}+\sum_{s=1}^{q}t_{is}y_{iks}+T_{ij}\leq
A_{jk}+(1-x_{ijk})M$ $\displaystyle\forall i\in N^{0},j\in N^{n+1},k\in K$
(2.7)

$\displaystyle S_{ik}+\sum_{s=1}^{q}t_{is}y_{iks}+T_{ij}\geq
A_{jk}+(x_{ijk}-1)M$ $\displaystyle\forall i\in N^{0},j\in N^{n+1},k\in K$
(2.8)

$\displaystyle A_{ik}\leq\sum_{s=1}^{q}y_{iks}M$ $\displaystyle\forall i\in
N,k\in K$ (2.9)

$\displaystyle S_{ik}\leq\sum_{s=1}^{q}y_{iks}M$ $\displaystyle\forall i\in
N,k\in K$ (2.10)

$\displaystyle\sum_{j=1}^{n+1}x_{ijk}=\sum_{s=1}^{q}y_{iks}$
$\displaystyle\forall i\in N,k\in K$ (2.11)

$\displaystyle y_{iks}\leq\delta_{is}\Delta_{ks}$ $\displaystyle\forall i\in
N,s\in S,k\in K$ (2.12)

$\displaystyle S_{0k}=d_{k}$ $\displaystyle\forall k\in K$ (2.13)

$\displaystyle A_{(n+1)k}\leq e_{k}$ $\displaystyle\forall k\in K$ (2.14)

$\displaystyle(\sum_{l=1}^{p}z_{il}+\sum_{s=1}^{q}y_{iks}-2)M+\sum_{l=1}^{p}a_{il}z_{il}-u_{i}\leq
S_{ik}$ $\displaystyle\forall i\in N,k\in K$ (2.15)

$\displaystyle
S_{ik}+\sum_{s=1}^{q}t_{is}y_{iks}\leq\sum_{l=1}^{p}b_{il}z_{il}+v_{i}+(2-\sum_{l=1}^{p}z_{il}-\sum_{s=1}^{q}y_{iks})M$
$\displaystyle\forall i\in N,k\in K$ (2.16)

$\displaystyle\sum_{l=1}^{p}z_{il}=1$ $\displaystyle\forall i\in N$ (2.17)

$\displaystyle u_{i}\leq E_{max}$ $\displaystyle\forall i\in N$ (2.18)

$\displaystyle v_{i}\leq T_{max}$ $\displaystyle\forall i\in N$ (2.19)

$\displaystyle W_{k}=\sum_{i=1}^{n}(S_{ik}-A_{ik})$ $\displaystyle\forall k\in
K$ (2.20)

$\displaystyle W_{k}\leq W_{max}$ $\displaystyle\forall k\in K$ (2.21)

$\displaystyle x_{iik}=0$ $\displaystyle\forall i\in N,k\in K$ (2.22)

$\displaystyle S_{ik}\geq 0$ $\displaystyle\forall i\in N,k\in K$ (2.23)

$\displaystyle A_{ik}\geq 0$ $\displaystyle\forall i\in N,k\in K$ (2.24)

$\displaystyle u_{i}\geq 0$ $\displaystyle\forall i\in N$ (2.25)

$\displaystyle v_{i}\geq 0$ $\displaystyle\forall i\in N$ (2.26)

$\displaystyle x_{ijk}\in\\{0,1\\}$ $\displaystyle\forall i\in N,j\in N,k\in
K$ (2.27)

$\displaystyle y_{iks}\in\\{0,1\\}$ $\displaystyle\forall i\in N,k\in K,s\in
S$ (2.28)

$\displaystyle z_{il}\in\\{0,1\\}$ $\displaystyle\forall i\in N,l\in L$ (2.29)

The objective function aims to minimize the total penalized earliness and
tardiness of services operations as well as caregivers’ total waiting times.
Constraints (2.1) and (2.2) state that each patient will be visited exactly by
one caregiver. Constraints (2.3) and (2.4) state that each caregiver who has
left the center to visit assigned patients must return to that center.
Constraints (2.5) express the flux conservation. Constraints (2.6) determine
the service operations’ starting time of the patient $j$ with respect to
service operations’ completion time of the patient $i$. These constraints
enforce that the starting time of services along the route of a caregiver are
strictly increasing. In doing so, they also eliminate sub-tours because a
return to an already visited patient would violate the start time of the
previous visit [74]. Constraints (2.7) and (2.8) define the arrival time of a
caregiver $k$ to the patient $j$. Constraints (2.9) and (2.10) initialize the
waiting and starting times to zero if the caregiver $k$ will not be affected
to the patient $i$. Constraints (2.11) define the variable $y_{iks}$.
Constraints (2.12) ensure that a qualified caregiver $k$ performs a requested
service operation $s$ to patient $i$. Constraints (2.13) and (2.14) enforce
the respecting of caregivers’ time windows. Constraints (2.15) and (2.16)
ensure the respecting of patients’ time windows. Constraints (2.17) guarantee
that only one period is selected from patient’s time windows. Constraints
(2.18) and (2.19) guarantee not to exceed the maximal earliness and tardiness
of a service operation. Constraints (2.20) define the total waiting time for
each caregiver. Constraints (2.21) ensure not to exceed the maximal waiting
time for each caregiver. Constraints (2.22 to 2.29) set the domains of the
decision variables.

####  2.2.3 Variable neighborhood search

The drawback of local search strategies is known as falling into a local
optimum with a poor value. Several heuristics, extend and improve the local
search strategies, have been proposed to avoid being trapped in a local optima
such as TS [53], SA [64] and VNS [79]. VNS is based on the idea of systematic
changes of neighborhoods in the search to find a better solution. When an
initial solution is defined, theVNS proceeds by a descent method exploring the
predefined neighborhoods of a solution to find a local minimum. Each time the
descent method is trapped in a local optimum, the shaking phase is randomly
applied to generate a new solution and start over the search. Many versions
ofVNS are used in the literature such as: 1) variable neighborhood descent
(VND) is a deterministic version of VNS, the defined neighborhoods are applied
to the initial solution in a predefined order, the searching restart from the
first neighborhood when a new local minimum is found. 2) reduced variable
neighborhood search is a pure stochastic search method where only the shaking
phase is applied to solutions; 3) GVNS is aVNS where the local descend method
is replaced by the VND.

#####  2.2.3.1 Encoding

A solution will be represented by a matrix where the number of columns equals
to the number of patients $n$. Two lines are used, the first one will contain
patients and requested services operations (included in parenthesis), and the
second will contain assigned caregivers.

Example: we assume that we have 6 patients and 2 caregivers skilled to provide
3 types of services operations. A solution will be encoded as described in
Table 2.1.

Table 2.1: Example of solution encoding Patients | 1 (3) | 3 (1) | 4 (3) | 2 (1) | 6  (2) | 5 (2)
---|---|---|---|---|---|---
Caregivers | 1 | 2 | 2 | 1 | 2 | 1

The caregiver 1 will visit patients 1, 2 and 5 to provide respectively the
services 3, 1 and 2.

#####  2.2.3.2 Decoding

1

2

3if  _$(\alpha\leq\gamma)$_ then

4

5 if  _$(ET_{il}\leq E_{max})$_ then

6 set $u_{i}\longleftarrow ET_{il}$ ;

7

8 else if  _$(W_{k}+ET_{il}-E_{max}\leq W_{max})$_ then

9 set $u_{i}\longleftarrow E_{max}$ and $W_{k}\longleftarrow
W_{k}+ET_{il}-E_{max}$ ;

10

11 else

12 the availability period $l$ is infeasible

13 end if

14

15else

16 if  _$(ET_{il}+W_{k}\leq W_{max})$_ then

17

18 set $W_{k}\longleftarrow W_{k}+ET_{il}$ ;

19

20 else if  _$(W_{k}+ET_{il}-W_{max}\leq E_{max})$_ then

21 set $u_{i}\longleftarrow W_{k}+ET_{il}-W_{max}$ and $W_{k}\longleftarrow
W_{max}$ ;

22

23 else

24 the availability period $l$ is infeasible

25 end if

26

27 end if

28

29

Algorithm 1 Caregivers’ arriving early to patients

Given a solution encoded as proposed above. For each sub set of patients
assigned to a caregiver, the starting, the arrival and the waiting times will
be calculated iteratively in the same order as they appear at the matrix. For
each patient $i$, the period $l\in L$ , constraints (1) to (31) are taken into
account, that minimize the waiting time, the earliness and the tardiness of
the service operation is selected (see equation 2.30).

$\operatorname*{arg\,min}_{l\in L}\\{\alpha u_{i}+\beta
v_{i}+\gamma(S_{ik}-A_{ik})\;|\;s.t.\;Constraints\;(1)\;to\;(31)\\}$ (2.30)

For each period $l\in L$, three possible cases of caregivers’ arrival times
are to distinguish:

  1. 1.

The caregiver arrives to a patient and finish providing requested service
operation within the availability period:

$u_{i}=0,\quad v_{i}=0\quad and\quad S_{ik}-A_{ik}=0$

  2. 2.

The caregiver arrives to a patient within the availability period and finish
providing requested service operation with a tardiness time:

$u_{i}=0,\quad v_{i}=A_{ik}+t_{is}-b_{il}\quad and\quad S_{ik}-A_{ik}=0$

  3. 3.

The caregiver arrives to a patient before the availability period . In this
case, many possibilities arise to calculate the waiting time and the earliness
of the service operation. This problem could be formulated as a MIP problem to
determine the optimal combination. However, the algorithm 1 is used. The early
time of the caregiver $k$ at patient $i$ for the availability period $l$
($ET_{il}$) is defined by the following formula: $ET_{il}=A_{ik}-a_{il}$.

#####  2.2.3.3 Neighborhoods

The neighborhood of a solution is defined as a transformation function applied
to this solution to get a set of solutions where one can move some amount in
any direction away from that solution without leaving the set. Four
neighborhoods structure are proposed, two neighborhoods are used to intensify
patients’ assignment to caregivers (switch and inter-swap) and the two others
are used to intensify the order visiting (intra-shift and intra-swap).

  1. 1.

Switch (i.e. Patients’ reassignment to caregivers): the neighborhood of a
solution is defined as a reassignment of another caregiver $k$ to a patient
$i$. The size of possible neighborhoods will be less than $n(c-1)$ depending
on caregivers’ qualifications. The equality could be hold if all caregivers
are skilled to provide all services operations ( see Fig. 2.1);

  2. 2.

Inter-swap: this neighborhood aims to change patients’ assignment to
caregivers. Given two patients, caregivers’ assignment are swapped. The size
of possible neighborhoods equals to $\frac{(n-1)\times n}{2}$ ( see Fig. 2.2);

  3. 3.

Intra-shift: given a visiting order, the neighborhood is defined as shifting
of a patient to another position. The size of possible neighborhoods equals to
$(n-1)\times n$ ( see Fig. 2.3);

  4. 4.

Intra-swap: given a visiting order, the neighborhood is defined as two
patients’ position exchanging. The size of possible neighborhoods equals to
$\frac{(n-1)\times n}{2}$ (see Fig. 2.4).

#####  2.2.3.4 Shaking

The shaking phase is the mechanism that allows to escape the local optima with
a poor value [79]. It consists of applying a series of moves to a solution to
jump from a local optimum to a new solution, then restart improving the new
solution using local search methods. The four proposed neighborhoods are used
for the shaking phase ($k_{max}$ = 4) as operators, which will be randomly
applied $m_{1}$ times whenever the local search method is trapped in a local
optimum.

Original solution :  Patients 1 (3) 3 (1) 4 (3) 2 (1) 6 (2) 5 (2) Caregivers 1
2 2 1 2 1 Neighbor solution :  Patients 1 (3) 3 (1) 4 (3) 2 (1) 6 (2) 5 (2)
Caregivers 2 2 2 1 2 1 Figure 2.1: Example of switch neighborhood moves
Original solution :  Patients 1 (3) 3 (1) 4 (3) 2 (1) 6 (2) 5 (2) Caregivers 1
2 2 1 2 1 Neighbor solution :  Patients 1 (3) 3 (1) 4 (3) 2 (1) 6 (2) 5 (2)
Caregivers 2 2 2 1 1 1 Figure 2.2: Example of inter-swap neighborhood moves
Original solution :  Patients 1 (3) 3 (1) 4 (3) 2 (1) 6 (2) 5 (2) Caregivers 1
2 2 1 2 1 Neighbor solution :  Patients 3 (1) 4 (3) 2 (1) 1 (3) 6 (2) 5 (2)
Caregivers 2 2 1 1 2 1 Figure 2.3: Example of intra-shift neighborhood moves
Original solution :  Patients 1 (3) 3 (1) 4 (3) 2 (1) 6 (2) 5 (2) Caregivers 1
2 2 1 2 1 Neighbor solution :  Patients 6 (2) 3 (1) 4 (3) 2 (1) 1 (3) 5 (2)
Caregivers 2 2 2 1 1 1 Figure 2.4: Example of intra-swap neighborhood moves

#####  2.2.3.5 Local search methods

Whenever shaking phase is applied, local search methods are called to improve
the new generated solution until they fall in a local optimum. The four
proposed neighborhoods are used as local search methods, each one (intra-swap,
intra-shift, inter-swap, and switch) is applied to a solution to explore the
search space until it falls in a local optimum. Local search methods adopt two
types of algorithm while exploring neighborhoods: i) The first improvement is
to start over the search whenever a neighbor that improves the best-known
solution is found; ii) The best improvement is to start over the search when
all neighbors are explored and the best one is selected [93]. The the best
improvement algorithm is adopted.

#####  2.2.3.6 Initial solution

The initial solution is generated randomly as follow:

  1. 1.

Patients are sorted by increasing end of their time windows for single period.
for multiple periods the visiting order is generated randomly (see Table 2.2);

Table 2.2: Example of visiting order Patients | 1 (3) | 3 (1) | 4 (3) | 2 (1) | 6 (2) | 5 (2)
---|---|---|---|---|---|---
Caregivers |  |  |  |  |  |
  2. 2.

For each patient, assign a qualified caregiver selected randomly (see Table
2.3);

Table 2.3: example of caregivers’ assignment to patients Patients | 1 (3) | 3 (1) | 4 (3) | 2 (1) | 6 (2) | 5 (2)
---|---|---|---|---|---|---
Caregivers | 1 | 2 | 2 | 1 | 2 | 1
  3. 3.

Calculate caregivers’ waiting times, the earliness and tardiness of services
operations using the decoding method proposed above;

  4. 4.

If the solution is infeasible repeat steps 1,2 and 3. Otherwise, go to the
step 5;

  5. 5.

Calculate the objective function value.

#####  2.2.3.7 GVNS algorithm

1

2Initialization: ;

3 \- Set $K_{max}=4$ and $l_{max}=4$ ;

4 \- Generate an initial solution $x$ ;

5 while  _(the stopping condition is not reached)_ do

6 for  _$k\leftarrow 1$ to $k_{max}$_ do

7

8 Set $x^{\prime}\longleftarrow$ Shaking ($x$, neighborhoodk, $m_{2}$) ;

9 for  _$l\leftarrow 1$ to $l_{max}$_ do

10

11 Set $x^{\prime\prime}\longleftarrow$ Local search ($x^{\prime}$,
neighborhoodl) ;

12 if  _$f(x^{\prime\prime}) <f(x^{\prime})$_ then

13 Set $x^{\prime}\longleftarrow x^{\prime\prime}$ ;

14 Set $l\longleftarrow 1$ ;

15

16 else

17 Set $l\longleftarrow l+1$ ;

18

19 end if

20

21 end for

22 if  _$f(x^{\prime}) <f(x)$_ then

23 Set $x\longleftarrow x^{\prime}$ ;

24 Set $k\longleftarrow 1$ ;

25

26 else

27 Set $k\longleftarrow k+1$ ;

28

29 end if

30

31 end for

32

33 end while

Algorithm 2 GVNS algorithm

GVNS algorithm is executed until there is no improvement over the best-known
solution for $m_{1}$ iterations. Therefore, the counter is set to zero if a
better new solution is found. Line 6 generates a new solution
$x\textquoteright$ by randomly applying $m_{2}$ times the neighborhood $k$ to
the solution $x$. Lines 7-15 describe VND algorithm, which is applied to each
solution $x^{\prime}$ generated in the shaking phase. Line 8 improves solution
$x\textquoteright$ using neighborhood $l$ as a local search method and stores
it in $x^{\prime\prime}$. At each time, if the solution $x$ (resp.
$x^{\prime}$) is improved, the $k$ (resp. $l$) is initialized to 1 (see
Algorithm 2).

####  2.2.4 Numerical experiments

The experiments run on the computer with Intel i7-7600U 2.80-GHz CPU and 16 GB
of RAM under windows 10. The MIP model is implemented and tested using CPLEX
IBM version 12.8. The metaheuristic based on GVNS is coded and tested using
the language C++.

#####  2.2.4.1 Test instances

Tests instances have been generated randomly using the benchmark instances
from Mankowska et al. [74]. Patients and the HHC office are placed at random
locations in the area of $100\times 100$ distance units. Travel times $T_{ij}$
are equal to the Euclidean distance between patients truncated to integer.
Processing times of services operations $t_{is}$ are randomly chosen from the
interval $[10,20]$. Six types of services $S=\\{1,...,6\\}$ are considered.
Caregivers are grouped into two subsets with different skills. Each caregiver
of the first group is qualified for providing at most three services, which
are randomly selected from the subset $\\{1,2,3\\}$ of S. Accordingly, each
caregiver of the second group is qualified for providing at most three
services from subset $\\{4,5,6\\}$. Each patient requires a single service,
which is randomly drawn from $S=\\{1,…,6\\}$. The time windows are of length
120 min (2 h) and are randomly placed within a daily planning period of 10
hours. Regarding instances which contains two availability periods, the first
period will be placed in the first 5 hours, and the second period will be
placed in the interval [5, 10]. No special preference for the three sub-goals
and, therefore, weights are set to $\alpha=\beta=\gamma=1/3$. The maximum
earliness and the maximum tardiness of service operations are set respectively
to 0min and 15min, the maximum waiting time is set to 90min. 8 instances are
generated, each one is used with 1-period and with 2-periods availability of
patients. The instance Int1_1 refers to the instance 1 with one availability
period and the instance Int1_2 refers to the instance 1 with two availability
periods. A series of tests was executed to find the best tuning parameters for
the proposed metaheuristic.

#####  2.2.4.2 Computational results

Instances are generated as described above and solved. Instances with two
availability periods are generated feasible in the first time. However,
instances with single time windows need many regenerations to get a feasible
solution. Table 2.4 summarizes the results of CPLEX and GVNS according to the
sizes and patients’ availability periods of test instances. $LB$ is the lower
bound of the model given by the CPLEX solver, $Z$ is the objective function
value, $GAP$ is calculated as $100\%\times$ (Z – lower bound)/Z and $CPU$ is
the computing time elapsed of solved instances. For the GVNS algorithm, each
instance has been executed 10 times and the best, the worst and the average
solutions are considered. $GAP$ is calculated as $100\%\times$ (Average –
lower bound)/Average. $CPU$ computing time corresponds to the sum of time
elapsed to solve each instance, which is running 10 times. Optimal solutions
reached are in boldface.

All instances are solved, using CPLEX IBM, to optimality except instances
Int7_2 and Int8_2. Instances Int6_2, Inst7_2 and Int8_2 are hard to solve
compared to others instances. The instance Int6_2 required 47530s to be
solved, the instance Int7_2 and Int8_2 was executed for 18 hours and CPLEX
could not find respectively the optimal solution and a feasible solution,
which shows the limit of the exact method used considering the problem is NP-
hard. The proposed metaheuristic (GVNS), was able to find a good solution in a
very short computational time, solution in bold are proven optimal( see Table
2.4). The proposed GVNS could find optimal solutions at least one time of the
10 executions for 11 instances. Due to the LB that equals zero, the gap of the
instances Int4_2, Int5_2, Int7_2 and Int8_2 is 100%. Because when LB
approaches zero, the gap tends to 100%.

Int_1Int_2Int_3Int_4Int_5Int_6Int_7Int_8$0$$10$$20$$30$$40$$50$InstancesObjective function valuesSingle TWDouble TW Figure 2.5: Objective function values according to the number of time windows (TW) Table 2.4: Numerical results of tested instances Instances | CPLEX | GVNS
---|---|---
| N | K | L | LB | Z | CPU | Best | Worst | Average | Gap | CPU
Int1_1 | 7 | 2 | 1 | 11 | 11 | 1.58 | 11 | 11 | 11 | 0 % | $<1$
Int2_1 | 10 | 3 | 1 | 31.33 | 31.33 | 1.90 | 31.33 | 31.36 | 31.53 | 1 % | $<1$
Int3_1 | 14 | 4 | 1 | 24 | 24 | 2.52 | 24 | 35.33 | 27.76 | 13 % | 1.79
Int4_1 | 20 | 5 | 1 | 7 | 7 | 3.02 | 7 | 9.33 | 7.43 | 6 % | 8.82
Int5_1 | 25 | 6 | 1 | 45 | 45 | 5.16 | 59.86 | 84 | 65.1 | 30 % | 25
Int6_1 | 30 | 6 | 1 | 34.6 | 34.6 | 12.13 | 35.3 | 44.6 | 39.13 | 17 % | 25
Int7_1 | 40 | 8 | 1 | 54 | 54 | 255 | 72 | 100 | 78 | 30 % | 111
Int8_1 | 50 | 10 | 1 | 7.66 | 7.66 | 381 | 11 | 18.66 | 13.73 | 44 % | 210
Int1_2 | 7 | 2 | 2 | 11.33 | 11.33 | 1.73 | 11.33 | 11.33 | 11.33 | 0 % | $<1$
Int2_2 | 10 | 3 | 2 | 5.33 | 5.33 | 1.91 | 5.33 | 6.33 | 5.43 | 2 % | $<1$
Int3_2 | 14 | 4 | 2 | 2.66 | 2.66 | 2.60 | 2.66 | 4 | 3.16 | 16 % | 1.74
Int4_2 | 20 | 5 | 2 | 0 | 0 | 16.31 | 0 | 9 | 2.7 | 100 % | 9.77
Int5_2 | 25 | 6 | 2 | 0 | 0 | 61 | 0 | 6.33 | 4.366 | 100 % | 32
Int6_2 | 30 | 6 | 2 | 35.3 | 35.3 | 47530 | 35.3 | 44.66 | 41.96 | 15 % | 52.64
Int7_2 | 40 | 8 | 2 | 0 | 2.33 | 64800 | 5.66 | 13.66 | 7.86 | 100 % | 248
Int8_2 | 50 | 10 | 2 | 0 | - | 64800 | 0 | 1.33 | 0.23 | 100 % | 561

The objective function values of instances with two availability periods are
less than those with single period, except the first and the sixth instances,
their values are very close (see Fig. 2.5). Therefore, patients will be more
satisfied seeing that the earliness and tardiness of service operations are
minimized. On the other hand, the waiting time is also minimized which will
increase the productive time of caregivers since the waiting time is
considered as unproductive time.

The soft/flexible time windows would increase the chance of finding a feasible
solution since delays are accepted with a penalty cost. However, patients will
be less satisfied because their availability periods are not respected.
Furthermore, Patients needs several care activities per day and some of them
are simultaneous by their nature. In the next section, we extend and adapt the
model to deal with multiple hard/fixed time windows for patients and multiple
synchronized services as well as to balance caregivers’ workload.

###  2.3 Home health care routing and scheduling problem with multiple hard
time windows and multiple synchronized services

####  2.3.1 Problem statement

We modify the problem statement defined the previous section 2.2.1 to allow
patients to request multiple services, which can be provided as independent or
simultaneous services. Also, we suppose that patients’ time windows are
hard/fixed and we consider two new objective functions.

In this problem, we aim to minimize waiting time and balance caregivers’
workload. The waiting time ($f_{1}$) is considered to be unproductive [85] and
the caregivers are supposed to be paid for their regular working time
regardless of the amount of care they provide [19]. On the other hand, to
ensure fairness among caregivers, their workload must be balanced ($f_{2}$).
To achieve this goal, we consider the minimization of the sum of absolute
difference between each caregiver’ working time and the average working time
of all caregivers. The total caregivers’ working times is equal to the sum of
service and travel times.

Most studies consider the workload as the difference between the extreme
values of working times. However, any change between the extremes has no
effect on the value of workload [76]. In this study, the Mean Absolute
Deviation (MAD) is used in our model to take into account all values but it is
sensible to extreme values. To overcome this issue, caregivers’ time windows
are considered and the overtime time is not allowed, which ensures caregivers’
working times do not exceed the duty length.

The goal is to define a daily schedule that minimizes waiting times for
caregivers and balances their workload. Each patient should be visited within
a time window selected from his availability periods. Services that need to be
provided simultaneously should be synchronized, but if it is not necessary
they would be performed independently. Caregivers leaving the HHC center must
return within their duty length and their assignment must respect skills
requirement.

The main hypotheses of this problem are:

  1. 1.

The first 6 hypotheses defined in 2.2.1;

  2. 2.

Each patient can request one or more services, which should be synchronized if
they are required to be simultaneous;

  3. 3.

Each requested service must be performed by one and only one caregiver. In
others words, providing the same service for the same patient by several
caregivers is not allowed;

  4. 4.

Each caregiver must provide one and only one service. In others word, a
caregiver $k$ is not allowed to carry out several services for the same
patient;

  5. 5.

Caregivers’ departure are independent and each caregiver leaves as soon as he
finished.

####  2.3.2 Mathematical formulation

In the following, we first present the new notations, those not defined are
the same from the previous section, used in the sequel and then the proposed
mathematical formulation for the HHCRSP-MTW-MSS.

#####  2.3.2.1 Parameters

  * •

$\lambda_{i}$: equals 1 if requested service operations by patient $i$ require
to be simultaneous, and 0 otherwise.

#####  2.3.2.2 Decision variables

  * •

$u_{ik}$: equals 1 if the arrival time of the caregiver $k$ is used as the
starting time for the patient $i$, 0 otherwise;

  * •

$v_{ik}$: equals 1 if the starting time $S_{ik}$ is greater than the arrival
time $A_{ik}$ of the caregiver k in the case of independent services or if the
synchronized starting time $SS_{i}$ is greater than the maximum of arrival
times of the caregivers at patient $i$ in the case of simultaneous services; 0
otherwise;

  * •

$D_{k}$: absolute value of the difference between the working time of each
caregiver $w_{k}$ and the average working time.

#####  2.3.2.3 Mathematical model

The mathematical model proposed to deal with the new hypotheses is adapted
from the previous formulation 2.2.2.4 to cover additional assumptions, such as
multiple services and their synchronization if they have to be simultaneous,
minimizing caregivers’ waiting times and balancing their workload. The
mathematical formulation of the new model is defined as follows:

$\displaystyle\min
Z=\alpha\sum_{k=1}^{c}\sum_{i=0}^{n}(S_{ik}-A_{ik})+\beta\sum_{k=1}^{c}D_{k}$

s.t.

$\displaystyle\sum_{i=0}^{n}\sum_{k=1}^{c}x_{ijk}=\sum_{s=1}^{q}\delta_{js}$
$\displaystyle\forall j\in N$ (2.31)

$\displaystyle\sum_{j=1}^{n+1}\sum_{k=1}^{c}x_{ijk}=\sum_{s=1}^{q}\delta_{is}$
$\displaystyle\forall i\in N$ (2.32)

$\displaystyle\sum_{i=0}^{n}x_{i(n+1)k}=1$ $\displaystyle\forall k\in K$
(2.33)

$\displaystyle\sum_{j=1}^{n+1}x_{0jk}=1$ $\displaystyle\forall k\in K$ (2.34)

$\displaystyle\sum_{i=0}^{n}x_{imk}=\sum_{j=1}^{n+1}x_{mjk}$
$\displaystyle\forall m\in N,k\in K$ (2.35)

$\displaystyle S_{ik}+\sum_{s=1}^{q}t_{is}y_{iks}+T_{ij}\leq
S_{jk}+(1-x_{ijk})M$ $\displaystyle\forall i\in N^{0},j\in N^{n+1},k\in K$
(2.36)

$\displaystyle S_{ik}+\sum_{s=1}^{q}t_{is}y_{iks}+T_{ij}\leq
A_{jk}+(1-x_{ijk})M$ $\displaystyle\forall i\in N^{0},j\in N^{n+1},k\in K$
(2.37)

$\displaystyle S_{ik}+\sum_{s=1}^{q}t_{is}y_{iks}+T_{ij}\geq
A_{jk}+(x_{ijk}-1)M$ $\displaystyle\forall i\in N^{0},j\in N^{n+1},k\in K$
(2.38)

$\displaystyle A_{ik}\leq\sum_{s=1}^{q}y_{iks}M$ $\displaystyle\forall i\in
N,k\in K$ (2.39)

$\displaystyle S_{ik}\leq\sum_{s=1}^{q}y_{iks}M$ $\displaystyle\forall i\in
N,k\in K$ (2.40)

$\displaystyle\sum_{j=1}^{n+1}x_{ijk}=\sum_{s=1}^{q}y_{iks}$
$\displaystyle\forall i\in N,k\in K$ (2.41)

$\displaystyle y_{iks}\leq\delta_{is}\Delta_{ks}$ $\displaystyle\forall i\in
N,s\in S,k\in K$ (2.42)

$\displaystyle\sum_{s=1}^{q}y_{iks}\leq 1$ $\displaystyle\forall i\in N,k\in
K$ (2.43)

$\displaystyle\sum_{k=1}^{c}y_{iks}\leq 1$ $\displaystyle\forall i\in N,s\in
S$ (2.44)

$\displaystyle d_{k}=A_{0k}$ $\displaystyle\forall k\in K$ (2.45)

$\displaystyle A_{(n+1)k}\leq e_{k}$ $\displaystyle\forall k\in K$ (2.46)

$\displaystyle(\sum_{l=1}^{p}z_{il}+\sum_{s=1}^{q}y_{iks}-2)M+\sum_{l=1}^{p}a_{il}z_{il}\leq
S_{ik}$ $\displaystyle\forall i\in N,k\in K$ (2.47)

$\displaystyle
S_{ik}+\sum_{s=1}^{q}t_{is}y_{iks}\leq\sum_{l=1}^{p}b_{il}z_{il}+(2-\sum_{l=1}^{p}z_{il}-\sum_{s=1}^{q}y_{iks})M$
$\displaystyle\forall i\in N,k\in K$ (2.48)

$\displaystyle\sum_{l=1}^{p}z_{il}=1$ $\displaystyle\forall i\in N$ (2.49)

$\displaystyle\sum_{k^{\prime}=1}^{c}S_{ik^{\prime}}-\sum_{s=1}^{q}\delta_{is}S_{ik}\leq(1-\lambda_{i}\sum_{s=1}^{q}y_{iks})M$
$\displaystyle\forall i\in N,k\in K$ (2.50)
$\displaystyle\sum_{k^{\prime}=1}^{c}S_{ik^{\prime}}-\sum_{s=1}^{q}\delta_{is}S_{ik}\geq(\lambda_{i}\sum_{s=1}^{q}y_{iks}-1)M$
$\displaystyle\forall i\in N,k\in K$ (2.51)

$\displaystyle
w_{k}=\sum_{i=1}^{n}\sum_{s=1}^{q}t_{is}y_{iks}+\sum_{i=0}^{n}\sum_{j=1}^{n+1}T_{ij}x_{ijk}$
$\displaystyle\forall k\in K$ (2.52)

$\displaystyle D_{k}\geq w_{k}-\frac{\sum_{k=1}^{c}{w_{k}}}{c}$
$\displaystyle\forall\ k\in K$ (2.53)

$\displaystyle D_{k}\geq\frac{\sum_{k=1}^{c}{w_{k}}}{c}-w_{k}$
$\displaystyle\forall k\in K$ (2.54)

$\displaystyle\sum_{k^{\prime}=1}^{c}S_{ik^{\prime}}\leq\sum_{s=1}^{q}\delta_{is}A_{ik}+(1-\lambda_{i}u_{ik})M$
$\displaystyle\forall i\in N,k\in K$ (2.55)

$\displaystyle\sum_{k=1}^{c}S_{ik}\leq\sum_{s=1}^{q}\delta_{is}\sum_{l=1}^{p}a_{il}z_{il}+(1-\lambda_{i}\sum_{k=1}^{c}v_{ik})M$
$\displaystyle\forall i\in N$ (2.56)

$\displaystyle\sum_{k=1}^{c}(u_{ik}+v_{ik})\leq 1+(1-\lambda_{i})M$
$\displaystyle\forall i\in N$ (2.57)

$\displaystyle\sum_{k=1}^{c}(u_{ik}+v_{ik})\geq 1+(\lambda_{i}-1)M$
$\displaystyle\forall i\in N$ (2.58)

$\displaystyle S_{ik}\leq A_{ik}+(1+\lambda_{i}-u_{ik})M$
$\displaystyle\forall i\in N,k\in K$ (2.59)

$\displaystyle S_{ik}\leq\sum_{l=1}^{p}a_{il}z_{il}+(1+\lambda_{i}-v_{ik})M$
$\displaystyle\forall i\in N,k\in K$ (2.60)

$\displaystyle u_{ik}+v_{ik}\leq 1+\lambda_{i}M$ $\displaystyle\forall i\in
N,k\in K$ (2.61)

$\displaystyle u_{ik}+v_{ik}\geq 1-\lambda_{i}M$ $\displaystyle\forall i\in
N,k\in K$ (2.62)

$\displaystyle u_{ik}\leq\sum_{s=1}^{q}y_{iks}$ $\displaystyle\forall k\in
K,i\in N$ (2.63)

$\displaystyle v_{ik}\leq\sum_{s=1}^{q}y_{iks}$ $\displaystyle\forall k\in
K,i\in N$ (2.64)

$\displaystyle x_{iik}=0$ $\displaystyle\forall i\in N,k\in K$ (2.65)

$\displaystyle S_{ik}\geq 0$ $\displaystyle\forall i\in N,k\in K$ (2.66)

$\displaystyle A_{ik}\geq 0$ $\displaystyle\forall i\in N,k\in K$ (2.67)

$\displaystyle x_{ijk}\in\\{0,1\\}$ $\displaystyle\forall i\in N,j\in N,k\in
K$ (2.68)

$\displaystyle y_{iks}\in\\{0,1\\}\ $ $\displaystyle\forall i\in N,k\in K,s\in
S$ (2.69)

$\displaystyle z_{il}\in\\{0,1\\}$ $\displaystyle\forall i\in N,l\in L$ (2.70)

$\displaystyle u_{ik}\in\\{0,1\\}$ $\displaystyle\forall i\in N,k\in K$ (2.71)

$\displaystyle v_{ik}\in\\{0,1\\}$ $\displaystyle\forall i\in N,k\in K$ (2.72)

The objective function aims to minimize caregivers’ waiting times as well as
to balance their workload. Constraints (2.31) and (2.32) state that each
patient will be visited by a group of caregivers, which their number depends
on the services requested. Constraints (2.33) and (2.34) state that each
caregiver who has left the center to visit assigned patients must return to
that center. Constraints (2.35) impose route continuity (flux conservation)
for the patients assigned to a caregiver $k$, while requiring that tours
should be constructed rather than open paths. Constraints (2.36) determine the
services operations’ starting time of the patient $j$ with respect to the
completion time of service operations of the patient $i$. These constraints
enforce that the starting time of services along the route of a caregiver are
strictly increasing. In doing so, they also eliminate sub-tours because a
return to an already visited patient would violate the start time of the
previous visit [74]. Constraints (2.37) and (2.38) define the arrival time of
a caregiver $k$ to the patient $j$. Constraints (2.39) and (2.40) initialize
the starting and arrival times to zero if the caregiver $k$ will not be
affected to the patient $i$. Constraints (2.41) define the variables
$y_{iks}$, the caregiver $k$ is assigned to the patient $i$ if he visits a
patient or returns to the HHC center after visiting the patient $i$.
Constraints (2.42) ensure that a qualified caregiver $k$ performs a requested
service operation $s$ to the patient $i$. Constraints (2.43) state that each
caregiver provides one service to an assigned patient $i$. Constraints (2.44)
ensure that for a patient $i$, each service is performed by one caregiver.
Constraints (2.45) and (2.46) ensure that each caregiver is available at the
earliest service time $d_{k}$ at the HHC center and must return before the
latest service time $e_{k}$ to that center. Constraints (2.47) and (2.48)
enforce the respecting of patients’ time windows. Constraints (2.49) guarantee
that only one time period is selected from the patient’s availability periods.
Constraints (2.50) and (2.51) ensure the synchronization of caregivers’
starting time if requested service operations must be simultaneous
($\lambda_{i}=1$) for patient $i$. These constraints are the refined version
of constraints (2.73) and (2.74), which reduces the number of constraints from
$2nc^{2}$ to $2nc$.

$\displaystyle
S_{ik^{\prime}}-S_{ik}\leq(2-\sum_{s=1}^{q}y_{ik^{\prime}s}-\sum_{s=1}^{q}y_{iks})M$
$\displaystyle\forall i\in N,k\in K,k^{\prime}\in K$ (2.73)

$\displaystyle
S_{ik^{\prime}}-S_{ik}\geq(\sum_{s=1}^{q}y_{ik^{\prime}s}+\sum_{s=1}^{q}y_{iks}-2)M$
$\displaystyle\forall i\in N,k\in K,k^{\prime}\in K$ (2.74)

Constraints (2.52) define the total working time for each caregiver.
Constraints (2.53) and (2.54) define the absolute value $D_{k}$ between the
total working time of the caregiver $k$ and the average working time:
$D_{k}=max\\{w_{k}-\frac{\sum_{k=1}^{c}{w_{k}}}{c},\frac{\sum_{k=1}^{c}{w_{k}}}{c}-w_{k}\\}$.
Constraints (2.55)-(2.62) guarantee that caregivers start working as soon as
they are available at patients. If the requested services must be
simultaneously performed ($\lambda_{i}=1$) for a patient $i$, constraints
(2.55)-(2.58) must be verified. $SS_{i}$ denotes the synchronized starting
time. These constraints are equivalent to the following formula:
$SS_{i}=max\\{a_{i\hat{l}},A_{ik_{1}},A_{ik_{2}},\ldots\\}$, which is the
maximum between the earliest starting time of the selected availability period
$\hat{l}$ for the patient $i$ and caregivers’ arrival times
$\\{A_{ik_{1}},A_{ik_{2}},\ldots\\}$ at patient $i$. Otherwise, the requested
service operations are not needed to be simultaneous ($\lambda_{i}=0$),
constraints (2.59)-(2.62) ensure that the starting time for each caregiver
equals the maximum between the earliest starting time of the selected
availability period $\hat{l}$ for the patient $i$ and caregiver $k$ arrival
time $A_{ik}$ ($S_{ik}=max\\{a_{i\hat{l}},A_{ik}\\}$). Constraints (2.63) and
(2.64) set $u_{ik}$ and $v_{ik}$ to zero if the caregiver $k$ will not be
affected to the patient $i$. Constraints (2.65)-(2.72) set the domains of the
decision variables.

Although the exact methods guarantee to find the optimal solutions, their
computation time increases with the size of the problem. Heuristics are more
flexible since their computational time could be controlled. A GVNS based
heuristic is proposed in the next section to solve the model with large
instances.

####  2.3.3 Variable neighborhood search

In the section we adapt the proposed GVNS in section 2.2.3 to deal with the
new hypothesis. We mention that the same neighborhoods are used with a
modification to include multiple services per patient. Therefore, we explain
only the changes that has been done.

#####  2.3.3.1 Encoding

We extend the encoding used in the previous chapter to deal with multiple
services per patients. Therefor, we will duplicate a patient $i$ as many times
as the number of services he requested (see Table 2.5).

Example: consider 5 patients and 2 caregivers skilled to provide 3 types of
services operations, patient $4$ requests two services 2 and 3. A solution
will be encoded as follows (see Table 2.5).

Table 2.5: Example of solution encoding Patients | 1 (3) | 3 (1) | 4 (3) | 2 (1) | 4  (2) | 5 (2)
---|---|---|---|---|---|---
Caregivers | 1 | 2 | 1 | 2 | 2 | 1

The caregiver 1 will visit patients 1, 4 and 5 to provide respectively the
services 3, 3 and 2.

#####  2.3.3.2 Decoding

The decoding method used to compute the objective function is defined
according to the following four cases:

  * •

Case 1: single service and single time window ($SSSTW$) for each patient.
Since caregivers’ routes are independents, their starting times will be
iteratively calculated in the order they appear in the matrix;

  * •

Case 2: single service and multiple time windows ($SSMTW$) for each patient.
Since caregivers’ routes are independents, their starting times will be
iteratively calculated in the order they appear in the matrix. Since each
patient has $p$ time windows, the earliest availability period $l\in L$ that
minimizes the tardiness of providing the requested service operation $s$ will
be chosen for each patient;

  * •

Case 3: multiple services and single time window ($MSSTW$). If any patient
requests simultaneous services, caregivers’ routes become dependents.
Therefore, caregivers’ starting times should be synchronized to ensure that
are available at the same time to provide those simultaneous services. A
synchronized starting time $SS_{i}$ per patient (in case $\lambda_{i}=1$) is
considered and it is equal to the maximum between the earliest time window
$a_{i1}$ for the patient $i$ and caregivers’ arrival times
$\\{A_{ik_{1}},A_{ik_{2}},\ldots\\}$. Algorithmically, arrival, starting and
waiting times will be iteratively calculated in the order they appear in the
matrix. Each time a caregiver $k$ arrives to a patient $i$, $SS_{i}$ is first
initialized by $a_{i1}$ and then will take the value $A_{ik}$ if
($A_{ik}>SS_{i}$). These steps are repeated until $SS_{i}$ will not change for
each patient. In the end, caregivers’ starting times at patients will be the
synchronized starting time $S_{ik}=SS_{i}$;

  * •

Case 4: multiple services and multiple time windows ($MSMTW$). This case
generalizes Case 3 to cover multiple time windows per patient. Since only a
single period should be chosen to provide multiple services, this choice may
be suitable for one caregiver but not for another. Therefore, a two-phase
strategy is used to select for each patient an availability period to receive
requested care services and ensure the synchronization of services operations
if are requested to be simultaneous. Phase $I$ aims to heuristically select