They are fast as giving you an answer but cannot tell you when are at the optimum solution. You need some termination rule to stop the algorithm such as time spent running, number of iterations etc.
We [1] have used a heuristic [2] method to solve vehicle routing for a client where optimum isn't important but certain features of the solution as speed of the answer are.
it depends on your problem, on what do you need, ... there are heuristics for trying to finde the best results, some are optimized for speed...
i have never seen a better heuristic than the k-opt-heuristic (implemented in LKH), not for speed, not for the results. there are some genetic algorithms, but they are much slower, but can find sometimes results who are a little better. (see the 100000 node mona-lisa tsp problem. lkh founds a tour with the length of 5757199, a genetic algorithm founds a tour with the length of 5757191, the best exact solver concorde founds the lower bound of 5757084 (so there is a gap of 107) after calculating a time of "11.5 CPU years").
heuristics have always the problem, that you can't not say if the found result is the optimum or not. so if you have to find the optimum, you have to take an exact solver (for bigger problems. for problems with <10000 nodes there are heuristics who find the optimum to 99%)
to get an idea if you are close to an optimum or not, there is the lower bound call "held-karp-lower-bound". you have to calculate a mst, a one-tree and some extra stuff to get it. than you can calculate the difference between both values.
> heuristics have always the problem, that you can't not say if the found result is the optimum or not.
Even worse: Heuristics have the problem that you usually can't give any metric on how good you even are. If you use an ILP (Integer Linear Programming) based approach if you found an integral solution the optimal solution of the LP relaxation gives you a lower bound (if you minimize) on the optimal length of the tour - so you can tell exactly that you only can get, say, 1% better and cancel any further computation, since you consider this as good enough.
> to get an idea if you are close to an optimum or not, there is the lower bound call "held-karp-lower-bound". you have to calculate a mst, a one-tree and some extra stuff to get it. than you can calculate the difference between both values.
The Held-Karp bound is the same as the optimal value over the subtour elimnination polytope (Theorem 21.34 in Korte, Vygen: Combinatorial Optimization - Theory and Algorithms (5th edition)). This is rather where one starts when one uses an ILP based approach.
> Which kind of metric is it used to compare these algorithms?
Usually (in particular if the edge weights in the graph are non-negative or even positive) the ratio (or sometimes, but more rarely, also the difference) between your attained solution and the optimal solution.
> How good are heuristics methods compared to exact solvers?
First: For mathematically minded people "heuristics" (in the sense of the video) are to be considered worthless since you rarely can prove anything about the solution attained by it. Even if by definition some result about the solution can be shown (say, that it is optimal in some k-neighbourhood of solutions) this will hardly tell you anything about how good you really are.
But one very good heuristic algorithm for which you actually prove something (and thus is really helpful) is the Christophides algorithm (https://en.wikipedia.org/wiki/Christofides_algorithm), for which one can show that if the edge weights form a metric in the graph you will get a solution that is at most 3/2 as long as the optimal solution.
