## 3 Problem Description and Cost Model
### Savings Algorithm for Generating Initial Solutions
Within this algorithm, the charging stations are assumed to be known a priori and cannot be changed. However, within Algorithm 2, we extend the procedure from [PERSON] and [PERSON] [20] significantly by incorporating location planning for charging stations. ```
1:Input: scheduled service trips \(T\), charging stations \(S\)
2:Output: vehicle rotations \(V\), charging stations \(\overline{S}\)
3:\(V\leftarrow\emptyset\)
4:\(\overline{S}\gets S\)
5:for all\(t\in T\)do
6: Add a vehicle rotation to \(V\) containing only \(t\);
7:endfor
8:while TRUE do
9:for all\(v\in V\



### Variable Neighborhood Search for Improvement

To finding new solutions with lower total costs, we use a VNS based solution method. VNS was first introduced by [PERSON] et al. [10]. Solution approaches based on VNS have already been extensively considered in the literature and have been proven to be suitable for numerous practical problems with realistic data sizes [32]. The underlying concept of VNS is a systematic change of neighborhoods, both in an improvement phase to find a local optimum and in a perturbation phase to escape from local optima. In the perturbation phase, a so-called shaking method is applied, which exerts a stochastic influence on an incumbent solution by performing stochastic changes. Even this procedure can cause a deterioration in the objective function value it has used to escape from local optima. In the improvement phase, a local search method is used to find new solutions with lower total costs. Adapting the basic VNS concept to solve the E-VSP-LP thus requires the definition of a problem specific neighborhood structure and methods for shaking, a local search, and changing the neighborhood. Algorithm 3 provides the procedure for our solution method. The algorithm follows the _basic_ VNS adapted from [PERSON] et al. [33]. Note that the following procedure is applicable not only for solutions generated by Algorithm 2 but also for every possible feasible solution. ```
1:Input: vehicle rotations \(V\), charging stations \(S\), \(t_{max}\), \(k_{max}\)
2:Output: vehicle rotations \(V\), charging stations \(S\)
3:\(t\gets 0\)
4:while\(t<t_{max}\)do
5:\(k\gets 1\);
6:while\(k\leq k_{max}\)do
7:\((V^{\prime},S^{\prime})\leftarrow\texttt{SHAKE}(V,S,k)\);
8:\((V^{\prime\prime},S^{\prime\prime})\leftarrow\texttt{BESTIMPROVEMENT}(V^{ \prime},S^{\prime},k)\);
9:\((V,S,k)\leftarrow\texttt{NEIGHBORHOODCHANGE}((V,S),(V^{\prime\prime},S^{ \prime\prime}),k)\);
10:endwhile
11:\(t\gets CPUTIME()\);
12:endwhile
13:return\((V,S)\);
```

**Algorithm 3** Basic Variable Neighborhood Search (BVNS). We first define a neighborhood \(N_{k}\) of size \(k\in\mathbb{N}\) by selecting \(k\) vehicle rotations. The choice of the vehicle rotations will be made randomly from the entire set in order to incorporate stochastic influences. It follows the maximum neighborhood size \(k_{max}\in\mathbb{N}\) as the number of vehicles used within the incumbent solution. After each iteration of shaking and local search, a neighborhood change is performed. In this step, the objective function values of the incumbent and improved solution are compared. If the improved solution is better than the incumbent, it is accepted and the size of the neighborhood is reset to the smallest possible value. Otherwise, the size of the neighborhood is increased and the procedure is repeated. The procedure terminates when the maximum computational time is exceeded. Algorithm 4 shows the procedure formally. ```
1:Input:solutions \((V,S)\), \((V^{\prime},S^{\prime})\), neighborhood size \(k\), objective function \(f\)
2:Output: solution \((V,S)\), neighborhood size \(k\)
3:if\(f(V^{\prime},S^{\prime})<f(V,S)\)then
4:\((V,S)\leftarrow(V^{\prime},S^{\prime})\);
5:\(k\gets 1\);
6:else\(k\gets k+1\);
7:endif
8:return\((V,S),k\);
```

**Algorithm 4**NEIGHBORHOODCHANGE. Second, we use Algorithm 5 as the local search method within Algorithm 3 for improving a solution.