## 3 Metaheuristic Algorithm
### Proposed Memetic Algorithm
#### 3.1.3. Local Search (LS) Procedure  
The LS procedure is based on local search strategies, applied to intensify the search in pursuit of finding local minima. This procedure consists of five different neighborhood structures arranged into two classes, namely intra-route and inter-route mechanisms, performing them iteratively. This strategy has proved to be successful for a mono-objective version of the CCVRP [10]. Below, we describe each type of move:  
* _Intra-route swap._ The procedure exchanges the positions of two customers belonging to the same route. For instance, if the customers to exchange belong to positions \(h\) and \(i\), then arcs \((h-1,h)\), \((h,h+1)\), \((i-1,i)\) and \((i,i+1)\) are removed and replaced by arcs \((h-1,i)\), \((i,h+1)\), \((i-1,h)\) and \((h,i+1)\). It is important to remark that these movements do not affect feasibility in terms of capacity.
* _Intra-route reallocation._ This mechanism deletes a customer from its current position and reinserts it into another position on the same route.
* _Intra-route 2-opt._ In this operator, two non-adjacent edges \((h,h+1)\) and \((i,i+1)\) in the path \(0,1,2,\ldots,h,h+1,\ldots,i,i+1,\ldots\) are deleted and replaced by \((i,h)\) and \((h+1,i+1)\), resulting in the new path \(0,1,2,\ldots,h,i,\ldots,h+1,i+1,\ldots\).  
* _Inter-routes interchange._ This strategy exchanges two customers belonging to different routes, as long as the move keeps feasibility (in terms of capacity).
* _Inter-routes reallocation._ For a given customer, the operator searches for the best position of the customer to move in any of the routes. If the best-identified position is different from the current one, the movement is performed.  
The two major strategies operate as follows: At first, the initial solutions are sent to the intra-local search procedure, where the intra-local search strategies are applied. Then, the local minimum is forwarded to perform inter-routes local search strategies. These procedures are iteratively implemented, while the current solution value \(L\) keeps improving. In each process, the reallocation movement is performed first, and the execution of the interchange movement next. The first improvement criterion (\(FI\)) is used. Algorithm 4 exhibits this process.  
```
begin repeat \(S^{*}=S\) and \(L^{*}=L\), and \(T^{*}=T\);  S',L' T' \(\leftarrow\) Intra-route local search (S,L, T); ifThe solution is non-dominatedthen \(S=S^{\prime}\) and \(L=L^{\prime}\), \(T^{*}=T\);  end if S',L' T'\(\leftarrow\) Inter-routes local search (S,L, T); ifThe solution is non dominatedthen \(S=S^{\prime\prime}\) and \(L=L^{\prime\prime}\), \(T^{*}=T\);  end if until\(L^{*}>L\); return\(S^{*},L^{*},T^{*}\);  end while
```  
**Algorithm 4**Local search (\(S,L,T\)).  
As observed, this mutation procedure seeks to insert improved individuals to the next generation, although the mechanism does not guarantee that the chromosome selected can be deeply improved. Because the size of this subset is relatively small, it is always possible to find a chromosome to be improved.  
This procedure differentiates the two versions of the MA. For the first version (MA-RK v1), all of the feasible individuals generated by the crossover mechanism are sent to the LS procedure (\(threshold=1\)). For the second version (MA-RK v2), the local search mechanism is applied only to a certain percentage of individuals, expecting to accelerate the performance of the algorithm in terms of CPU time.