Tabu Search is a metaheuristic that guides local search procedures to explore solution spaces beyond local optimality. It maintains a tabu list - a short-term memory of recently visited solutions or moves to prevent cycling. Key components: (1) neighborhood structure defining candidate moves; (2) tabu list storing forbidden moves for a tenure period; (3) aspiration criteria allowing tabu moves if they lead to best-known solutions; (4) intensification strategies to search promising regions thoroughly; (5) diversification strategies to explore new regions. Advanced features include: long-term memory, strategic oscillation, and path relinking. Applications include: scheduling, routing, facility location, and telecommunications network design.

The Transportation Problem is a special linear programming problem for optimizing shipment from sources (suppliers) to destinations (consumers) at minimum cost. Given: m sources with supplies sᵢ, n destinations with demands dⱼ, and unit transportation costs cᵢⱼ. Objective: minimize Σᵢ Σⱼ cᵢⱼxᵢⱼ subject to: Σⱼ xᵢⱼ = sᵢ (supply constraints), Σᵢ xᵢⱼ = dⱼ (demand constraints), xᵢⱼ ≥ 0. The problem has a totally unimodular constraint matrix, ensuring integer optimal solutions. Solution methods include: Northwest corner rule, Vogel's approximation method, and the transportation simplex algorithm. Extensions include: transshipment problems and assignment problems.

The Traveling Salesman Problem seeks the shortest tour visiting each city exactly once and returning to the starting city. Given n cities with distances dᵢⱼ, find permutation π minimizing Σᵢ₌₁ⁿ d(π(i),π(i+1)). TSP is NP-hard with n!/2n possible tours. Exact methods include: branch and bound, dynamic programming (Held-Karp O(n²2ⁿ)), and integer programming formulations (subtour elimination constraints). Heuristics include: nearest neighbor, 2-opt, 3-opt, Lin-Kernighan, Christofides algorithm (1.5-approximation for metric TSP). Variants include: asymmetric TSP, multiple TSP, and vehicle routing problem. TSP applications extend beyond routing to: circuit board drilling, genome sequencing, and scheduling.