## 5 A Descent Local Search Algorithm for an HHC Problem  
In this section, we adopt a descent local search algorithm based on the work of [PERSON] et al. [36], and we fix, as they did, the planning horizon to a daily one. The set of jobs demanded by patients is denoted \(\mathcal{J}\). Each job \(j\in\mathcal{J}\) is associated with a certain duration \(dur_{j}\) and a time frame \([\alpha_{j},\beta_{j}]\). To reach another patient, a distance \(d_{j}\) (beeline) is set up, and a travel time \(t_{j}\) is calculated. Let \(\mathcal{C}\) denote the set of caregivers. \(\mathcal{C}\) includes both full-time and part-time caregivers. For each caregiver \(c\in\mathcal{C}\), a time window corresponding to their available time is set up. Variables \(t_{c}^{begin}\) and \(t_{c}^{end}\) represent respectively the time when the caregiver \(c\) starts and ends his/her journey. The working time of a caregiver \(c\) is defined by \(t_{c}^{zero}\). It must not exceed the maximal working time planned by his/her labor agreement. We set \(p_{i}\) as a penalty that occurs when a job is not assigned. The objective function minimizes unassigned jobs and the daily operating cost of the HHC such as salaries and traveling cost by refunding the fuel cost. The solving method was based on a descent algorithm. Firstly, the algorithm tries to reduce the bag of non-allocated jobs by switching jobs between caregiver and the bag until the job can insert itself into a caregiver schedule, as described in Figure 9. During this process, the qualification constraint must be respected, as well as the working balance, as much as possible. Compatibility constraints can be raised if necessary. Indeed, for example, a patient can have a low compatibility score with all caregivers. In Figure 9, for example, the algorithm tries neighborhood moves by inserting the first job of the bag in front of the second job of the second caregiver. At the same, it also tries to insert the second job of the second caregiver in front of the first job of the first caregiver. Lastly, the algorithm inserts the last job of the first caregiver at the end of the job list of the second caregiver to produce a correct solution. For more details about the algorithm, please refer to the main article written by [PERSON] et al. [36]. Algorithm 1 presents a pseudo-code version of how the descent local search algorithm works regarding the different inputs. \begin{table}
\begin{tabular}{c c c c} \hline \hline  & **Parameters** & **Range** & **References** \\ \hline \#1 & Number of depots & 1–3 & [9; 35] \\ \#2 & Number of days & 1–7 & [13; 31; 34] \\ \#3 & Number of patients & 10–250 & [11; 21; 28; 39] \\ \#4 & Number of caregivers & 2–25 & [5; 11; 21; 30; 43] \\ \#5 & Number of different qualifications & 5–7 & [9; 13; 34; 41] \\ \#6 & Reference caregiver & false-true & [42] \\ \#7 & Part-time/full-time proportion & 5–50\% & [16; 34] \\ \#8 & Traveled time between patients (ratio) & 15–25\% & [13; 33] \\ \#9 & Occupation/capacity of the instance (ratio) & 50–100\% & [33; 35; 43] \\ \#10 & Synchronization ratio (ratio) & 10–25\% & [13; 32; 38] \\ \#11 & Biological samples (ratio) & 10\% & [13; 24; 38] \\ \#12 & Precedence between jobs (ratio) & 10–25\% & [12; 24; 44] \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Range of all editable parameters. ```
Result: Optimal shifts for caregivers  Given a set of patients \(\mathcal{P}\), a set of caregivers \(\mathcal{C}\), and a set of jobs \(\mathcal{J}\):  Create a feasible solution for all caregivers with a bag of jobs for unassigned jobs; for job in \(\mathcal{J}\)do if job can be affectedthen  Assign it randomly to a caregiver with the right qualifications; else  Store it in the bag of jobs;  end if  end while whilethe solution can be improveddo if not an empty bag of jobsthen  Try to insert a job in a caregiver shift;  Fix the solution if the solution violates the constraints; if job cannot be insertedthen  Do not try again to insert jobs from the bag of jobs.