Heuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean Space

Abstract

We describe a family of heuristics to solve combinatorial problems such as routing and partitioning. These heuristics exploit geometry but ignore specific distance measures. Consequently they are simple and fast, but nonetheless fairly accurate, and so seem well-suited to operational problems where time or computing resources are limited. We survey promising new application areas, and show how procedures may be customized to reflect the structure of particular applications.