## 3 Problem Description and Cost Model
### Savings Algorithm for Generating Initial Solutions  
The savings algorithm was first introduced by [PERSON] and [PERSON] [30] to solve VRPs heuristically. The objective of vehicle routing is to determine an optimal set of routes seeking to service a number of customers with a fleet of vehicles. Following [PERSON] et al. [31], the savings algorithm is one of the most commonly used methods for vehicle routing in practice. Starting from routes each containing one customer the basic procedure is to compute cost savings iteratively for merging two routes into the same one. Within each iteration the merging that results in the highest saving is performed. A saving consists of fixed and operative costs saved. This procedure terminates when no further mergings can be performed. While this algorithm has been applied generally to VRPs, we adapt this algorithm hereinafter in order to apply the same procedure to the E-VSP-LP. Algorithm 2 shows the procedure for generating initial solutions to the E-VSP-LP formally using the idea of cost savings. The set of scheduled service trips to be assigned and an initial set of charging stations, together with their locations, serve as the input data. The algorithm begins by adding a vehicle rotation for each scheduled service trip, now containing only the associated trip together with a deadhead trip from and to the depot (I. 4). If these vehicle rotations are not feasible for BEBs the entire optimization problem is infeasible. Within each iteration of the algorithm those two vehicle rotations (I. 7 and 8) are merged that lead to a feasible rotation and entail the highest saving. Therefore, the set of service trips of both rotations to be merged are processed consecutively, in order of departure times (I. 9). Since the SoC mostly influences the feasibility of a vehicle rotation besides temporal restrictions the algorithm aims at adding charging procedures as often as possible. For this purpose, starting with a new and empty vehicle rotation (I. 10), four different cases are considered for each service trip of the rotations to be merged. First, we check whether a charging procedure can be performed at an existing charging station of \(S\) before executing the current service trip, taking into account necessary deadhead trips (I. 12). If this can be done, necessary deadhead trips, the charging procedure, and the service trip are added (I. 13). If this is not possible, we examine whether the current service trip can be executed without detours to charging stations (I. 14). If the SoC is insufficient, we check whether the current service trip can be executed by building a new charging station at the trip's departure stop and performing a charging procedure (I. 16). Lastly, the same is checked but for the latest position of the vehicle, which is less strict because the deadhead trip is executed after the charging procedure (I. 18). If none of these options can be carriedout, the current merging is aborted (l. 20). When a merging is feasible, the saving for merging two vehicle rotations \(v,w\in V\) into a new rotation \(\overline{v},\overline{w}\) is given by  
\[s(v,w)=c_{fix}^{plus}-\delta\cdot c_{fix}^{charging}-(o(\overline{v},\overline{w })-o(v)-o(w)) \tag{2}\]  
where \(o(v)\geq 0,\ \forall v\in V\) denotes the operational costs for each vehicle rotation and \(\delta\in\mathbb{N}\) the number of additionally respectively fewer needed charging stations. After each iteration the merging is performed that involves the highest positive saving (l. 25). Then, the set \(S\) of charging stations is modified, the new vehicle rotation is added, and the rotations merged are removed (l. 26 and 27). If no positive savings exist, the algorithm terminates and returns the sets of vehicle rotations and charging stations (l. 29). Hence, solutions generated by this procedure are always feasible. The procedure of Algorithm 2 is based on the heuristic solution method proposed for the E-VSP by [PERSON] and [PERSON] [20].