Tabu Search

Local search with a memory of recently visited moves to avoid cycling.

Also called: Tabu Search · TS · 금기 탐색

A local search augmented with short-term memory. It forbids recently made moves for a while (the tabu list) to prevent immediate reversal and cycling, and accepts even worsening moves to escape local optima; an aspiration criterion overrides the ban when a forbidden move is good enough. Applied to the sequence and placement search of 2D Bin Packing, Strip Packing, and 2D Irregular Nesting.

Claims & evidence

Every relationship is a claim with an evidence grade; applicable problem-to-problem relationships also carry an equivalence level. See the evidence policy.

A–X describes evidence reliability; E0–E4 describes mathematical similarity between problems. The two axes are independent.

Relationships to this entry 3

uses method
2D Bin Packing to Tabu Search
2D bin packing has also been reported with tabu-search-based search.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method
2D Irregular Nesting to Tabu Search
Irregular nesting has also been reported with tabu-search-based search, using a placement heuristic as the inner loop.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: B — Survey / tutorial / communityA tutorial in irregular shape packing problems
  Citation details
  Bennell, J.A., Oliveira, J.F. (2009). A tutorial in irregular shape packing problems. JORS 60(S1):S93-S105.
uses method
2D Strip Packing to Tabu Search
Strip packing has also been reported with tabu-search-based search.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.

Relationships to this entry
Relationship	Claim	Evidence	Equiv.	Sources
uses method 2D Bin Packing to Tabu Search	2D bin packing has also been reported with tabu-search-based search.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method 2D Irregular Nesting to Tabu Search	Irregular nesting has also been reported with tabu-search-based search, using a placement heuristic as the inner loop.	B · Survey / tutorial / community	—	Source grade: B — Survey / tutorial / communityA tutorial in irregular shape packing problems Citation details Bennell, J.A., Oliveira, J.F. (2009). A tutorial in irregular shape packing problems. JORS 60(S1):S93-S105.
uses method 2D Strip Packing to Tabu Search	Strip packing has also been reported with tabu-search-based search.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.