  This study combines simulated annealing with delta evaluation to solve the
joint stratification and sample allocation problem. In this problem, atomic
strata are partitioned into mutually exclusive and collectively exhaustive
strata. Each partition of atomic strata is a possible solution to the
stratification problem, the quality of which is measured by its cost. The Bell
number of possible solutions is enormous, for even a moderate number of atomic
strata, and an additional layer of complexity is added with the evaluation time
of each solution. Many larger scale combinatorial optimisation problems cannot
be solved to optimality, because the search for an optimum solution requires a
prohibitive amount of computation time. A number of local search heuristic
algorithms have been designed for this problem but these can become trapped in
local minima preventing any further improvements. We add, to the existing suite
of local search algorithms, a simulated annealing algorithm that allows for an
escape from local minima and uses delta evaluation to exploit the similarity
between consecutive solutions, and thereby reduces the evaluation time. We
compared the simulated annealing algorithm with two recent algorithms. In both
cases, the simulated annealing algorithm attained a solution of comparable
quality in considerably less computation time.
