## 3 Problem Description and Cost Model
### Savings Algorithm for Generating Initial Solutions
As the total costs of a solution consist of operational costs for deadheading as well as fixed costs for vehicles and charging stations, Algorithm 5 combines the three following Algorithms 6-8, each aiming towards reducing one cost component. In Algorithm 5, the move is performed that involves the highest cost saving. ```
1:Input: neighborhood \(N_{k}\), objective function \(f\)
2:Output: neighborhood \(N_{k}\)
3:return\(\min_{f}\{EXST(N_{k}),SST(N_{k}),SCP(N_{k})\}\);
```

**Algorithm 5**BESTIMPROVEMENT. Algorithm 6 is used to reduce operational costs for deadheading by exchanging service trips between different vehicle rotations of a corresponding neighborhood. Therefore, a saving is computed for each pair of service trips for the neighborhood's set of vehicles that can be exchanged, and the move with the highest saving is returned. ```
1:Input: neighborhood \(N_{k}\)
2:Output: neighborhood \(N_{k}\)
3:for all\(v\in V\setminus\{v\}\)do
4:for all\(t_{v}\in v\)do
5:if\(t_{v}\) and \(t_{w}\) can be exchanged then
6: Compute saving;
7:endif
8:endfor
9:endfor
10:endfor
11:endfor
12: Perform exchange with the highest saving;
13:return\(N_{k}\);
```

**Algorithm 7**A NEIGHBORHOODCHANGE. Algorithm 7 aims at inserting service trips of vehicle rotations with a lower number of service trips into vehicle rotations with a higher number of service trips, again based on a neighborhood. If an insertion is possible, a saving is computed containing proportionate fixed costs for the remaining service trips, fixed costs for additional charging stations, and operational costs for possible detours. Again, the best move found is returned. The algorithm attempts to omit vehicle rotations whereby no service trips are being executed any more. ```
1:Input: neighborhood \(N_{k}\), fixed costs for an BEB \(c_{fix}^{bus}\)
2:Output: neighborhood \(N_{k}\)
3:for all\(v\in V\)do
4:for all\(w\in V:|ST_{w}|<|ST_{v}|\)do
5:for all\(t_{w}\in w\)do
6:if\(t_{w}\) can be inserted in \(v\)then
7: Compute saving \((c_{fix}^{bus}/|ST_{w}|)\) less the costs for newly built charging stations
8: and additional operational costs;
9:endif
10:endfor
11:endfor
12: Perform move with the highest saving, omit a vehicle if no trips are being performed;
13:return\(N_{k}\);
```

**Algorithm 7** Shift Service Trips (SST). Algorithm 8 aims at decreasing the number of charging stations used by moving charging procedures from less frequented charging stations to higher frequented charging stations, considering the vehicle rotations of a neighborhood. The move is returned that is feasible and entails the highest saving including proportionate fixed costs for remaining charging procedures at a specific charging station and operational costs for additional detours. Similar to Algorithm 7, this procedure aims at omitting charging stations where chargings are no longer being performed at a specific stop point. ```
1:Input: neighborhood \(N_{k}\), charging stations \(S\)
2:Output: neighborhood \(N_{k}\), charging stations \(S\)
3:
4:Sort \(S\) by the number of charging procedures performed within the entire set of vehicle rotations in ascending order;
5:for\(s=1\)to\(|S|-1\)do
6:for all\(t=|S|\)to\(s+1\)do
7:if A charging of a vehicle in \(N_{k}\) is performed at \(s\) and can be shifted to \(t\)then
8: Compute saving \((c_{fix}^{ charging}/|CP_{s}|)\) less additional operational costs;
9:endif
10:endfor
11:endfor
12: Perform move with the highest saving, omit a charging stations if no chargings are being performed;
13:return\(N_{k}\), \(S\);
```

**Algorithm 8** Shift Charging Procedures (SCP). While stochastic influences on incumbent solutions are already incorporated by the random selection of a neighborhood's set of vehicles, the Algorithm 9 is applied additionally within Algorithm 3. This approach is intended to enable more stochastic changes to the procedure aiming to escape from local optima. Shaking is based on the procedures given by Algorithms 6-8. Within each method call of Algorithm 9, one of the three algorithms is randomly applied if the corresponding move is feasible.