## 3 Problem Description and Cost Model
### Savings Algorithm for Generating Initial Solutions
This is done even though the objective function value is being worsened. ```
1:Input: neighborhood \(N_{k}\)
2:Output: neighborhood \(N_{k}\)
3:Choose EXST, SST or SCP as \(f\) at random;
4:if\(f(N_{k})\) is feasible then
5:return\(f(N_{k})\);
6:else Go to 1
7:endif
```

**Algorithm 9** SHAKE. ### Inserting Partial Chargings

In our computational study, which follows this section, we incorporate complete and partial charging procedures. So far, the algorithms presented operate with any kind of charging procedures. However, we need more algorithmic effort in order to incorporate partial chargings within Algorithms 2 and 3. To that purpose, we consider the following Algorithm 10 by [PERSON] and [PERSON] [34]. It is applied to each vehicle rotation that is generated respectively modified within the solution procedure. As a result, Algorithm 10 either returns the set of partial charging procedures that have to be inserted into the corresponding vehicle rotation or its infeasibility. Only if a resulting vehicle rotation is feasible is it taken into further consideration. ```
1:Input: neighborhood \(N_{k}\)
2:Output: neighborhood \(N_{k}\)
3:Choose EXST, SST or SCP as \(f\) at random;
4:if\(f(N_{k})\) is feasible then
5:return\(f(N_{k})\);
6:else Go to 1
7:endif
```

**Algorithm 10** checks iteratively, after each trip of a rotation, whether the SoC has been violated (I. 2). If this is the case, the previous trips are considered (I. 3). Each trip that begins or ends at a charging station represents a charging opportunity (I. 5). If no such possibilities are found the vehicle rotations is infeasible (I. 9). Over all charging possibilities determined, the one performed at the most highly frequented charging station is processed (I. 11). This aims at reducing the number of charging stations by shifting charging procedures from less to more highly frequented charging stations. In the next step, the vehicle rotation is divided at the specific charging station into two sub-rotations containing the previous and subsequent trips. Then, both sub-rotations are processed by the algorithm. In the case that all sub-rotations are feasible, the algorithm terminates (I. 13). If a charging station is no longer needed it is omitted. If at least one sub-rotation is infeasible, the next charging opportunity is processed (I. 15 and I.16). ```
1:vehicle rotation \(v\), set \(S\) of charging stations
2:vehicle rotation \(v\), feasibility or infeasibility of \(v\)
3:for all\(t_{1}\in v\)do
4:if SoC after executing \(t_{1}\) is not sufficient then
5:for all\(t_{2}\in v\) previous to \(t_{1}\)do
6:if Departure stop is a charging station then
7: Save charging opportunity;
8:endif
9:endfor
10:if Set of charging opportunity is empty then
11:return\(v\), infeasible;
12:endif
13: Add charging opportunity at the highest frequented charging station;
14:if Vehicle rotation can be performed then
15:return\(v\), feasible;
16:else
17: Exclude charging opportunity from the set of all opportunities;
18: Go to 8;
19:endif
20:endif
21:endfor
```

**Algorithm 10** Inserting Partial Chargings (PCP). ## 5 Computational Analysis

In the following, we perform our computational experiments. We first present the instances to be solved and the problem parameters. Then, we look at the results of a sequential planning approach. In this case, location planning of charging stations and vehicle scheduling of BEBs are solved one by one. Therefore, our analysis is twofold: First, we discuss the results of solving a location planning problem for charging stations to enable the operation of given cost-optimal vehicle rotations computed for traditional buses without the range limitations of BEBs. Second, we present the results of solving an E-VSP given the locations of charging stations computed in the previous step. Last, we analyze the results of simultaneous problem solving using our heuristic solution method provided by Algorithm 3 for the E-VSP-LP and compare the results to the sequential planning approaches.