In traveling salesman problems (TSPs), a set of cities must be visited in the order that incurs the lowest travel cost. The time required to evaluate all possible routes increases so rapidly with the number of cities that exhaustive search for the best route becomes impossible. Operations research has developed heuristic non-exhaustive search strategies that solve large instances of TSPs, e.g. simulated annealing, genetic algorithms, and tabu-search. Stratigraphic seriation and correlation are tasks analogous to TSPs and solvable by the same methods. The cities in the TSP become event horizons, e.g. appearances and disappearances of fossil taxa, paleomagnetic reversals, and ash beds. The possible routes connecting the cities become hypothetical historical sequences of stratigraphic events. Typically, no sequence can match every local stratigraphic section because the order of observed range ends for fossil taxa varies from section to section. Thus, each hypothetical sequence incurs a cost which is the net mismatch, summed across all events and sections. The solution is the sequence with the lowest mismatch and may vary with the measure of mismatch - net range extension, pair-wise event reversals, implied but unobserved coexistences, etc. The solution time increases with the number of sections and the number of events. Correlation problems involving over 2700 range-end events and 230 sections have been solved in this fashion on desktop computers. The results are time scales with up to an order of magnitude more resolving power than traditional biozones and biodiversity curves for which taxa are not binned into coarse time intervals.
SEPM: Quantitiative Stratigraphy and Geostatistics: New Approaches and Applications