Heuristics Based on Spacefilling Curves for Combinatorial Problems in the Plane

摘要

We introduce a family of heuristics, based on spacefilling curves, to solve general combinatorial problems in the plane, such as routing, location, and clustering. These remarkably simple and fast heuristics are nonetheless fairly accurate and so seem well-suited to operational problems where time or computing resources are limited. They ignore many details of the problem, yet generate solutions that are good simultaneously with respect to a variety of measures. (This may be useful when the problem specification is incomplete or cannot be agreed upon.) Furthermore they are extremely simple to code, and in some cases may even be implemented without a computer.