# 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  
The initial solution constructed by our version of the C&W savings heuristic from above is used as input for a variable neighborhood search (VNS) approach outlined in the following. VNS was proposed by [41] to solve complex combinatorial optimization problems. Unlike other algorithms based on local search, VNS uses multiple neighborhood  
Figure 3: Graphical illustration of route merging in the C&W savings heuristic. structures and makes use of them during the search based on a set of pre-defined rules. This dynamic search mechanism allows the algorithm to intensify the search in the vicinity of good solutions, but also to diversify the search in order to avoid getting stuck in local optima. In particular, intensification is achieved by applying a local search procedure in order to reach locally optimal solutions, while shaking operators are used in order to diversify the search process and to explore different neighborhoods. For these reasons, the choice of appropriate neighborhood structures/operators for local search and for shaking is crucial. So far, VNS has shown state-of-the-art performance for a wide range of optimization problems, including the facility layout problem [42], scheduling problems [43; 44; 45], portfolio optimization [46; 47], assembly and disassembly line balancing [48] and various routing problems [49; 50; 51; 52]. Algorithm 2 presents a pseudo-code of our implementation of VNS for the 2E-EVRP-TW. The proposed algorithm starts by taking an initial solution \(S_{init}\) as input. Then, the neighborhood structures used for shaking \(N_{k}^{\textit{shake}}\), \((k=1,\ldots,k_{max})\) and the ones used for local search \(N_{h}^{local}\), \((h=1,\ldots,h_{max})\) are determined. These neighborhood structures will be explained in detail in following sections. However, note that, in addition to rather standard inter-route and intra-route operators, our VNS also makes use of so-called destroy-and-repair operators for the shaking step. Operators such as these ones were mostly introduced in the context of approaches based on large neighborhood search (and very large neighborhood search) algorithms and have shown to be highly useful for exploring large search spaces [53]. In particular, the reconstruction of a partially destroyed solution using various reinsertion operators has the potential to produce solutions that may have been difficult to reach otherwise. Concerning the specific case of VRP problems, removing rather large components of a solution and reinserting them into other positions of the solution may help reduce the number of routes and the number of vehicles, respectively. After obtaining the initial solution \(S_{init}\), both the current solution \(S_{cur}\) and the best-so-far solution \(S_{bsf}\) are initialized to \(S_{init}\). At each main iteration of VNS, the shaking neighborhoods are randomly ordered. This order is then used until the current neighborhood utilized for shaking (indicated by \(k\)) is the \(k_{max}\)-th neighborhood. Next, a random solution \(S_{shake}\) is chosen from the current shaking neighborhood \(k\). In case this neighborhood is a removal/destroy operator, the partially destroyed solution must subsequently be repaired with an insertion operator; see lines 15-17 of Algorithm 2. After re-constructing the first echelon tours of \(S_{shake}\) using our C&W savings algorithm (line 18), local search is applied to \(S_{shake}\). For this purpose we applied the variable neighborhood descent (VND) method shown in Algorithm 3. In the VND phase, a set of local search operators are applied to \(S_{shake}\) in a predefined and fixed order. In this context, note that after each application of a shaking and/or a local search operator, the first echelon routes must be reconstructed since satellite demands may have changed. In a basic VNS, only improved solutions are accepted. However, in the context of problems with many unfeasible solutions, this may cause the algorithm to get stuck during the search process.