# Variable Neighborhood Search for the Two-Echelon Electric Vehicle Routing Problem with Time Windows
## 4 Solution Approach
### Initial Solution Construction
In this study, we have utilized the formulation introduced by [38]: \[s2_{ij}=d2_{si}+d2_{sj}-\lambda d2_{ij}+\mu|d2_{si}-d2_{sj}|+\gamma\frac{D2_{i} +D2_{j}}{\overline{D}}\] (50) Note that, according to this formula, both the distances between nodes as well as the customer demands have an influence on the route construction process. More precisely, the first four terms of Equation (50) are based on the distances between nodes, while the last term (\(\frac{(D2_{i}+D2_{j})}{\overline{D}}\)) takes into account the customer demands. Hereby, \(D2_{i}\) and \(D2_{j}\) refer to the demands of customers \(i\) and \(j\), while \(\overline{D}\) indicates the average demand of customers in \(N_{\mathbb{C}}^{s}\setminus L_{u}\). As a result, tours that include customers with higher demands are prioritized during tour merging operations and vehicle capacities are used more effectively. Finally, note that the so-called _route shape parameter_\(\lambda\) adjusts the selection priority based on the distance between customers \(i\) and \(j\)[39], while \(\mu\) is used to scale the asymmetry between customers \(i\) and \(j\)[40]. Parameter \(\gamma\) weights the demand information. Note that well-working values for these parameters are obtained by parameter tuning which is presented in Section 5.2. Finally, the savings list is sorted according to non-increasing savings values. 3. At each iteration, the two routes that contain a pair of nodes \((i,j)\) with the highest savings value \(s2_{ij}\) are selected from \(R\) (e.g., \(\tau 2_{1}\), \(\tau 2_{2}\)). Then, the chosen routes are merged by connecting nodes \(i\) and \(j\). All of the merging scenarios are graphically illustrated in Figure 3. Based on the way in which nodes \(i\) and \(j\) are connected to the respective satellite, one or both of the routes must be reversed in order to be able to connect nodes \(i\) and \(j\). In this context, note that the reversed version of a tour \(\tau 2_{1}\) is denoted by \(\text{rev}(\tau 2_{1})\). If the merged route is infeasible in terms of vehicle capacity or time windows, the route is eliminated, and merging continues considering the pair of nodes with the next-highest savings value. If the merged route is battery infeasible, a charging station \(r\) with a lowest insertion cost is inserted between node \(i\) and \(j\) (e.g., \(<\)s - \(\ldots\)- i - r - j - \(\ldots\)-s\(>\)). In these cases in which the route is still infeasible after charging station insertion, it is eliminated, and merging continues with the next pair of customers from the savings list. This procedure is repeated while the savings list is not empty. After merging, some of the charging stations that were previously added to the routes may become redundant. These charging stations are removed from the merged route. 4. Update the savings list as described in step 2 and repeat step 3 until no further pairs of tours can be merged. Finally, the customers in \(L_{u}\) (the list of unvisited customers) are inserted into the constructed tours using the greedy insertion operator, which is described in detail in Section 4.3.3.