## 3 The Proposed EATS-MOBFS Method for the 2L-VRPSC
### Framework of the Solution Mechanism
#### 3.1.4 Diversification Mechanisms  
The main advantage of tabu search is that it can avoid revisiting recent solutions via the tabu list, while it emphasizes relatively small and local neighborhoods [36]. Based on this consideration, a diversification mechanism is integrated to enhance the exploration capability of EATS, which is inspired by the remove-reinsert strategy in the large neighborhood search [34]. The basic idea of the remove-reinsert method is to reconstruct the obtained local optimum solution by ruining the incumbent best solution first and then reconstructing a new feasible solution. First, several similar customers are removed from the solution according to the Shaw removal heuristic [37], expecting to create a new, perhaps better, solution by the reinsertion process. To quantify the similarity of two customers, a relatedness indicator \(\widetilde{r}(i,j)\) is proposed as follows:  
\[\widetilde{r}(i,j)=\alpha_{1}(\frac{d_{ij}}{d_{max}})+\alpha_{2}\big{|}q_{i}-q _{j}\big{|}+\alpha_{3}(1-\frac{\big{|}K_{i}\cap K_{j}\big{|}}{\min\big{\{}|K_{ i}|,\big{|}K_{j}\big{|}\big{\}}}) \tag{14}\]  
where \(d_{max}\) denotes the maximal distance over all \(d_{ij}\) (\(i,j\in N\)), which is used for standardizing \(d_{ij}\). Term \(K_{i}\) denotes the set of vehicles able to serve customer \(i\), and \(|K_{i}|\) denotes the number of vehicles in set \(K_{i}\). Terms \(\alpha_{1},\alpha_{2},\alpha_{3}\) are weight coefficients.  
As shown in (14), the relatedness indicator consists of three aspects: (i) the distance between customers, (ii) the difference in demands between customers, and (iii) the difference in the number of vehicles that can serve customers.  
In the reinserting process, the customers that have been removed from the solution are first sorted in descending order according to the total area of their items and reinserted into the partial solution one by one. The route and position of a customer are decided by the same insertion-based rule used in the initial solution construction (Section 3.1.1). When a customer cannot be inserted into any route, other customers in a partial solution are randomly erased one by one until the given customer can be inserted into the partial solution successfully. Then the mechanism restarts the reinserting process with the erased customers. The reinserting process is repeated until a complete solution is found. The pseudocode Algorithm 4 for the removal process is shown as follows. The removal process initially selects a customer \(i\) randomly (Algorithm 4 line 1). Then it repeatedly chooses an already selected customer, \(j\), and selects a new customer that is most related to \(i\) (Algorithm 4 line 4-7). The process stops when \(\rho\) customers have been chosen. Moreover, a determination parameter \(\phi\) (\(\phi\geq 1\)) (Algorithm 4 line 7) introduces some randomness into the request selection process (a high value of \(\phi\) corresponds to low randomness).  
```
Input: Destruction degree \(\rho\), integer \(\phi\) and current solution \(X\) Output: The set of customers removed (\(R_{m}\))
1 Randomly select a customer \(i\) to remove from \(X\), \(R_{m}=\{i\}\).
2 while\(|R_{m}|<\rho\)do
3 Select a request randomly from \(R_{m}\).
4\(R_{l}\) be the requests list sorted in descending order of relatedness.
5 Generate a random number \(a\) from the internal \([0,1)\).
6 Remove \(j=R_{l}\big{[}|R_{l}|\cdot a^{\phi}\big{]}\) from \(X\).
7\(R_{m}=R_{m}\cup\{j\}\).
8
9 end while
```  
**Algorithm 4** Removal Operation.