Multi-objective Tabu Search (MOTS) — Metaheuristic for Pareto-optimal solutions
- Introduced by
- Hansen, M. P.; building on Glover (1989) Tabu Search
- Year
- 1997
- Type
- Metaheuristic multi-objective optimization
- Family
- Simulation / optimization
What does it do?
Multi-objective Tabu Search (MOTS) is a metaheuristic algorithm that extends the classic Tabu Search framework to simultaneously optimize two or more conflicting objective functions.
Instead of a single optimum, it seeks to approximate the Pareto front — the set of solutions where no objective can be improved without worsening another — making it suitable for complex combinatorial and continuous optimization problems in engineering, logistics, and operations research.
The intuition behind the method
Imagine exploring a rugged landscape with many hills and valleys, but you have several maps showing different terrains (one per objective) that contradict each other. MOTS navigates this space by moving to neighboring solutions, keeping a short-term memory list (the tabu list) of recently visited spots to avoid cycling, and maintaining an archive of non-dominated solutions found so far. Periodically, strategic diversification pushes the search into unexplored regions of the Pareto front, balancing exploitation of promising areas with global exploration.
History
Multi-objective Tabu Search extends the single-objective Tabu Search introduced by Fred Glover in 1989. The first systematic MOTS formulation — including Pareto archiving and multi-objective aspiration criteria — was presented by M. P. Hansen at the 1997 MCDM conference. Subsequent work by Gandibleux, Teghem, and others formalized variants for combinatorial problems, and MOTS has since been applied to scheduling, logistics, and engineering design as a competitive alternative to evolutionary multi-objective algorithms.
When to use it
Use MOTS when you face a combinatorial or mixed-integer optimization problem with two or more conflicting objectives (e.g., cost vs. quality, time vs. risk) and exact methods are computationally intractable. It excels on scheduling, vehicle routing, network design, and portfolio selection problems where the search space is too large for exhaustive enumeration. Prefer MOTS over purely random search when neighborhood structure is meaningful and move operators can be defined cleanly. Do NOT use MOTS when: the problem has a single objective (plain Tabu Search suffices); when the Pareto front can be enumerated exactly; when gradient information is available and the landscape is convex (use mathematical programming instead); or when real-time decisions require deterministic, reproducible outputs without stochastic variation.
Limitations and considerations
- Performance is highly sensitive to tabu list length, neighborhood definition, and diversification strategy — requiring careful parameter tuning.
- No convergence guarantee to the true Pareto front; solution quality depends on run length and problem structure.
- Computationally expensive per iteration when neighborhoods are large or objective evaluations are costly.
- Maintaining and updating the Pareto archive can become expensive as the number of objectives and archive size grow.
- Parallel implementation is non-trivial due to the sequential memory-based nature of the tabu mechanism.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Avoids revisiting recent solutions via the tabu list, reducing the risk of cycling in complex landscapes.
- Aspiration criteria allow override of tabu restrictions when a move leads to exceptional improvement, balancing memory with flexibility.
- Does not require gradient information, making it applicable to non-differentiable, discrete, or black-box objective functions.
- Produces an approximation of the entire Pareto front in a single run, supporting multi-criteria decision-making.
- Flexible neighborhood and move operator design allows problem-specific customization.
- Diversification mechanisms enable escape from local optima and better Pareto front coverage.
Applications
- Multi-objective vehicle routing and logistics scheduling (minimize cost and delivery time simultaneously)
- Bi-objective project scheduling: minimize makespan and resource cost under precedence constraints
- Portfolio optimization: balance expected return against risk across multiple asset classes
- Network design: minimize installation cost while maximizing reliability or throughput
- Manufacturing process planning: optimize cycle time, energy use, and quality metrics jointly
- Environmental management: balance economic output against pollution or ecological impact
How it works
How it works
Initialize the search with one or more starting solutions (randomly generated or constructed heuristically). Set an empty tabu list of fixed length L and initialize the Pareto archive with non-dominated solutions from the starting population.
Generate the neighborhood N(s) of the current solution s by applying move operators (swaps, insertions, perturbations). Evaluate all neighbor solutions on every objective function to identify candidates for progression.
Apply the tabu filter: exclude neighbors whose defining moves appear on the tabu list unless they satisfy an aspiration criterion — typically that the neighbor dominates all current archive members or improves the best known value on at least one objective. This prevents cycling and forces exploration.
Select the best non-tabu neighbor (or aspiration-criterion winner) as the next current solution. Update the Pareto archive by adding the new solution if it is non-dominated; remove any archive members that are dominated by the new entry.
Apply diversification strategies when the search stagnates: long-term frequency memory identifies rarely visited regions; restart from elite archive solutions or randomly perturbed solutions to extend coverage of the Pareto front.
Repeat the neighborhood, filter, and archive steps until a stopping criterion is met — typically a maximum number of iterations, function evaluations, or elapsed CPU time. Return the Pareto archive as the approximated Pareto-optimal front.
Common pitfalls
- Setting the tabu list too short causes cycling; setting it too long over-restricts the search and misses good solutions — empirical calibration is essential.
- Neglecting diversification leads to premature convergence on one region of the Pareto front, producing a poor approximation.
- Applying MOTS with more than three objectives degrades performance because archive management and diversity maintenance become computationally burdensome; consider decomposition-based methods for many-objective problems.
- Using generic move operators without problem-specific design severely limits solution quality compared to tailored implementations.
- Reporting only the final archive without examining convergence history can mask premature stagnation.
Frequently asked questions
How does MOTS handle the tabu list when there are multiple objectives?
The tabu list stores moves (not solutions), so it operates the same way as in single-objective Tabu Search. The key difference is that selection among non-tabu neighbors uses multi-objective dominance or a scalarization function, and the aspiration criterion is redefined to allow a tabu move if the resulting solution is non-dominated by all current archive members.
What is the Pareto archive and how large should it be?
The Pareto archive stores all non-dominated solutions found during the search. Its maximum size is usually bounded (e.g., 100–500 solutions) to keep memory and update cost manageable. When the archive is full, crowding-distance or grid-based pruning removes solutions from over-crowded regions to maintain diversity.
How does MOTS compare to NSGA-II for multi-objective problems?
NSGA-II uses a population-based evolutionary approach with crossover and mutation, making it better at global exploration early in the search. MOTS relies on neighborhood moves and memory, which often gives finer local search quality. In practice, MOTS tends to outperform on combinatorial problems with strong neighborhood structure, while NSGA-II is more widely used for continuous problems.
How many iterations are typically needed?
There is no universal rule. Common practice is to budget function evaluations rather than iterations — typically 10,000 to 100,000 evaluations depending on problem size — and to run multiple independent starts to assess solution quality and Pareto front stability.
Can MOTS handle more than two objectives?
Yes, but effectiveness degrades as the number of objectives grows beyond three (the 'curse of dimensionality' in objective space). For four or more objectives, archive size explodes and diversity maintenance becomes difficult; decomposition-based or indicator-based approaches are often preferred.
Related methods
Sources
Hansen, M. P. (1997). Tabu search for multiobjective optimization: MOTS. Presented at the 13th International Conference on Multiple Criteria Decision Making (MCDM), Cape Town, South Africa.
Open publication referenceCopied.Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.
Open DOI referenceCopied.