rapid_solve::heuristics

Module tabu_search

Source
Expand description

This module contains the TabuSearchSolver implementing the tabu search metaheuristic. There are several tabu_improvers (neighborhood exploration stategies) to choose from.

  • This solver requires a TabuNeighborhood, which, in comparison to a regular Neighborhood, requires a tabu list as an additional argument and returns in addition to the neighbors a list of tabus that should be added to the tabu list.
  • Starts with an initial solution and iteratively explores the neighborhood of the current solution, while ignoring tabu solutions.
  • The best non-tabu neighbor, even if it is worse than the current solution, is chosen.
  • Each neighbor is paired with a list of tabus that should be added to the tabu list.
  • A good tabu should forbid to return to the previous solution.
  • The list of tabus is limited in size, and the oldest tabus are removed when the list is full.
  • The search stops after a certain number of iterations, after a certain time limit, or if no global improvement is found after a certain number of iterations.
  • The best solution seen is returned.

For examples, see the tabu search solver for the TSP.

Modules§

Structs§

Traits§

  • Defines a neighborhood for a tabu search. Compared to a regular neighborhood, a tabu neighborhood takes a tabu list as an additional argument and returns in addition to the neighbors a list of tabus that should be added to the tabu list.