Journal
ANNALS OF OPERATIONS RESEARCH
Volume 154, Issue 1, Pages 69-92Publisher
SPRINGER
DOI: 10.1007/s10479-007-0181-5
Keywords
multiple criteria; districting problems; evolutionary algorithms; local search; combinatorial optimization
Categories
Ask authors/readers for more resources
Districting problems are of high importance in many different fields. Multiple criteria models seem a more adequate representation of districting problems in real-world situations. Real-life decision situations are by their very nature multidimensional. This paper deals with the problem of partitioning a territory into homogeneous zones. Each zone is composed of a set of elementary territorial units. A district map is formed by partitioning the set of elementary units into connected zones without inclusions. When multiple criteria are considered, the problem of enumerating all the efficient solutions for such a model is known as being NP-hard, which is why we decided to avoid using exact methods to solve large-size instances. In this paper, we propose a new method to approximate the Pareto front based on an evolutionary algorithm with local search. The algorithm presents a new solution representation and the crossover/mutation operators. Its main features are the following: it deals with multiple criteria; it allows to solve large-size instances in a reasonable CPU time and generates high quality solutions. The algorithm was applied to a real-world problem, that of the Paris region public transportation. Results will be used for a discussion about the reform of its current pricing system.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available