The term heuristic algorithm refers to the use of systematic procedures that typically trade off the quality of a solution for processing speed. Many heuristics are derived from relatively simple, commonsense ideas for finding solutions to problems, but which will not necessarily produce an optimum solution. In some instances heuristics do produce provably optimal solutions. Heuristics are defined by a set of permitted moves or transformations of a current solution, Q say, to a new (generally improved) solution, Q*. The space of all possible solutions for a given problem is known as the search space, S, and the space of solutions that are obtainable by a single transformation of a current solution, Q, is known as the neighbourhood space, N. A comparison of a number of alternative heuristics applied to a facility location problem is provided in Section 7.4.2.3.

Heuristic algorithms will often provide a fast ‘upper bound’ or ‘lower bound’ to the value of some objective function, such as the average travel time from a set of demand locations to a set of supply locations or facilities. The ‘upper bound’ can provide one edge of a confidence band whose overall width can be determined if a procedure can be devised that provides a matching ‘lower bound’ for the problem at hand. The true upper bound and lower bound is the optimal solution itself — however, this value is generally unknown in advance and may be impossible to determine. An alternative approach is to solve a problem that is very similar to the problem at hand, often with fewer constraints on the permissible solutions, and for which a solution can be obtained rapidly. This is generally known as solving a ‘relaxed’ version of the original problem. A similar concept is to solve a set of sub-problems that collectively include all of the original dataset elements.

Once an upper and lower bound have been obtained, procedures can be devised that attempt to reduce the upper bound and raise the lower bound until they are arbitrarily close — if they meet the global optimum will have been obtained, and if not then at least the quality of the solution in terms of proximity to the optimum is known — a solution procedure that gives results that are within 5% of the optimum and can be obtained very rapidly is often preferable to a solution procedure that is optimal but which in practice may not do this using finite computer and time resources. An example of a relaxed problem might be to permit the use of Manhattan or minimax distance rather than Euclidean or network distance when assigning customers to facilities, or to entirely or partially remove one or more constraints on the problem as a temporary measure. A widely used procedure of this kind is known as Lagrangian relaxation (see further, Section 7.2.2.7).

Tests of combinatorial optimisation procedures in general and heuristics in particular, often use the travelling salesman problem (TSP) as a benchmark for the quality and performance. This is because the problem is easily specified, known to be extremely difficult to solve, and may be examined using a library of available test data. In essence the TSP involves making a tour of every vertex in a given set (e.g. cities in a country), and returning to the starting point, such that the total tour length or cost is minimized. The distance measure used must be a metric or semi-metric, i.e. asymmetry may be permitted but distances must be positive and satisfy the triangle inequality. If there are N cities there are N! possible tours, so the search space is O(N!), a value which rapidly becomes immensely large (this reduce slightly to N!/2 if the distances are symmetric and (N-1)!/2 if the position of the first city is pre-defined). More details on the TSP are provided in Section 7.3.5, but it is referred to frequently in other sections of this Guide. An excellent introduction to TSP problems and solutions is available at:

http://www.tsp.gatech.edu/index.html

Currently the largest solved TSP cases are of the order of 25,000 cities and test problems for 1 million plus cities exist. Although the basic symmetric Euclidean TSP, as described above, is the most common baseline used for testing, many variants exist, including: asymmetric edges; time windows for deliveries/collections; multiple routes (partitioned sets of cities); capacity constrained links and vehicles; and many more. Their application is also not restricted to transportation problems, but extends to many other fields of research, from printed circuit board manufacture to job scheduling to genetic sequencing.