# Variable Neighborhood Search for the Two-Echelon Electric Vehicle Routing Problem with Time Windows
## 4 Solution Approach
### Initial Solution Construction  
The VRP literature offers numerous heuristic approaches in order to construct initial solutions to different VRP variants. The Clarke and Wright (C&W) savings algorithm is one of the most commonly used methods because of its simplicity, performance, and ease of adaptation to different problem variants. This study proposes a savings-based initial solution construction algorithm that considers the multi-tier transportation structure and additional constraints (capacity, battery, and time windows) of the 2E-EVRP-TW. Algorithm 1 provides a high-level pseudo-code of this procedure. First, each customer is assigned to the nearest satellite. After this assignment, set \(N_{C}^{s}\subseteq N_{C}\) contains all customers assigned to satellite \(s\), for all \(s\in N_{S}\). Note that, with this assignment, an indirect time window arises for each satellite based on the customer's time windows. Assume, for example, that goods are transported from central warehouse 0 to satellite \(s\), and then from satellite \(s\) to customers \(i\) and \(j\), that is, \(i,j\in N_{C}^{s}\). As illustrated in Figure 2, the electric vehicle must depart from satellite \(s\) before a certain time in order to be able to visit customers within their time windows. Therefore, the large truck in the first echelon must deliver goods to satellite \(s\) no later than \(t\text{v}l_{s}:=\min\{t\text{v}l_{v}-d2_{sv}\mid v\in N_{C}^{s}\}\) such that the electric vehicle is able to visit customer \(i\) and \(j\) before \(t\text{v}l_{i}\) and \(t\text{v}l_{j}\), respectively. After calculating time windows for each satellite, first, the routes for the large vehicles in the first echelon and, second, the routes for the electric vehicles in the second echelon are constructed using the savings heuristic. In the following, we explain the steps for constructing the routes for the electric vehicles in the second echelon. In particular, for each satellite \(s\in N_{S}\) the following steps are applied:  
Figure 2: An illustration of the indirect time windows arising for a satellite depending on the customers it must serve. Note that time windows are indicated in green color. A set of direct routes \(R2=\{(s-i-s)\mid i\in N_{\mathbb{C}}^{s}\}\) is created. However, note that not all of these single-customer tours are necessarily battery feasible. If this occurs, a charging station with the minimum insertion cost is inserted into the route. To achieve this, first, for each charging station \(r\in N_{R}\) the cost \(C_{insert}(r)\) of inserting \(r\) between satellite \(s\) and customer \(i\) is calculated as \(C_{insert}(r)=d2_{sr}+d2_{ri}-d2_{si}\). Then, a charging station \(r^{\prime}\in N_{R}\) such that \(C_{insert}(r^{\prime})\leq C_{insert}(r)\) for all \(r\in N_{R}\) is inserted into the infeasible route. Only one charging station is allowed to be inserted to fix infeasibility. In the unique case that the battery infeasibility cannot be eliminated despite charging station insertion, the relevant tour is removed, and the customer in the tour is added to the initially empty list of unvisited customers \(L_{u}\). 2. Subsequently, a savings list formed by all possible pairs of nodes (customers and charging stations) together with their respective savings values is generated. A pair of nodes \((i,j\in N_{\mathbb{C}}\mid i\
eq j)\) must fulfill the following conditions to be included in the savings list: (1) node \(i\) and node \(j\) must belong to different routes, and (2) both \(i\) and \(j\) must be directly connected to the satellite in the route to which they belong. With regard to the calculation of the savings value \(s2_{ij}\) for two nodes \(i\) and \(j\), the literature offers various enhancements and extensions.