# A Multi-Strategy ALNS for the VRP with Flexible Time Windows and Delivery Locations
## 4 Multi-Strategy ALNS with a Simulated Annealing Mechanism
### The Adaptive Mechanism  
For the selection of different removal and insertion operators, a roulette mechanism is used. For all operators, the initial score is set to 1, and the score of different operators is increased according to the use of operators in each search process. It should be noted that the probability of selecting different operators depends on their score. The scores of the operators used to generate \(s_{cur}\) are updated based on the outcome, using the following reward scheme designed to favor operators that lead to better solutions:  
1. If \(s_{cur}\) is a new global best solution (\(z(s_{cur})<z(s_{global})\)), the operators involved receive the highest reward \(\phi_{1}\).
2. If \(s_{cur}\) improves upon the current local best (\(z(s_{cur})\leq z(s_{local})\)) but is not a new global best, they receive \(\phi_{2}\).
3. If \(s_{cur}\) is worse than \(s_{local}\) (\(z(s_{cur})>z(s_{local})\)) but is still accepted by the SA criterion, they receive \(\phi_{3}\).
4. If \(s_{cur}\) is worse and not accepted, they receive the lowest reward \(\phi_{4}\).  
The operator score is updated at the end of each iteration interval, with the interval length being 50 generations. While retaining appropriate historical experience, the search test of the previous iteration interval is fully considered. The updated formula is as follows:  
\[\rho_{i+1}=(1-\gamma)\bullet\rho_{i}+\gamma\bullet\Phi_{i} \tag{16}\]  
where \(\rho_{i+1}\) represents the scores of operators for the \(i+1\) iteration interval, \(\Phi_{i}\) represents the scores accumulated by the operators between the corresponding \(i\) iteration intervals, and \(\gamma\in[0,1]\) represents the decay factor. The selection weights of different operators are calculated as follows during each iteration search:  
Figure 6: An illustration of the VRP-CS. (**a**) Customer–locations table. (**b**) Index of insertable positions and removal set. (**c**) An illustration of the calculation of the insertion cost for customer H.  
\[\omega=\phi/(\sum_{\phi\in\Phi}\phi) \tag{17}\]  
where \(\omega\) represents its weight, \(\phi\) represents its score, and \(\Phi\) represents the set of operators of the same type.  
To balance exploration and exploitation within each iteration, MSALNS performs a dual search. It executes _pop_ sub-searches where removal/insertion operators are chosen with equal probability, and another _pop_ sub-searches where operators are chosen adaptively based on their current weights (calculated using Equation (17) from scores updated via Equation (16)), where _pop_ is a parameter defining the number of searches per strategy. The best solution found among all \(2\cdot pop\) generated neighbors become the candidate solution \(s_{cur}\) for potential acceptance. Furthermore, to prevent the search from stagnating, if the global best solution \(s_{global}\) has not improved for \(U_{gap}\) iterations, the simulated annealing temperature \(T\) is reset to its initial value \(T_{0}\), increasing the likelihood of accepting diversifying moves.