## 3 Metaheuristic Algorithm
### Proposed Memetic Algorithm
#### 3.1.1 Constructive Procedure Based on Random Keys  
The constructive procedure creates an initial population of feasible solutions based on generating a chain \(S_{a}=\{1,2,\cdots,n\}\) and, for each customer, an auxiliary random key \(R_{a}\) is used to encode the solution. Additionally, an empty set \(S_{p}\) is used to save the temporary assignment of the customers to the routes. ```
begin\(it\gets 0\);  Initialize a population (\(P_{0}\)) of \(\sigma\) chromosomes implementing the constructive procedure based on random keys;  Sort \(P_{0}\) in fronts following the non-dominated sorting approach; for(\(it=1;it<=\mathit{Maxiter};it++\))do  Generate an offspring population \(P_{it}\), of size \(N\), from \(P_{it-1}\), using selection, crossover and local-search operators;  Combine parent and offspring population \(R_{it}=P_{it}\cap P_{it-1}\);  Sort population using the non-dominated sorting approach, identify fronts \(F_{j}=(1,2,\cdots)\), and calculate the crowding distance for each solution in \(F_{j}\);  Make \(T_{it+1}\leftarrow\emptyset,j\gets 1\); while(\(|T_{it+1}|+|F_{j}|<N\))do \(T_{it+1}\gets T_{it+1}+F_{j}\) ; \(j\gets j+1\);  Sort solutions in \(F_{j}\) in decreasing order according to crowding distances, select the first \(N-|T_{it+1}|\) elements of \(F_{j}\) and add it to \(T_{it+1}\);  end while  end for
```  
**Algorithm 1**Memetic algorithm with random keys. **Encoding mechanism:** To encode the solution, a real number drawn randomly from [0, 1) is assigned to every single position in \(R_{a}\). Figure 3 depicts an example of this mechanism. **Decoding mechanism:** The decoding mechanism is applied based on the information of the random key \(R_{a}\). The \(R_{a}\) chain is sorted in a non-decreasing order and their respective positions in \(S_{a}\) are sorted correspondingly. As a result, a random ordered chain \(S_{a}\) is obtained. Figure 4 exhibits the decoding mechanism. **Assignment mechanism**: In every iteration, the algorithm selects the corresponding \(j\)th customer in \(S_{a}\) and systematically tries to insert it into into a temporary set \(S_{p}\) in the first available position (procuring to maintain feasibility in the capacity of the vehicles). For instance, if in the first potential route, two customers have been previously assigned, the next open position will be the third one. In the case that the customer cannot be inserted in the route due to the capacity constraints, the insertion will be evaluated in the next available route. It is important to emphasize that, since the number of routes is given in advance, the construction procedure considers a parallel routing mechanism. In other words, it performs the evaluation of feasible insertions over all of the routes. If so, the algorithm continues by selecting the next customer at \(S_{a}\). Otherwise, the construction mechanism stops. If the algorithm reaches a feasible assignment, then \(S\gets S_{p}\) and the solution is inserted into the population  
Figure 4: Example of the decoding mechanism. Figure 3: Example of the encoding mechanism. \(Q_{t}\). Otherwise, the algorithm destroys the partial constructed solution in \(S_{p}\) and generates a new random key \(R_{a}\) (to sort \(R_{a}\)). The entire constructive procedure finishes when all of the customers have been assigned into \(S_{p}\) or after having a successive number of attempts without producing a feasible solution. When a feasible assignment is reached, the set \(S\) represents a feasible initial solution of routes. The customers already inserted in \(S\) are removed from \(S_{a}\). Figure 5 shows an illustrative example of a feasible assignment. After reaching a feasible assignment, the sequencing mechanism is applied to construct each route by respecting the order of insertion and, based on this, the corresponding calculations of the objective functions \(L\) (representing the total latency of the system) and \(T\) (total tardiness of the system, based on the priorities of the customers) are performed. Algorithm 2 shows the pseudocode for this algorithm.