## 2 Materials and Methods
### Nearest-Neighbor-Based Randomized Algorithm
vehicle capacity constraint) with the possible addition of customer trial in the end of route \(route.add(trial)\)// trial is added to route \(unvisitedCustomers.remove(trial)\)// trial is removed from unvisitedCustomers \(first\leftarrow\)false// the first customer of the route is already added else \(trial.infeasible\leftarrow\)true// trial is proven infeasible to be part of route \(feasibleCustomers\leftarrow\)false for each customer in unvisitedCustomersdo ifnot\(customer.infeasible\)then \(feasibleCustomers\leftarrow\)true// There are still customers in unvisitedCustomers that can be possibly added to route \(currentRoutes.add(route)\)// route is closed and added to currentRoutes if\(bestRoutes=nil\)or\(cost(currentRoutes)<cost(bestRoutes)\)then \(bestRoutes\gets currentRoutes\)// new best routes found return bestRoutes
```  
**Algorithm 1**Nearest-Neighbor-Based Randomized Algorithm  
In the sequel, we propose a feasible solution to the problem of finding  
At each iteration, to obtain a feasible solution, we first generate a random permutation of all customers. We maintain a list of customers that were not served by a vehicle yet, named as _unvisitedCustomers_, which is initially set with the random permutation. The routes of a feasible solution are generated sequentially. For each route, we randomly choose a vehicle among all types. The route always starts from the depot to the first customer from _unvisitedCustomers_ whose delivery and pickup demands respect the capacity of the vehicle used to serve the route. Thereafter, the next customer under consideration to be appended to the route, named as _trial_, is chosen either by the ordering of _unvisitedCustomers_ or by the nearest neighbor strategy, according to a probability \(\rho\). Every time _trial_ has been effectively added to the current route, it is removed from _unvisitedCustomers_. And every time _trial_ has been proven to be infeasible to be part of the route (because of a vehicle capacity violation), we set its property \(infeasible=\mathsf{true}\), and then it is no more considered to be part of this route. The algorithm follows this process until there are no more customers that can be appended to the current route. In this case, the current route is closed, the feasibility of customers in _unvisitedCustomers_ is reestablished (\(infeasible=\mathsf{false}\)), and a new route is opened. Routes are created until all customers have been visited (_unvisitedCustomers_ is empty), when we obtain a feasible solution to the HVRPSPD. The algorithm continues to generate feasible solutions until a time limit is reached. The best set of routes found during this whole process is deemed to be the final solution. To illustrate the core of our algorithm, consider the running example presented in Figure 1 with 4 customers and the depot. Assume that the random permutation is _unvisitedCustomers_\(=3-4-1-2\) and that the capacity of the vehicle chosen to serve the route is \(q=12\). Since _route_ is initially empty, the depot (i.e., node 0) is added to the route, and _trial_ is set to be the first customer from _unvisitedCustomers_ (i.e., customer 3). In this point, the route to be tested is \(0-3-0\). We denote by \(load_{ij}\) the cargo of the vehicle while traversing the arc \(ij\). Note that the vehicle must leave the depot loaded with all deliveries of the customers on the route and, conversely, return to the depot with all pickup demands of these customers. In Table 1, we check the feasibility of the route: \begin{table}
\begin{tabular}{l c c} \hline \hline  & **Depot** & **Customer 3** \\ \hline delivery & – & 3 \\ pickup & – & 3 \\ \hline load & 3 & 3 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Vehicle load of the tentative route \(0-3-0\). Figure 1: Running example with 4 customers and the depot. Pickup and delivery demands are marked in blue, and distances between customers are marked in red. \(load_{03}=d_{3}=3\leq 12\);
* \(load_{30}=load_{03}-d_{3}+p_{3}=3-3+3=3\leq 12\).