Qualitative information-based heuristic for districting problems

Districting problems are of high importance in many real-world applications. When multiple criteria are considered, enumerating all the efficient solutions in these problems is known as being Non-Polynomial (NP)-hard. The objective of this paper is thus to introduce a heuristic to solve this type of problem. The proposed heuristic relies on a tree data structure, previously constructed based on a qualitative evaluation of the study area. This evaluation is grounded on several criteria and takes the form of a qualitative scale with a finite set of evaluation levels. The paper introduces the qualitative assessment approach, the mathematical formulation and the resolution heuristic.