## 3 Problem Description and Cost Model
### Savings Algorithm for Generating Initial Solutions
The number of vehicles as well as charging stations used is lower in almost all cases. This leads to significant cost savings up to 4.68% compared to the best solution found for one of the two sequential approaches. On average, savings of 1.17% over all instances and battery capacities can be observed. The same total costs are achieved in only one case. Furthermore, the more vehicles are used, the higher the cost savings are. For this reason, the cost savings generally decrease when the battery capacities increase. It is worth noting that the clarified statements would also hold true for exact solution methods for the E-VSP-LP. Exact solving would even strengthen the results because of the expected lower total costs. Figure 3 illustrates the key statements made within this chapter. The figure provides an overview of the total costs obtained by the different solution approaches presented for the instances t1060_s209, t1135_s101, and t3067_s209 and for all battery capacities. The instances are chosen among all instances presented since they cover characteristic problem sizes and distributions of cumulative service trips over the day. Comparable behavior is to be expected for instances with similar characteristics not shown here. It is important to note that the total costs are only specified for feasible solutions. \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Instance**} & \multirow{2}{*}{ \begin{tabular}{c} **Battery** \\ **Cap.(\&Wh)** \\ \end{tabular}  } & \multicolumn{6}{c}{**Complete Chargings**} & \multicolumn{6}{c}{**Partial Chargings**} \\ \cline{3-10}  & & \multicolumn{2}{c}{**\# Vehicles**} & \multicolumn{1}{c}{**\# Stations**} & \multicolumn{1}{c}{**Operat**} & \multicolumn{1}{c}{**Tot. Costs**} & \multicolumn{1}{c}{**\# Vehicles**} & \multicolumn{1}{c}{**\# Stations**} & \multicolumn{1}{c}{**Operat. **} & \multicolumn{1}{c}{**Tot. Costs**} \\ \hline  & 60 & 79 & 6 & 1.317 & 30.46 & 77 & 4 & 1.348 & 29.29 (\(-1.17\)) \\ t876\_s207 & 120 & 76 & 3 & 1.334 & 30.57



#### 5.4.3 Convergence Analysis

The experiments were performed on a common desktop computer (Intel(R) Core(TM) i7-6700 HQ @CPU 2.60 GHz 2.59 GHz, 16 GB RAM). The solution method is implemented in Java. The computational analysis was carried out using Python 3.10. Figure 4 provides an overview of the convergence behaviour for all problem instances solved by Algorithm 3. In order to facilitate comparison between the different instances, the total costs obtained are normalized. Each figure contains data for the first 20.000 runs. For none of the instances solved a total run time of 10 h was exceeded. The results basically prove reasonable convergence behaviours towards the minimum total costs for all instances. However, particular differences between the instances can be observed. The lower the number of service trips, the faster the total costs obtained by Algorithm 3 decrease. It is noteworthy that the number of stop points has no visible influence on the speed of convergence. Figure 3: Overview of total costs obtained by the different solution approaches presented for all battery capacities. ## 6 Conclusions

We have introduced a novel solution method for simultaneous optimization of location planning of charging stations and vehicle scheduling for BEBs in public transport. To do so, we introduced the E-VSP-LP, which extends the standard E-VSP to incorporate location planning of charging stations. To solve the problem we developed a metaheuristic solution method based on VNS, as both problems are difficult to solve. To generate the necessary initial solutions we adapted the traditional savings algorithm. To evaluate the solution approach we performed a computational study based on real-world public transport data, with up to 3000 service trips and different battery capacities of the buses deployed.