## 3 Problem Description and Cost Model
### Savings Algorithm for Generating Initial Solutions
The set of charging stations determined by the previous experiment within Section 5.2 serves as the input, since this set is already optimal if corresponding solutions are feasible for BEBs. Following Section 1, the objective of the E-VSP is to minimize the \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Instance** & **Batter Capacity (kWh)** & **\# Vehicles** & **\# Stations** & **Operat. Costs (Mio)** & **Feasible Rotations** & **Total Costs (Mio)** \\ \hline \multirow{4}{*}{t135\_s207} & 60 & 69 & 47 (22.71\%) & - & 5 (7.25\%) & - \\  & 120 & 69 & 44 (21.25\%) & - & 31 (44.93\%) & - \\  & 300 & 69 & 33 (15.94\%) & - & 62 (89.86\%) & - \\  & 500 & 69 & 7 (3.38\%) & 1.127 & 69 (100\%) & 33.93 \\ \hline \multirow{4}{*}{t1135\_s101} & 60 & 75 & 33 (32.67\%) & - & 43 (57.33\%) & - \\  & 120 & 75 & 27 (26.73\%) & - & 69 (92\%) & - \\  & 300 & 75 & 15 (14.85\%) & 1.351 & 75 (100\%) & 35.48 \\  & 500 & 75 & 2 (1.98\%) & 1.349 & 75 (100\%) & 35.60 \\ \hline \multirow{4}{*}{t1296\_s88} & 60 & 47 & 43 (48.86\%) & - & 28 (59.68\%) & - \\  & 120 & 47 & 32 (36.36\%) & - & 42 (80.37\%) & - \\  & 300 & 47 & 25 (28.40\%) & - & 42 (80.37\%) & - \\  & 500 & 47 & 6 (6.81\%) & 0.114 & 47 (100\%) & 22.76 \\ \hline \multirow{4}{*}{t2633\_s67} & 60 & 125 & 29 (43.28\%) & - & 74 (58.4\%) & - \\  & 120 & 125 & 21 (32.34\%) & - & 80 (64\%) & - \\  & 300 & 125 & 17 (25.37\%) & - & 117 (93.6\%) & - \\  & 500 & 125 & 8 (11.94\%) & 2.652 & 125 (100\%) & 60.91 \\ \hline \multirow{4}{*}{t3067\_s209} & 60 & 165 & 90 (43.06\%) & - & 88 (53.33\%) & - \\  & 120 & 165 & 69 (33.01\%) & - & 154 (93.33\%) & - \\  & 300 & 165 & 39 (18.66\%) & - & 162 (96.97\%) & - \\  & 500 & 165 & 14 (6.69\%) & 3.045 & 165 (100\%) & 80.79 \\ \hline \multirow{4}{*}{t1580\_s209} & 60 & 75 & 55 (26.31\%) & - & 39 (52\%) & - \\  & 120 & 75 & 45 (21.53\%) & - & 61 (81.33\%) & - \\  & 300 & 75 & 20 (9.56\%) & 1.342 & 75 (100\%) & 36.71 \\  & 500 & 75 & 7 (3.34\%) & 1.319 & 75 (100\%) & 36.82 \\ \hline \multirow{4}{*}{t1487\_s209} & 60 & 89 & 53 (25.35\%) & - & 46 (51.79\%) & - \\  & 120 & 89 & 37 (17.71\%) & - & 87 (97.76\%) & - \\  & 300 & 89 & 24 (11.48\%) & 1.696 & 89 (100\%) & 43.74 \\  & 500 & 89 & 7 (3.34\%) & 1.672 & 89 (100\%) & 43.47 \\ \hline \multirow{4}{*}{t1060\_s209} & 60 & 54 & 43 (20.57\%) & - & 43 (79.63\%) & - \\  & 120 & 54 & 30 (14.35\%) & 0.988 & 54 (100\%) & 28.20 \\ \cline{1-1}  & 300 & 54 & 13 (6.22\%) & 0.987 & 54 (100\%) & 26.11 \\ \cline{1-1}  & 500 & 54 & 3 (1.43\%) & 0.985 & 54 (100\%) & 26.04 \\ \hline \multirow{4}{*}{t1074\_s209} & 60 & 56 & 39 (18.66\%) & - & 31 (55.36\%) & - \\  & 120 & 56 & 33 (15.78\%) & - & 52 (92.86\%) & - \\ \cline{1-1}  & 300 & 56 & 16 (7.65\%) & 0.986 & 56 (100\%) & 27.67 \\ \cline{1-1}  & 500 & 56 & 6 (2.87\%) & 0.985 & 56 (100\%) & 27.69 \\ \hline \multirow{4}{*}{t933\_s209} & 60 & 54 & 35 (16.74\%) & - & 23 (42.60\%) & - \\ \cline{1-1}  & 120 & 54 & 25 (11.96\%) & - & 32 (77.78\%) & - \\ \cline{1-1}  & 300 & 54 & 15 (7.17\%) & 0.971 & 54 (100\%) & 26.59 \\ \cline{1-1}  & 500 & 54 & 4 (1.91\%) & 0.963 & 54 (100\%) & 26.26 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Results of solving a location planning problem for charging stations for the electrification of cost-minimal vehicle rotations computed without range restrictions incorporating partial charging procedure. number of buses in use and the operational costs for deadheading while covering each service trip. In order to ensure comparability, partial chargings are performed. Because the E-VSP is NP-hard and exact solution methods are not suitable for solving large real-world instances in general, as in our experiments, we solve the E-VSP heuristically here. To do so, we use our main solution method from Algorithm 1 in a reduced version. Within both Algorithms 2 and 3, which represent the main components of Algorithm 1, we disable modifications of the charging stations. Within Algorithm 2, we only allow the assignment of service trips to vehicles without charging or with detours to existing charging stations. The other two cases are omitted.