## 4 Algorithms
### Path Relinking Procedure
Since there are many candidates to consider, it is more convenient to generate a priority list of every pair of jobs. The List is sorted using the traveling times between pairs of patients in ascending order. We developed three improving procedures: Swapping procedure (Section 4.4.1), Moving procedure (Section 4.4.2), and 2-opt procedure (Section 4.4.3). In the first step of Local Search, the procedure will generate a priority list containing all candidates for swapping, moving, and 2-opt. It will then apply Swapping, Moving and 2-opt procedures accordingly. The procedures are explained in detail below. #### 4.4.1 Swapping Procedure

The swapping procedure aims to switch the order of a pair of jobs on the List in order to make the solution better, or to reduce the objective value. For our purpose, the List is generated by sorting travel times between pairs of patients. This procedure will be applied multiple times until the solution can no longer be improved. \begin{tabular}{l l} \hline \hline \multicolumn{2}{l}{**Swapping Procedure**} \\ \hline
1. & **For** (job1, job2) in List **do** \\
2. & swap the routing position between job1 and job2 if it reduces the total routing cost and the routing \\
3. & **End For** \\ \hline \hline \end{tabular} 

#### 4.4.2 Moving Procedure

This procedure uses the same idea as the swapping procedure: the chosen patient is moved to another position. The patient moves when the objective value is reduced; otherwise, the patient will maintain his/her position. This procedure also uses the same List as the swapping procedure. \begin{tabular}{l l} \hline \hline \multicolumn{2}{l}{**Moving Procedure**} \\ \hline
1. & **For** (job1, job2) in List **do** \\
2. & Move job2 to process before or after job1 if it reduces the total routing cost and the routing is \\  & feasible. If both positions reduce cost, choose the one with more cost reduction. \\
3. & **End For** \\ \hline \hline \end{tabular} 

#### 4.4.3 2-Opt Procedure

This is a local search procedure for solving the traveling salesman problem. It uses the same idea as the swapping procedure by swapping a pair of edges, instead of patients, from any route and reconnecting them with each other. In other words, the main idea is the crossover between two routes. The edge moves when the objective value is reduced; otherwise, all patients will maintain their positions. The List for this procedure contains all pairs of edges in random order. Suppose, for example, that we have two routes that start and end at the origin, denoted by \"O\", and are arranged as follows: O-A1-A2-A3-A4-A5-O and O-B1-B2-B3-B4-B5-B6-O. Suppose the selected edges are (A1-A2) and (B4-B5). The result routes will be O-A1-B5-B6-O and O-B1-B2-B3-B4-A2-A3-A4-A5-O. \begin{tabular}{l l} \hline \hline
**2-Opt Procedure** \\ \hline
1. & **For** (A-B, C-D) in List **do** \\
2. & Define a path starting from depot to node A by OA, a path starting from B to depot by BO, a path \\  & starting from depot to node C by OC, and a path starting from D to depot by DO. \\
3. & Reconstruct a path as OA connected to DO and OC connected to BO only if the result is feasible \\  & and the total cost is reduced. \\
4. & **End For** \\ \hline \hline \end{tabular} 

### R&R Procedure

The main idea behind this procedure is to jump out to a new solution to avoid the local optimum [30]. In this procedure, one of the caretakers is randomly removed. The removed patients are then added to the remaining caretakers using the _Inserting procedure_. If some of the remaining patients cannot be inserted into any place, a new caretaker will be deployed by applying the _Inserting procedure_ to the remaining patients.