# Balancing Staff Finishing Times vs. Minimizing Total Travel Distance in Home Healthcare Scheduling
## 4 Solution Method
### Initial Solution  
To obtain qualified solutions, it is preferable to start with a good one. In this section, the insertion algorithm is proposed. An initial solution inspired by the insertion operator is generated. The fundamental concept is to assign a patient to the routing sequence (caretaker) with the fewest patients, so that the number of patients each caregiver must visit will be balanced. In addition, the new patient will be added to the position in the sequence with the earliest completion time. When a patient is inserted into a sequence of other patients, it is common for subsequent patients to have to delay their procedures. To fix this, tardy patients will be removed from the route and reassigned to other positions. This procedure will continue until no patients remain. Moreover, the procedure will try to minimize both objectives simultaneously by choosing the minimum finishing time as the primary and the minimum total distance as the secondary objective. The pseudocode is given in Algorithm 2. ```
1.Input: A set of patients (waiting to be assigned), set to \(J_{c}\) and a partial solution, \(J=\{J_{1},J_{2},\ldots,J_{K}\}\) where \(J_{i}\) is the routing sequence of route \(i\), and \(K\) is the number of caretakers. 2.Set\(J_{m}=\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.Choose a caretaker \(k\) that has the minimum number of patients. Consider all inserting assignments of \(j\) into \(J_{k}\). 6.If there is more than one inserting assignment such that all patients are not late do
7.Choose the case that has the minimum finishing time and if there are the same value of finishing time, choose the minimum distance, replace the route into \(J\). 8.Else If there are tardy patients in every inserting assignment of \(j\)do
9.Choose the assignment that has the lowest number of tardy patients and whose inserting assignment's completion time after removing tardy patients is the smallest, replace the route in \(J\). Add the tardy patients to \(J_{w}\). 10.End If
11.End While
12.While\(J_{w}\
eq\varnothing\)do
13.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\). 14.End While

### Neighborhood Operators

In this study, the solution space is explored using three neighborhood operators, namely swap, move and path exchange. After obtaining an initial solution, neighborhood operators will iteratively enhance the solution. Each iteration will select one of these operators at random. The procedures are detailed below. Moving operator: The objective of the operator is to move patients from their current location in the routing sequence to a new location where they will not be tardy. This operator will begin moving patients from the route with the highest number of patients to the route with the lowest number of patients in order to balance out completion times. Even if the completion time increases, it is still possible for the solution to be accepted due to its probability. Figure 1 below shows the example of such moving operation. Swapping operator: Shown in Figure 2 is the example of swapping operation. The objective of this operator is to swap the locations of two patients. Similarly to the moving operator, the switch operator will be applied to the pair of patients that will not cause other patients to be late and will accept the worst possible solution. Path exchange operator: The purpose of the path exchange operator is to choose an edge and exchange the path either at the start or end of that edge in a pair of routes. It is analogous to the swap operator, except that it swaps a pair of edges. The operator will be applied if the result is feasible. For example, as shown in Figure 3, path 4-5-0 is selected from the first route and path 0-6-7 is selected from the second route.