# An Improved Genetic Algorithm for Solving the Semi-Soft Clustered Vehicle Routing Problem
## 4 Solution Methodology
### Improved Genetic Algorithm  
The algorithm proposed in this paper employs a two-level strategy to solve the SemiSoftCluVRP, which is also one of the widely used methods for solving the CluVRP and the SoftCluVRP. The algorithm decomposes the original problem into two sub-problems at low-level and high-level. The former aims to determine the visiting order of customers within each cluster, while the latter aims to determine the allocation of all clusters to vehicles and the visiting order between them. For these two sub-problems, first abstract them as a TSP and a CVRP, respectively, and then use genetic algorithms tailored to solve the corresponding problems. In addition, after each generation of genetic operations, a VND method including inter-route and intra-route neighborhood search operators is used to enhance the local search capability of the algorithm. The flowchart of the proposed algorithm is shown in Figure 2 and the pseudocode of the proposed algorithm is shown in Algorithm 1. ```
1:Maximum number of iterations \(T\), population size \(\eta\), crossover probability \(\theta_{1}\), mutation probability \(\theta_{2}\)
2:Optimal solution \(S^{*}\) Begin
3:1: Solve the low-level sub-problem and provide the initial visiting order of customers within each cluster;
4:2:\(P\leftarrow\) Initialize population for the high-level sub-problem;
5:3:\(S^{*}\leftarrow\) Compute the fitness values of all individuals and record the best individual;
6:4:While the stopping criteria is not met
7:5: While the population size is not satisfied
8:6:\(P_{1},P_{2}\leftarrow\) Randomly select two individuals from the current population using the binary tournament method;
9:7:\(P_{1}^{\prime},P_{2}^{\prime}\leftarrow\) Crossover (\(P_{1},P_{2},\theta_{1}\));
10:8:End While
11:\(P_{c}\leftarrow\) Population generated by the crossover operator;
12:\(P_{m}\leftarrow\) Mutation (\(P_{c},\theta_{2}\));
13:\(P_{clu1}\leftarrow\) Perform VND at inter-route cluster level (\(P_{m}\));
14:\(P_{clu2}\leftarrow\) Perform VND at intra-route cluster level (\(P_{clu1}\));
15:\(P_{cus}\leftarrow\) Perform VND at intra-route customer level (\(P_{clu2}\));
16:\(P\leftarrow\) Truncation selection (\(P_{cus}\));
17:\(S^{*}\leftarrow\) Compute the fitness values of all individuals and record the best individual;
18:End While
19:Return the optimal solution \(S^{*}\); End
```  
**Algorithm 1**Pseudocode of the improved genetic algorithm  
Figure 2: Flowchart of the improved genetic algorithm. 4.1.1 Handling the Low-Level Sub-Problem  
For each cluster, since the sum of the demands of all customers within it must not exceed the vehicle's capacity, the determination of their visiting order can be achieved by solving the corresponding TSP while disregarding the customer demands. A genetic algorithm is employed to solve this TSP. Here, chromosomes are encoded using integer encoding, where each gene corresponds to a customer, and the gene sorting determines the visiting order of customers; the initial population is generated in a random manner; the fitness function is the reciprocal of the length of the TSP tour; the selection operator uses the binary tournament method; the crossover operator uses the partial matching crossover and two-point order crossover strategies with equal probability; and the mutation operator uses the swap mutation and inversion mutation strategies with equal probability. 4.1.2 Handling the High-Level Sub-Problem  
Each cluster is treated as a whole, with its demand being the sum of the demands of all customers within it, thus abstracting a CVRP. A genetic algorithm is used to solve this CVRP.