# Balancing Staff Finishing Times vs. Minimizing Total Travel Distance in Home Healthcare Scheduling
## 4 Solution Method
For the feasibility test, we chose the conditions to ensure the feasibility of the algorithm. For convenience, the route \(i\) can be written as \(R_{k}=\left[0,\ \delta_{k^{\prime}}^{1}\delta_{k^{\prime}}^{2}\ldots, \delta_{k}^{|R_{k}|},0\right]\) where each \(\delta_{k}^{i}\) represents the node that vehicle \(k\) visits in the \(j^{th}\) order. **Definition 1**. : _The starting time for node \(\delta_{k}^{i}\) is equal to the maximum between the lower time window of the node, i.e., \(e_{\delta_{k}^{i}}\), and the starting time of the immediately preceding node together with the travel time between them and service time, i.e., \(t\big{(}\delta_{k}^{j-1}\big{)}\ +\ p_{\delta_{k}^{j-1}}+d_{\delta_{k}^{j-1} \delta_{k}^{j}}\). Thus, \(t\big{(}\delta_{k}^{i}\big{)}=\max\left\{\ e_{\delta_{k}^{i}},t\Big{(}\delta_ {k}^{i-1}\Big{)}+p_{\delta_{k}^{i-1}}+d_{\delta_{k}^{i-1},\delta_{k}^{i}}\right\}\)_  
**Definition 2**. : _The completion time for node \(\delta_{k}^{i}\), namely \(c\Big{(}\delta_{k}^{i}\Big{)}\), is equal to the combination of the starting time and the service time of the node, i.e., \(c\Big{(}\delta_{k}^{i}\big{)}=s\Big{(}\delta_{k}^{i}\Big{)}+p_{\delta_{k}^{i}}\)._  
**Definition 3**. : _The finishing time for node \(\delta_{k}^{i}\), namely \(f\left(\delta_{k}^{i}\right)\), is equal to the maximum of completion time between all nodes visited by caretaker \(k\), i.e., \(f\left(\delta_{k}^{i}\right)=\max\limits_{j\in\{1,2,\ldots,|R_{k}|\}}\left\{c \Big{(}\delta_{k}^{i}\Big{)}\right\}\)._  
**Lemma 1**. : _Let \(R_{k}=\left[0,\ \delta_{k}^{1},\delta_{k}^{2},\ldots,\delta_{k}^{|R_{k}|},0\right]\) be a routing sequence for vehicle \(k\). The node \(\delta\) can be feasibly inserted into the routing sequence \(R_{k}\) next to the \(i\) position, i.e., between \(\delta_{k}^{i}\) and \(\delta_{k}^{i+1}\) if the following conditions hold:_  
\[t\Big{(}\delta_{k}^{i+1}\Big{)}-d_{\delta_{k}^{i+1}}-p_{\delta}\geq e_{\delta}\]\[c\left(\delta_{k}^{i}\right)+d_{\delta_{k}^{i},\delta}+p_{\delta} \leq l_{\delta}\] \[t\left(\delta_{k}^{i+1}\right)-c\left(\delta_{k}^{i}\right)\geq d_ {\delta_{k}^{i},\delta}+p_{\delta}+d_{\delta_{k}^{i+1}}\]  
Proof. : Suppose the node \(\delta\) is inserted between \(\delta_{k}^{i}\) and \(\delta_{k}^{i+1}\). The completion time for node \(\delta\) can be calculated as  
\[t(\delta)=\max\Bigl{\{}e_{\delta},c\left(\delta_{k}^{i}\right)+d_{\delta_{k}^{ i},\delta}\Bigr{\}}.\]  
Consequently, the starting time for the node \(\delta_{k}^{i+1}\) can be recalculated as:  
\[t\left(\delta_{k}^{i+1}\right)=\max\Bigl{\{}e_{\delta_{k}^{i}},c(\delta)+d_{ \delta_{k}^{i+1}}\Bigr{\}}.\]  
To check for feasibility, we must ensure that the starting times of \(\delta\) and \(\delta_{k}^{i+1}\) lie within their time windows. Specifically, the starting time for \(\delta_{k}^{i+1}\) needs to be recalculated; we set it as \(t^{*}\left(\delta_{k}^{i+1}\right)\). If \(e_{\delta}\geq\ c\left(\delta_{k}^{i}\right)+d_{\delta_{k}^{i},\delta}\), the starting time for \(\delta\) is set to be equal to its lower time window, i.e., \(t(\delta)=e_{\delta}\leq l_{\delta}\). Consequently, from condition (1), we obtain  
\[t^{*}\left(\delta_{k}^{i+1}\right)\geq t\left(\delta_{k}^{i+1}\right)\geq e_{ \delta}+d_{\delta_{k}^{i+1}}+p_{\delta}.\]  
The starting time for \(\delta_{k}^{i+1}\) can thus be set to remain the same. Therefore, the starting times for \(\delta\) and \(\delta_{k}^{i+1}\) lie within their time windows. Similarly, in the case of \(e_{\delta}\leq\ c\left(\delta_{k}^{i}\right)+d_{\delta_{k}^{i},\delta}\), by using condition (3), the new starting time for \(\delta_{k}^{i+1}\) also satisfies its time windows. For \(\delta\), from the assumption, \(t(\delta)=\max\Bigl{\{}e_{\delta},c\left(\delta_{k}^{i}\right)+d_{\delta_{k}^{ i},\delta}\Bigr{\}}\) and condition (2), the starting time is calculated to be \(t(\delta)=c\left(\delta_{k}^{i}\right)+d_{\delta_{k}^{i},\delta}\leq l_{ \delta}-p_{\delta}\leq l_{\delta}\).