## 4 Solution Strategies
### The Neighborhood Search by Probability  
This section aims to inter-change the clustering of customers in each depot. The neighborhood search by probability (called NSP) is used to exchange the customers based on a probability calculated by Equation (39):  
\[p(C_{i},D_{n})=\frac{\max\Bigl{\{}\overline{d(C_{i},D)}-\mathrm{d}(C_{i},D_{n }),0\Bigr{\}}}{\sum_{n=1}^{N}\max\Bigl{\{}\overline{d(C_{i},D)}-\mathrm{d}(C_{ i},D_{n}),0\Bigr{\}}}, \tag{39}\]  
where \(\mathrm{d}(C_{i},D_{n})\) indicates the distance customer \(i\) to depot \(n\), and \(\overline{d(C_{i},D)}\) indicates the average distance between customer \(i\) and all depots. For example, the distance between customer 1 and depots 1, 2 and 3 are 7, 4 and 5, respectively. The average distance of customer 1 and all depots is 5.34. The probability that customer 1 is assigned to depots 1, 2 and 3 equals 0.00%, 80.00% and 20.00%, respectively. Although depot 2 is closest to customer 1, there is a chance to assign customer 1 to depot 2. After calculating the probability, the next step is to randomize the number of customers to inter-change nodes (\(k\)). where \(k\ \in\ [2,\ \text{round up}\ (N*0.2)]\) that mean \(k\) should be the random number between 2 to round up 20% of the number of customers. The neighborhood search strategies, a kind of changing sequence, is developed to four neighborhood search structures and described for \(k=2\) as follows:  
* Inter-exchange by probability, randomize \(k\) customer nodes from each depot in a clustered customer sequence, as demonstrated in Figure 6a. The neighborhood structure is defined as Nh1;
* Inter-insertion by probability, randomize \(k\) customer nodes from one depot to another depot in a clustered customer sequence, as demonstrated in Figure 6b. The neighborhood structure is defined as Nh2;
* Intra-exchange without probability is similar to inter-exchange but change \(k\) customer nodes only for the same depot. The neighborhood structure is defined as Nh3;
* Intra-insertion without probability is similar to inter-insertion but insert \(k\) customer nodes only for the same depot. The neighborhood structure is defined as Nh4. The sequencing of the structure neighborhood is selected by two random operations between inter-depot and intra-depot neighborhood search structures. For example, iteration 1 used sequencing of structure neighborhood {Nh1,Nh4}, but iteration 2 used {Nh2,Nh3}. The idea of the NPS is to increase the search to prevent moving into a trap solution. Similarly to Section 4.1.2, the neighborhood search translation is used to return the position sequence with the new changed customer sequence. For example, a customer sequence before entering the NSP is {6, 3, 7, 8, 5, 1, 2, 4, 9, 10} denoted by NS10 (Figure 7), the dimension position corresponding to the customer sequence is {0.090, 0.133, 0.210, 0.409, 0.666, 0.695, 0.778, 0.858, 0.949, 0.990} (denoted by RS10). The NSP that changes NS10 to a new customer sequence is {8, 3, 7, 6, 10, 2, 1, 4, 9, 5}(denoted by NSP10) (Figure 7b) with the corresponding dimension position RS10. Figure 6: Methods of neighborhood search. (**a**) Inter-exchange; (**b**) Inter-insertion structure. \[RI=\left(\frac{Sol_{CT}-Sol_{name}}{Sol_{CT}}\right)\times 100, \tag{42}\]  
where  
\(HP=\) the heuristic performance (%). \(Optimal=\) the optimal solution obtained from the mathematical model. \(RI=\) the relative improvement (%) between current practices and meta-heuristics. \(Sol_{CT}=\) the solution obtained from current practices. \(Sol_{name}=\) the solution obtained from the meta-heuristics. The numerical experiments were tested with 18 randomly generated instances and 1 case study. The factors of all instances and a case study are shown in Table 3.  
In Table 3, the first column shows the size instances, including small (instances S1-S5), medium (instances M1-M7), large size instances (instances L1-L6), and the case study (instance CS1).