# A Multi-Strategy ALNS for the VRP with Flexible Time Windows and Delivery Locations
## 4 Multi-Strategy ALNS with a Simulated Annealing Mechanism  
The VRP-CS involves flexible delivery times and locations, which increases the complexity of the problem. As shown in Section 2.2, ALNS and its variants have demonstrated strong performance in solving complex VRP. This paper adopts ALNS as the base framework and proposes an improved algorithm, MSALNS, tailored to the VRP-CS. In this approach, neighborhood structures are designed from the perspective of customer satisfaction, which expands the search space and enhances solution performance. In addition, a multi-annealing mechanism is introduced to prevent the algorithm from falling into local optima too early, thereby improving solution quality.  
Figure 3 introduces the structure of MSALNS. Construct the initial solution by greedy insertion. Based on the initial solution, MSALNS performs removal and insertion actions on the current solution to obtain the neighborhood solution. Then, when the neighborhood solution is improved, it accepts the neighborhood solution and updates the scores of different operators.  
Figure 2: Distribution of customer satisfaction.  
The algorithm determines the selected removal and insertion operators based on the different scores in each generation of search. When the neighborhood solution is not improved, the solution is accepted by simulated annealing strategy. Simulated annealing is a commonly used adaptive mechanism in ALNS [40; 41; 42; 43], as shown in Section 4.4. Compared to other adaptive strategies, the simulated annealing approach effectively balances simplicity and efficiency. Its mechanism is straightforward and clear, while also effectively controlling the LNS in selecting different neighborhood structures. This ensures high search efficiency and helps avoid getting trapped in local optima, thus ensuring the quality of the solution.  
In order to improve the ability of the algorithm to jump out of the local optimal solution, the following new strategies are designed:  
* If the number of times (\(c_{ui}\)) that the solution has not been updated reaches the threshold \(U_{ui}\), a random removal operator and a random repair operator are selected to destroy the current solution on a larger scale.
* If the number of times (\(c_{gap}\)) that the simulated annealing reaches the threshold \(U_{gap}\), \(T\) is reinitialized as \(T_{0}\) to increase the probability of accepting a poor solution.
* In each generation of the search, equal weights and adaptive weights based on operator scores are applied. Both methods perform the search, and the better solution is accepted. The main improvements of the proposed algorithm are as follows:
* Design of different operators (e.g., satisfaction-based Shaw removal, worst-route satisfaction removal, location-related removal, sequence-related removal, and satisfaction-based best insertion) to enrich the neighborhood structure, as shown in Section 4.3.
* Adoption of a dual-weight local search strategy to balance the influence of historical and recent performance in selecting neighborhood structures, as shown in Section 4.4.
* A simulated annealing-inspired acceptance criterion is designed, and a temperature adaptation strategy is proposed, which allows the temperature to rise when the search becomes stagnant, thus preventing the algorithm from prematurely converging to local optima.  
Figure 3: An illustration showing the structure of MSAINS.