# A Multi-Strategy ALNS for the VRP with Flexible Time Windows and Delivery Locations
## 4 Multi-Strategy ALNS with a Simulated Annealing Mechanism
### The Search Mechanism
#### 4.3.1 Removal Operators  
The removal operators destroy the structure of a part of the solution by selecting it randomly or based on a specific criterion. In this way, a certain amount of \"free space\" is created for subsequent optimization.  
MSALNS can achieve a sizable neighborhood using a variety of removal operations. After removal, customers are placed in the request bank. The removal operator selects \(\Gamma=\tau\cdot m\) customers from the current solution to perform removal. Then, the current solution becomes a partial solution. Figure 5 is an illustration of removal operators.  
MSALNS uses some of the operators that are widely used in the VRP with time windows problems. Specifically, random removal [44], time-related removal [45], random route removal [44], route removal [46], worst cost removal [47], zone removal [48]. MSALNS adjusts these operators according to the characteristics of the VRP-CS.  
However, these operators do not consider the characteristics of the VRP-CS, optional delivery locations, and customer satisfaction. Moreover, they do not take full advantage of the degree of similarity between different delivery routes. Therefore, in order to expand the search space, improve the search performance, and the ability of the algorithm to jump out of the local optimal solution, MSALNS presents the following new operators:  
* **Satisfaction Shaw Removal:** In this destruction operator, a reference customer location \(i^{a}\in L_{i}\) is first randomly selected, and then the similarity between the other locations in the current solution and \(i^{a}\) is calculated. Then, it deletes \(i^{a}\) and a number of locations that are most similar to \(i^{a}\) until \(\Gamma\) locations are deleted. Specifically, for the current location \(j^{b}\in L_{j}\), the relationship \(R(i,a,j,b)\) between the two is calculated as follows: \[R(i,a,j,b)=\alpha_{1}\bullet d_{i\alpha jb}+\alpha_{2}\bullet\left|q_{i}-q_{ j}\right|+\alpha_{3}\bullet\left|e_{ia}-e_{jk}\right|+\alpha_{4}\bullet\left|e_{ia}-e_{ jk}\right|+\alpha_{5}\bullet l_{ij}\] (15) where \(d_{i\alpha jb}\) represents the distance between delivery options \(a\) and \(b\); \(q_{i}\) and \(q_{j}\) represent the demand of customer \(i\), \(j\); \(e_{ia}\) represents the customer satisfaction of customer \(i\) receiving service at \(a\); \(e_{jk}\) represents the customer satisfaction of customer \(j\) receiving service at \(b\); \(l_{ij}\) indicates whether customer \(i\) and \(j\) are delivered by the same vehicle; if so, \(l_{ij}=-1\); otherwise \(l_{ij}=1\). \(\alpha_{1}\alpha_{2}\alpha_{3}\alpha_{4}\alpha_{5}\) are the weight of each parameter in the formula. A lower \(R(i,a,j,b)\) indicates a greater similarity between customers.
* **Worst Route Satisfaction Removal:** This operator calculates the total satisfaction of each route from the perspective of the route, selects the route in ascending order, and deletes all locations with low satisfaction until the number of locations removed reaches \(\Gamma\).
* **Location Related Removal:** This operator preferentially removes customers with similar optional locations.
* **String Related Removal:** This operator uses the distance between locations as a basis for judgment. First, a customer location is randomly selected as a reference location, and \(\lfloor\Gamma/2\rfloor\) nearest points to it on the same route are deleted. Then, it selects a nearest point that is not on the same route and deletes \(\lfloor\Gamma/2\rfloor\) nearest point to it on that route.