# Variable Neighborhood Search for the Two-Echelon Electric Vehicle Routing Problem with Time Windows
## 3 Problem Description and Mathematical Model  
Given is a directed graph \(G=(N,A)\) in which the set of nodes (\(N\)) is composed of the following four subsets: the set of central warehouses (\(N_{D}\)), the set of satellites (\(N_{S}\)), the set of charging stations (\(N_{R}\)), and the set of customers (\(N_{C}\)). The set of arcs (\(A\)) includes (1) arcs that connect central warehouses and satellites \(A1=\{(i,j)|i\
eq j\text{ and }i,j\in N_{D}\cup N_{S}\}\) and (2) arcs that connect satellites, customers and charging stations \(A2=\{(l,m)|l\
eq m\text{ and }l,m\in N_{S}\cup N_{R}\cup N_{C}\}\). In other words, \(A1\) contains the arcs of the first echelon, and \(A2\) contains the arcs of the second echelon. Traveling along an arc \((i,j\in A1)\), \((l,m\in A2)\), has a cost/distance of \(d1_{ij}\), \(d2_{lm}\). Each customer \(i\in N_{C}\) has a demand \(D2_{i}\) and a time window that indicates the earliest possible visiting time \(twe_{i}\) and the latest possible visiting time \(twl_{i}\). Two different fleets of vehicles, each one homogeneous in itself, serve in the first and second echelons in order to meet customer demands. A fleet of large trucks \(V1\) with internal combustion engines are located in the central warehouse and carry products from the central warehouses to the satellites, while a fleet of electric vehicles \(V2\) are present at the satellites and distribute products to customers (demand points). In the first echelon, a truck \(k\in V1\) starts its tour from a central warehouse, visits one or more satellites, and returns to the central warehouse from which the tour started. The total amount of deliveries may not exceed the load capacity \(Q1_{k}\) of vehicle \(k\). In the second echelon, an electric vehicle \(e\in V2\) starts its tour from a satellite, visits one or more customers and charging stations if necessary, and returns to the satellite from which the tour started. The total amount of deliveries cannot exceed the load capacity \(Q2_{e}\) of electric vehicle \(e\). A customer can only be served by one electric vehicle. An electric vehicle starts its tour with a fully charged battery (battery level \(BC_{e}\)) and the vehicle's battery is consumed in proportion to the distance traveled. If a charging station is visited, the electric vehicle's battery is fully charged up to level \(BC_{e}\) with a constant charging speed. Note that an electric vehicle may need to visit a charging station multiple times. Therefore, set \(N_{R}\) includes charging stations as well as copies of each charging station in order to allow multiple visits to any charging station. The idea of using such dummy vertices was introduced for the first time in [35] in order to permit multiple visits to intermediate satellites. Moreover, this approach was adopted in [11] for a green vehicle routing problem. Determining the number of copies of each charging station (\(\psi\)) is, however, not a trivial task. An insufficient number of copies may prevent finding an optimal solution due to not allowing a sufficient number of multiple visits of the same charging station. On the other hand, an unnecessarily large number of copies of each charging station would increase the model size, resulting in longer running times of the MILP solvers. As a result of preliminary experiments on various instance sets, we set \(\psi\) to 3. We developed a three-index node-based integer programming model for 2E-EVRP-TW. Including the vehicles as a third index ensures that the model may be used for instances that contain heterogeneous fleets with different vehicle characteristics. In the following, we first introduce the notations, sets and problem data used by the MILP model. Subsequently, the model is outlined in terms of the decision variables, the objective function and the constraints.