# 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
#### 4.3.3 Repair Operators  
A partially destroyed solution may either be repaired using an exact or a heuristic approach. Although exact approaches guarantee the optimal insertion of removed customers or routes, they are much more time consuming than heuristic approaches, especially when a rather large part of the solution is destroyed. Moreover, too much optimality in the repair operator may limit the diversification capabilities of the search. Therefore, we have applied greedy and best-insertion strategies for repairing partially destroyed solutions; see also [56; 57]. In the following, partially destroyed solutions are labelled \(S_{d}\).  
_Greedy customer insertion:_ This operator reinserts each customer from \(L_{r}\) into the partially destroyed solution \(S_{d}\) according to the last-in-first-out (LIFO) principle. Henceforth, \(N_{S_{d}}\) denotes the set of nodes (customers and charging stations) that still form part of the partially destroyed solution \(S_{d}\). Let \(v\in L_{r}\) be the customer that is to be re-inserted into \(S_{d}\). First, for each pair \(i,j\in N_{S_{d}}\) such that \(i\) and \(j\) are consecutive nodes in one of the routes of \(S_{d}\), the insertion cost \(\delta_{vij}\) is calculated as follows:  
\[\delta_{vij}=d2_{iv}+d2_{vj}-d2_{ij} \tag{52}\]  
Then, customer \(v\) is inserted at the position with the lowest insertion cost. Suppose that the obtained route after insertion is infeasible in terms of vehicle capacity or time windows constraints. In this case, customer \(v\) is inserted at the next-cheapest position in terms of the insertion cost, and so on. If no feasible insertion position can be found, the customer is finally inserted at the initially best position, ignoring the infeasibility. In case of battery infeasibility, a charging station is added to the route. These procedures are applied until no customer remains in \(L_{r}\).  
_Greedy customer insertion with noise:_ This operator is a special version of the greedy customer insertion operator described above. It utilizes the following modified cost function with a noise parameter for calculating the insertion cost of a customer \(v\):  
\[\delta_{vij}^{noise}=\delta_{vij}+d_{max}+\alpha+\beta \tag{53}\]  
Here, \(d_{max}\) refers to the maximum distance between all nodes in \(N_{SRC}\), and \(\alpha\) refers to the noise parameter set to \(0.1\)[57; 58; 59; 60]. Finally, \(\beta\) is a uniform random number generated independently for the calculation of each cost value from the interval \([-1,1]\).  
_Best customer insertion:_ Instead of re-inserting customers from \(L_{r}\) in the LIFO order, this operator aims to find the best insertion position for all customers. Each time, the insertion costs of all remaining customers from \(L_{r}\) are calculated using Equation (52). Then, the customer with the best insertion cost is inserted into the best possible position. This operator is much more time consuming than the greedy customer insertion operator. Itmay, however, lead to better results. Infeasible insertions are handled in the same way as the greedy customer insertion operator.  
_Greedy CS insertion:_ In the case of battery infeasibility, this operator inserts a charging station with the lowest insertion cost at the point at which infeasibility occurs. Figure 5 illustrates the insertion of a charging station to a battery-infeasible route. Assuming that the electric vehicle runs out of battery before reaching node \(v_{4}\), the operator first tries to insert a charging station \(r^{*}:=\text{argmax}\{d2_{3r}+d2_{r4}-d2_{34}\mid r\in N_{R}\}\) between nodes \(v_{3}\) and \(v_{4}\). In case the battery level is not high enough to reach the charging station that is to be inserted, a possible insertion is tried before node \(v_{3}\), etc.