## 4 Algorithms
### Path Relinking Procedure  
Path relinking is a search strategy guided by the other solution based on the idea that quality solutions may share similar properties [44]. The guide solution is selected from the current best solution. Path relinking aims to create a new solution that shares information from the original and the guided solutions. In the context of VRPTW, the good solutions may retain some routes as the current best solution. Route-based path relinking is therefore considered in this study: the new solution will have one of the routes as the guided solution. The path relinking contains two steps. The first step is to select a guided route (any route) from the guided solution and then remove all patients corresponding to the guided route from the current solution. The next step is to insert the removed patients into the current solution using the _Inserting procedure_. Suppose, for example, that the current solution contains 3 routes arranged as follows: O-A1-A2-A3-A4+O, O-B1-B2-B3-O, O-C1-C2-C3-C4-C5-O, and the guided route is O-A2-B3-A3-C5-O. The result will contain 4 routes: O-A2-B3-A3-C5-O (the guided route), O-A1-A4-O, O-B1-B2-O, and O-C1-C2-C3-C4-O. The procedure can be summarized as follows:  
```
1. Input: the current solution, set to \(p\) and guided solution (current best solution), set to \(p_{best}\)
2. Randomly choose any route in \(p_{best}\), set to \(r_{0}\)
3. Remove all jobs corresponding to route \(r_{0}\) from \(p\). If the remaining schedule is infeasible, move the infeasible patient to \(r_{0}\). 4. Apply the Inserting procedure to insert all jobs in \(r_{0}\) to \(p\)

### Inserting Procedure

The aim of this procedure is to arrange patients, one by one, between pairs of already assigned patients where none of the assigned patients are served late. In the iteration process, if the inserted patient cannot be treated immediately after the completion time of the directly preceding patient, that caretaker will wait until the lower time window of the patient is reached. A patient that cannot be inserted into any position will be considered a tardy (late) patient. Let \(J\) be a set of assigned patients, \(J_{w}\) be a set of tardy patients, \(J_{c}\) be a set of remaining unattended patients and let \(J(j)\) be a set of all assignments obtained by inserting patient \(j\) between every pair of patients in the assignment \(J\), iteratively. The inserting procedure can be described as follows: \begin{tabular}{l l} \hline \hline \multicolumn{2}{l}{**Inserting Procedure**} \\ \hline
1. & **Input**: A set of assigned patients, set to \(J\), and a set of patients (waiting to be scheduled), set to \(J_{c}\) \\
2. & **Set**\(J_{w}=\varnothing\) and arrange the patients in \(J_{c}\) according to their upper time windows in ascending order \\
3. & **While**\(J_{c}\
eq\varnothing\)**do** \\
4. & Choose the first patient in \(J_{c}\), say \(j\). Remove \(j\) from \(J_{c}\) \\
5. & Consider the set of assignments \(J(j)\) \\
6. & **If** there is more than one assignment and all patients are not late **do** \\
7. & Choose the case that has the minimum completion time, set to \(J\) \\
8. & **Else If** there is a tardy patient in every assignment in \(J(j)\)**do** \\  & Choose the assignment with only one late patient, set as \\
9. & \(J\), and whose assignment completion time after removing that patient is the smallest. \\  & Add the late patient to \(J_{w}\) \\
10. & **Else If** every assignment \(J(j)\) has more than two tardy patients **do** \\
11. & Add the patient \(j\) to the set \(J_{w}\) \\
12. & **End If** \\
13. & **End While** \\
14. & **While**\(J_{w}\
eq\varnothing\)**do** \\
15. & Add a new caretaker. Repeat all steps in the While loop with \(J_{w}\), instead of \(J_{c}\), until there is no change in \(J\). \\
16. & **End While** \\ \hline \hline \end{tabular} 

### Local Search Procedure

The aim of the proposed Local Search is to improve the solution. Some patients, if served by a different caretaker, could result in reduced objective value.