The Adaptive Configuration-Aware Simulated Annealing (ACSA) algorithm is designed to solve the MDGP by integrating novel neighborhood moves within a simulated annealing framework.
General Framework:
ACSA's general framework is presented in Algorithm 1.
- Initialization: An initial solution π is randomly generated, and the best solution found so far, π*, is set to π. Initial and final temperatures (Tinit and Tfinal) are determined using a bisection method based on target percentages Pinit and Pfinal.
- Search Procedure: The algorithm enters a main loop that continues until the elapsed time exceeds a predefined timelimit.
- Temperature Setting: At the beginning of each outer loop, the current temperature T is set to Tinit.
- Configuration-Aware Simulated Annealing (CSA): An inner loop runs for a maximum number of iterations Iin.
- Vertex Selection: In each inner iteration, a vertex v is randomly selected from the set of all vertices V.
- Relaxation-Based Insertion (RBI): The algorithm first attempts a relaxation-based insertion move for vertex v. This move temporarily relaxes capacity constraints to explore a wider neighborhood.
- Memory-Based Swap (MBS): After the insertion move, the algorithm switches to a memory-based swap procedure for vertex v. This mechanism selectively reuses cached suboptimal swap candidates to balance diversification and intensification.
- Solution Update: If the new solution from either RBI or MBS yields a better objective value than the current best solution π*, then π* is updated.
- Temperature Cooling: After each inner loop, the temperature T is decreased by a cooling factor λ.
- The outer loop continues until T falls below Tfinal.
- Return Best Solution: After the search procedure, the algorithm returns the best solution π* found.
Relaxation-based Insertion (RBI):
This strategy addresses the limitations of strict capacity constraints. It introduces a two-stage feasibility check:
- Standard Constraint Check: An insertion move is considered feasible if both the involved groups (Cold and Cnew) satisfy their original capacity constraints after the insertion.
- Lnew ≤ |Cnew + 1| ≤ Unew
- Lold ≤ |Cold - 1| ≤ Uold
- Relaxed Constraint Check: If the standard constraints are not met, the fixed capacity bounds are relaxed by interchanging the upper and lower bounds between the two groups. The move is still considered valid if the resulting group sizes satisfy the updated capacity constraints and the move obtains a positive objective gain.
- Lold ≤ |Cnew + 1| ≤ Uold
- Lnew ≤ |Cold - 1| ≤ Unew
- Δ ≥ 0
The algorithm evaluates all groups that satisfy either the standard or relaxed constraint and selects the one with the maximum objective gain.
Memory-based Swap (MBS):
MBS enhances search diversification and reduces evaluation overhead by reusing cached suboptimal swap candidates.
- Cached Partner Check: The algorithm first checks if a cached swap partner u exists for vertex v and if its target group (toGroup[v]) matches the current group of u (γ(u)).
- Re-evaluation or Direct Calculation:
- If the cache is invalid (no partner stored or group mismatch), the algorithm finds the best swap partner u for v from other groups based on objective gain and updates the cache (vSwap[v] = u, toGroup[v] = γ(u)).
- If the cache is valid, the gain of swapping v and u is directly calculated.
- Solution Update: If the swap move is accepted (based on simulated annealing probability), the cached entries for both v and u are cleared, and the solution π and auxiliary data structure W are updated.