Dans le cas de problèmes très difficiles, les méta-heuristiques peuvent permettre d'atteindre une solution. Trois méthodes principales sont alors utilisées : le recuit simulé, les algorithmes génétiques et la recherche tabou.

• Le recuit simulé minimise de manière stochastique une fonction de coût. C'est une méthode de recherche locale dans la mesure où l'algorithme procède par de petites modifications de la solution courante, en autorisant éventuellement une dégradation temporaire de la qualité de la solution.
• Les algorithmes génétiques nécessitent un codage des solutions potentielles semblable à l'identité génétique. L'algorithme procède par mutation et croisement de ces codes en sélectionnant les solutions de qualité élevée.
• La recherche tabou est une méthode déterministe qui repose sur une gestion dynamique de deux types de mémoires : l'une à court terme assure une exploration intensive, l'autre à long terme assure une diversification. La mémoire contient des caractéristiques dites tabou i.e. que l'on s'interdit pour les futures solutions. L'objectif premier est d'éviter une exploration cyclique pour augmenter l'efficacité de la recherche.