# Variable Neighborhood Search for the Two-Echelon Electric Vehicle Routing Problem with Time Windows
## 4 Solution Approach
### Variable Neighborhood Search for the 2E-EVRP-TW
Therefore, we have adopted the method introduced by [54] for the solution acceptance decisions (lines 20-29). Based on this method, while improved solutions are always accepted, non-improving solutions are accepted with a certain probability \(p_{accept}\). At each iteration, function \(\text{ClcAcceptanceProbability}()\) calculates \(p_{accept}\) as follows:  
\[p_{accept}=\frac{e^{(-(f_{ext}(S_{local})-f_{ext}(S_{cur})))}}{T} \tag{51}\]  
Here, \(f_{ext}(S_{cur})\) and \(f_{ext}(S_{local})\) are values of the extended fitness function of the current solution and of the solution after local search, respectively. Lastly, \(T\) refers to the actual temperature value. At the beginning, \(T\) is initialized to an initial temperature \(T_{init}\) which is decreased by \(t^{-}\) at each main iteration of VNS (see line 30). In this way, while a non-improving solution is more likely to be accepted early during the search, the probability of accepting non-improving solutions will decrease with a growing iteration number. However, in case no improved solution was found during \(iter\_tri_{max}\) iterations, \(T\) is reset to \(T_{init}\) in order to enhance diversification. ```
1:input: an initial solution \(S_{init}\)
2:\(S_{shake}\) : Solution obtained after shaking
3:\(S_{local}\) : Local solution after VND
4:\(S_{cur}\) : Current solution
5:\(S_{bsf}\) : Best-so-far solution
6:\(iter\_ni\) : The number of non-improving solutions
7:\(iter\_ni_{max}\) : The maximum iteration limit for non-improving solutions
8: Determine set of neighborhood structures for shaking \(\{N_{k}^{\textit{shake}}\mid k=1,\ldots,k_{max}\}\) and local search \(\{N_{h}^{local}\mid h=1,\ldots,h_{max}\}\)
9:\(S_{cur},S_{bsf}\gets S_{init}\)
10:while the computational time limit is not reached do
11: Create \(\pi\) of the shaking neighborhoods \(N_{k}^{\textit{shake}}\)
12: Set \(k\gets 1\)
13:while\(k\leq k_{max}\)do
14: Apply shaking: Choose \(S_{shake}\) from \(N_{\pi(k)}^{\textit{shake}}(S_{cur})\), the \(\pi(k)\)th shaking neighborhood of \(S_{cur}\)
15:if\(N_{\pi(k)}^{\textit{shake}}\) is a removal/destroy operator then
16: Repair \(S_{shake}\)
17:endif
18: Re-construct first echelon tours using C&W savings algorithm
19: Apply local search: \(S_{local}\leftarrow\text{VND}(S_{shake})\)
20:\(p_{accept}\leftarrow\text{ClcAcceptanceProbability}(f_{ext}(S_{cur}),f_{ext}(S_{ local}),T)\)
21:\(\rho\leftarrow\text{rand}()\)
22:if\(f_{ext}(S_{local})<f_{ext}(S_{bsf})\)then\(S_{bsf}\gets S_{local}\)
23:if\(f_{ext}(S_{local})<f_{ext}(S_{cur})\) or \(\rho<p_{accept}\)then
24:\(S_{cur}\gets S_{local}\)
25:\(k\gets 1\)
26:else
27:\(k\gets k+1\)
28:\(iter\_ni\gets iter\_ni+1\)
29:endif
30: Decrease \(T\) by \(t^{-}\)
31:if\(iter\_ni=iter\_ni_{max}\)then
32:\(T\gets T_{init}\)
33:\(iter\_ni\gets 0\)
34:endif
35:endwhile
36:endwhile
```  
**Algorithm 2** VNS for the 2E-EVRP-TW  
The following four sections will provide a detailed description of standard shaking operators, removal/destroy operators, repair operators, and local search neighborhoods, respectively.