# Variable Neighborhood Search for the Two-Echelon Electric Vehicle Routing Problem with Time Windows
## 4 Solution Approach
### Solution Representation and Extended Objective Function  
In our implementation, a solution \(S\) is represented by two sets of routes: \(R1\) and \(R2\). Each route \(\tau 1\in R1\) starts from a central warehouse, visits one or more satellites from \(N_{S}\), and returns to the same central warehouse. Each route \(\tau 2\in R2\) starts from a satellite \(s\in N_{S}\), visits a sequence of locations/nodes \(v\in N_{RC}\), and returns to the same satellite. Figure 1 shows an exemplary solution for a 2E-EVRP-TW instance with a single central warehouse, two satellites, three charging stations and five customers. The solution contains one route in the first echelon (\(\tau 1_{1}\)) and two routes in the second echelon (\(\tau 2_{1}\) and \(\tau 2_{2}\)). The usefulness of allowing the algorithm to visit unfeasible solutions during the search process has already been recognized in the metaheuristics community, especially in the field of evolutionary computation [37]. In this work, we do this in a similar way as in [12] in the context of the EVRP. In particular, the extended objective function that evaluates both feasible and unfeasible solutions by means of penalty values for capacity, battery, and time windows violations is defined as follows:  
\[f_{ext}(S)=f(S)+\omega_{c}P_{cap}(S)+\omega_{b}P_{bat}(S)+\omega_{tw}P_{tw}(S) \tag{44}\]  
Here, \(f(S)\) refers to the objective function of the 2E-EVRP-TW problem, that is, the sum of the distances traveled by all utilized vehicles from the first and the second echelon. Furthermore, \(P_{cap}(S)\), \(P_{bat}(S)\) and \(P_{tw}(S)\) denote the capacity, battery and time windows violations in solution \(S\). In this context, the function for calculating the capacity violations of a solution \(S\) with \(m\) routes in the first echelon and \(n\) routes in the second echelon is defined as follows:  
\[P_{cap}(S)=\sum_{i=1}^{m}\max\Big{\{}\big{(}\sum_{j\in\tau 1_{i}}D1_{j}\big{)}-Q1,0 \Big{\}}+\sum_{k=1}^{n}\max\Big{\{}\big{(}\sum_{l\in\tau 2_{k}}D2_{l}\big{)}-Q2,0 \Big{\}} \tag{45}\]  
In words, if the total demand of the satellites (resp. the customers) on a route exceeds the vehicle capacity, the capacity violation of the route is determined as the difference between the vehicle capacity and the total demand of the route. Otherwise, it is set to zero. Note that, in an abuse of notation, \(j\in\tau 1_{i}\) refers to a satellite \(j\) visited by route \(\tau 1_{i}\) and \(l\in\tau 2_{k}\) refers to a customer \(l\) visited by route \(\tau 2_{k}\). Next, the total battery violation of a solution \(S\), \(P_{bat}(S)\), is calculated using Equations (46) and (47):  
\[P_{bat}(S) =\sum_{k=1}^{n}P_{bat}(\tau 2_{k})\quad,\text{where} \tag{46}\] \[P_{bat}(\tau 2_{k}) =\sum_{l\in\tau 2_{k}}\big{|}\min\{BSCa_{le},0\}\big{|} \tag{47}\]  
That is, this function sums (for all second echelon routes \(\tau 2_{k}\)) the battery level violations of the electric vehicles at the arrival to all nodes \(l\in\tau 2_{k}\). Hereby, the term _node_ refers  
Figure 1: Example of a solution for a small 2E-EVRP-TW instance with a single central warehouse, two satellites, three charging stations and five customers. to customers and charging stations. Finally, similar to the approach used to calculate \(P_{\text{batt}}\), \(P_{\text{ttw}}\) is calculated using Equations (48) and (49):  
\[P_{\text{ttw}}(S) =\sum_{k=1}^{n}P_{\text{ttw}}(\tau 2_{k})\quad,\text{where} \tag{48}\] \[P_{\text{ttw}}(\tau 2_{k}) =\sum_{l\in\tau 2_{k}}\max\left\{w2_{\text{e}i}-t\text{v}l_{i},0\right\} \tag{49}\]  
These three penalty terms are added as a weighted sum to the original objective function value (see Equation (46)). The corresponding three weights are denoted by \(\omega_{c}\), \(\omega_{b}\) and \(\omega_{\text{ttw}}\). At the start of the VNS algorithm, all three weights are set to an initial value \(p_{init}\). Then, they are dynamically updated between \(p_{\text{min}}\) and \(p_{\text{max}}\).