# A Two-Echelon Electric Vehicle Routing Problem with Time Windows and Battery Swapping Stations
## 4 Algorithms for the 2E-EVRPTW-BSS
### Neighborhoods and Local Search  
The proposed VNS of this paper adopted several frequently used inter- and intra-route neighborhood structures.  
2-Opt*. As a modification of the 2-opt operator originally proposed by [PERSON] [47], the 2-Opt* operator was applied to VRPTW by [PERSON] and [PERSON] [48]. For the two routes that depart from the same satellite, this operator replaces the arc \((i,l+1)\) of one route and arc \((j,j+1)\) of another route with arcs \((i,j+1)\) and \((j,l+1)\) (Figure 2(a)). With respect to 2E-EVRPTW-BSS, there is at least one BBS among the nodes \(i,i+1,j,j+1\) and no two successive BBSs in the generated routes, compared with the 2-Opt* operator in traditional problems in which only customers are swapped.  
Relocate. This operator deletes and replaces a node from one route and then inserts it into another route (Figure 2(b)) or another location in the same route (Figure 2(c)). It is performed only on the sequence of customers.  
Exchange. The exchange operator swaps the positions of two nodes, which is applied to customers. This operator can be used for both intra- (Figure 2(d)) and inter-route (Figure 2(e)) moves.  
Swap (\(\lambda_{1},\lambda_{2}\)). This operator swaps \(\lambda_{1}\) consecutive customers in one route with \(\lambda_{2}\) consecutive customers in another route (Figure 3f), or just swaps in the same route (Figure 3g).  
Shift \((\lambda_{1},0)\). This operator removes \(\lambda_{1}\) consecutive customers and inserts them into another position in the same route (Figure 3h) or another route (Figure 3i).  
Satellite-change. This operator was proposed by [PERSON] et al. [38]. Subject to the constraints on the second-echelon EVs per satellite, this operator exchanges the current satellite with another satellite and inserts the old satellite into a position of the route (Figure 3j).  
Figure 3: Neighborhoods for the proposed VNS.  
StationInRe. This operator, proposed by [PERSON] et al. [15], performs insertions and removals of BSS. This operator is applied to the arcs starting from a BBS \((k,j),k\in V_{B}\). If the arc \((k,j)\) does not belong to the current solution, the stationInRe will insert the BBS \(k\) between \(j\) and its predecessor, as depicted in Figure 3k. If the arc already exists, the BSS \(k\) will be removed, as shown in Figure 3l.  
The proposed VNS procedure in Algorithm 1 contains two phases to generate a neighborhood, i.e., shaking and local search. In the shaking phase, five inter-route neighborhood structures (2-Opt*, inter-Relocate, inter-Exchange, inter-Swap, and inter-Shift) and one intra-route neighborhood structure (Satellite-Change) are sequentially used to generate the neighborhood.  
In the local search phase, five intra-route neighborhood structures, i.e., intra-Relocate, intra-Exchange, intra-Swap, intra-Shift, and Station-InRe, are sequentially applied. Local search neighborhoods are performed in a cyclic manner [49]. Each neighborhood is explored until no further improvement can be found, then the next neighborhood structure is selected. When all the five neighborhood structures have been performed, the search process repeats again. The procedure terminates when the local optimum is reached in every single neighborhood.