## 2 Materials and Methods
### Nearest-Neighbor-Based Randomized Algorithm
Since the capacity constraint is satisfied throughout the route, customer 3 is effectively added to it and removed from \(unvisitedCustomers=4-1-2\). At this point, we choose the next \(trial\) customer either by the ordering of \(unvisitedCustomers\) or by the nearest neighbor strategy, according to a probability \(\rho\). Consider that the nearest neighbor strategy has been used to select the next customer this time, and thus customer 1 was chosen as \(trial\). Therefore, the route to be tested is \(0-3-1-0\), as presented in Table 2. We check its feasibility:  
* \(load_{03}=d_{3}+d_{1}=3+4=7\leq 12\);
* \(load_{31}=load_{03}-d_{3}+p_{3}=7-3+3=7\leq 12\);
* \(load_{10}=load_{31}-d_{1}+p_{1}=7-4+2=5\leq 12\). The capacity constraint remains satisfied all the way through the route, and therefore, customer 1 is added to it and removed from \(unvisitedCustomers=4-2\). Again consider that \(trial\) has been chosen by the nearest neighbor strategy, and thus customer 4 was selected as \(trial\). Now the route to be tested is \(0-3-1-4-0\), as shown in Table 3. We check its feasibility:  
* \(load_{03}=d_{3}+d_{1}+d_{4}=3+4+5=12\leq 12\);
* \(load_{31}=load_{03}-d_{3}+p_{3}=12-3+3=12\leq 12\);
* \(load_{14}=load_{31}-d_{1}+p_{1}=12-4+2=10\leq 12\);
* \(load_{40}=load_{14}-d_{4}+p_{4}=10-5+8=13\
lessapprox 12\). However, in this attempt, the capacity constraint is violated. Customer 4 is not removed from \(unvisitedCustomers=4-2\) but is set to be infeasible (crossed out in the list). Assume now that \(trial\) has been chosen by the ordering of \(unvisitedCustomers\). In this case, the first customer not set as infeasible (customer 2) was selected as \(trial\). Now the route to be tested is \(0-3-1-2-0\), as presented in Table 4. We check its feasibility:  
* \(load_{03}=d_{3}+d_{1}+d_{2}=3+4+2=9\leq 12\); \begin{table}
\begin{tabular}{l c c c c} \hline \hline  & **Depot** & **Customer 3** & **Customer 1** & **Customer 2** \\ \hline delivery & – & 3 & 4 & 2 \\ pickup & – & 3 & 2 & 1 \\ \hline load & 9 & 9 & 7 & 6 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Vehicle load of the tentative route \(0-3-1-0\). \begin{table}
\begin{tabular}{l c c c} \hline \hline  & **Depot** & **Customer 3** & **Customer 1** \\ \hline delivery & – & 3 & 4 \\ pickup & – & 3 & 2 \\ \hline load & 7 & 7 & 5 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Vehicle load of the tentative route \(0-3-1-4-0\). * \(load_{31}=load_{03}-d_{3}+p_{3}=9-3+3=9\leq 12\);
* \(load_{12}=load_{31}-d_{1}+p_{1}=9-4+2=7\leq 12\);
* \(load_{20}=load_{12}-d_{2}+p_{2}=7-2+1=6\leq 12\). The capacity constraint is satisfied throughout the route, and therefore, customer 2 is added to it and removed from \(unvisitedCustomers=\
ot{4}\). At this point, \(unvisitedCustomers\) is not empty, and for that reason, we do not have a feasible solution yet. In addition, \(unvisitedCustomers\) only contains customers that are set as infeasible, and thus the current route cannot be expanded. This route is then closed and incorporated to the current set of routes under construction. The feasibility of unvisited customers is reestablished (\(unvisitedCustomers=4\)), and a new route is opened. For the new route, assume that the capacity of the vehicle randomly chosen is \(q=10\). The depot is added to the route, and \(trial\) is set to be the first customer from \(unvisitedCustomers\) (i.e., customer 4). The route to be tested is \(0-4-0\), as shown in Table 5. We check its feasibility:  
* \(load_{04}=d_{4}=5\leq 10\);
* \(load_{40}=load_{04}-d_{4}+p_{4}=5-5+8=8\leq 10\). The capacity constraint is fulfilled, and therefore, customer 4 is added to the route and removed from \(unvisitedCustomers=nil\). Since \(unvisitedCustomers\) is empty, the route is closed and incorporated to the current set of routes. Finally, a feasible solution to the HVRPSPD is obtained. Note that the computation time of the functions \(nearestNeighbour\), \(firstPossiblyFeasible\), and \(checkRoutFeasibility\) is \(O(n)\).