# The Electric Vehicle Routing Problem with Time Windows, Partial Readers, and Parcel Lockers
## 4 Solution Method
### Removal and Insertion Algorithms
#### 4.4.1 Customer Removal and Insertion  
Customers are removed from the solution by three removal operators, while they are re-inserted into the solution by three insertion operators based on array 1 of the solution representation (denoted by _customerRemovalInsertion_()). The customer removal and insertion algorithms are selected in an adaptive manner [53]. The probabilities of selections are re-computed by a smoothing rate \(\omega^{prob}\) after a learning period (i.e., \(\eta^{proba}\) iterations). During a learning period, when a new solution is generated, the associated removal and insertion algorithms are rewarded based on their performance. The rewards, denoted as \(\epsilon_{f},\epsilon_{b},\epsilon_{i}\), and \(\epsilon_{w}\), correspond to different scenarios, which are gained when a new best feasible solution, a new best solution (which may be infeasible), a solution improving the current solution, and a worse solution, respectively, are found. For each customer removal operator, \(\eta^{rem}\) customers are removed. The number of removed customers \(\eta^{rem}\) is randomly selected within a range \(\eta^{rem}\in[1,|C|]\). The following removal operators are implemented in our ALNS:  
* Random removal randomly removes \(\eta^{rem}\) customers from a given solution. * Worst removal is adopted by ref. [53], which iteratively removes the customer that increases the generalized total cost the most, defined by \(\Delta f_{gen}=f_{gen}^{a}-f_{gen}^{b}\), where \(f_{gen}^{b}\) and \(f_{gen}^{a}\) represent the generalized costs before and after removing the customer, respectively. Moreover, to avoid being trapped at local optimum points, we consider randomness by controlling a randomness level \(\delta^{noise}\). Instead of choosing the highest cost reduction, the \(\lfloor r^{\delta^{noise}}\rfloor L^{worst}\rfloor\)-th highest cost reduction is then selected for removal from the solution, where \(r\) is a random variable drawn from a uniform distribution \(U[0,1]\), and \(L^{worst}\) is a list of customers sorted in descending order by the cost reduction. * Shaw removal was first introduced in [56] and aims to remove customers that are similar to each other with respect to four criteria (i.e., travel distance, time window, demand, and delivery method). The procedure begins by randomly removing a customer and storing it in a list (denoted by \(L^{shur}\)). The removal process is then repeated until \(\eta^{rem}\) customers are removed. At every iteration, a customer \(j\) in the route is selected for removal based on its relatedness to a randomly chosen customer \(i\) from the list \(L^{shur}\). The relatedness between customers \(i\) and \(j\) is evaluated using the following equation: \[\mathcal{R}(i,j)=\phi_{1}d_{ij}+\phi_{2}|q_{i}-q_{j}|+\phi_{3}|e_{i}-e_{j}|+ \mathcal{P}(i,j)\] Here, the four terms correspond to the relatedness of travel distance, the earliest time, demand, and delivery method, respectively. For the first three terms, each criterion is weighted by \(\phi_{1},\phi_{2}\), and \(\phi_{3}\), respectively. In addition, \(\mathcal{P}(i,j)\) equals 0 if both customers are assigned the same delivery method (either home delivery or self-pickup method) and 1 otherwise. We note that a lower \(\mathcal{R}(i,j)\) represents more relatedness between customers \(i\) and \(j\). For each insertion operator, the set of absent customers due to the removals is re-inserted into the solution. Infeasible solutions in terms of time windows, load, and battery are taken into account by the generalized objective function (see Section 4.2). The insertion operators are briefly described as follows. * Greedy insertion is adopted by ref. [48] and iteratively selects a customer from the list of absent customers with the best insertion for inserting into the solution until all customers are re-inserted. In each iteration, the customer with the best insertion is determined based on the increase in the generalized objective value.