Multi-objective Tabu Search (MOTS) — Metaheuristic for Pareto-optimal solutions
Multi-objective Tabu Search (MOTS) — Metaheuristic optimization for multiple conflicting objectives · Also known as: MOTS, Multi-criteria Tabu Search, Pareto Tabu Search, TSMOO
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.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
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.
Strengths & limitations
- 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.
- 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.
Frequently asked
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.
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. link ↗
- Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206. DOI: 10.1287/ijoc.1.3.190 ↗
How to cite this page
ScholarGate. (2026, June 3). Multi-objective Tabu Search (MOTS) — Metaheuristic optimization for multiple conflicting objectives. ScholarGate. https://scholargate.app/en/simulation/multi-objective-tabu-search
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Multi-objective ant colony optimizationSimulation↔ compare
- Multi-objective genetic algorithmSimulation↔ compare
- Multi-objective particle swarm optimizationSimulation↔ compare
- Multi-objective simulated annealingSimulation↔ compare
- Tabu SearchOptimization↔ compare