Empirical Analysis

The final definition of good solution is perhaps the most commonly used. It is testing heuristics on real problems. If you want a heuristic to route a machine that puts together cellular telephones, then it seems reasonable to test your heuristic on a bunch of cellular telephones. Similarly, if you are interested in Meals-on-Wheels scheduling, then try your router on some sample customer lists.

The advantage of this approach is that it does solve problems at least similar to ones you are interested in. You generally cannot work with exactly the data you are interested in. Typically, you have to use last years data, or some variant on past data (perhaps randomly corrected for year to year changes). In general, you have confidence in the underlying problems.

The disadvantage is that no analytical test can be done. Solutions must be simulated, and statistics gathered and analyzed. This can turn into a very expensive process. In addition, if there are fundamental differences between next year and last year, all that work may be irrelevant: the conclusions might not hold. Also, in many applications, there is no set of data from last year. In many cases, you are trying to schedule a new machine, or build a new system, so you can only guess what problems are like.

In spite of these difficulties, you can generally place much more faith in this type of testing.