1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| Step 1 (Initial solution)
Find an initial solution using a basic local search algorithm as
proposed in [2].
Step 2 (Tabu Search)
Repeat Steps 2.1 to 2.2 for Number Iterations iterations
2.1 (Explore the neighborhood)
2.1.1 Determine the best move while taking into
consideration the tabu moves and the aspiration
criteria. For each move x → x, we find the
solution by solving GPU(x). The cost of the
solution is the total cost of the network.
2.1.2 Determine the number of iterations (according
to a uniform distribution) for which the chosen
site is tabu.
2.2 (TS best solution update)
If the cost of the current solution is less than the cost of
the best solution found so far, update this best solution.
Step 3 (Multi-start)
3.1 (Update the solution)
If the cost of the current solution is less than the cost of
the best solution found so far, update this best solution.
3.2 (Stop condition)
If the number of start is smaller than the maximum
allowed number of starts go to step 2. Otherwise, return
the best cost found so far.
Fig. 2. Tabu search algorithm |
Partager