Title: Partição multicritério de um território em zonas : modelos, algoritmos e aplicações
Authors: Pereira, Fernando Manuel Tavares 
Keywords: Optimização matemática;Ordenamento do território;Investigação operacional;Planeamento territorial
Issue Date: 18-Jul-2007
Citation: Pereira, Fernando Manuel Tavares - Partição multicritério de um território em zonas : modelos, algoritmos e aplicações. Coimbra, 2006.
Abstract: Actualmente, os problemas de partição de um território têm sido alvo de uma maior atenção por parte da comunidade científica, como por parte dos agentes de decisão. Dependendo do contexto onde se insere, uma partição criteriosa de um território pode representar um incremento de eficiência de uma actividade, um maior equilíbrio de cargas de trabalho ou uma menor distância percorrida. Neste trabalho analisámos os diferentes problemas de partição territorial que têm sido abordados até à actualidade, por forma a classificá-los, quer na sua natureza quer na metodologia utilizada para os resolver. Partindo desta análise tentámos preencher algumas lacunas, enriquecendo o conjunto de ferramentas teóricas da área da modelação, estabelecendo uma taxonomia dos critérios e concebendo uma plataforma de comparação entre diferentes partições, através da definição de medidas de similitude que traduzem os conceitos aos quais associámos os termos compatibilidade, inclusão e distância. Cada um destes conceitos foi testado através da implementação de uma medida compatível com o que se pretende avaliar. Quando se consideram vários critérios, o problema da enumeração de todas as soluções eficientes é conhecido como sendo NP-difícil. Este facto implica o abandono de métodos exactos para a resolução de instâncias de grande dimensão. A nossa resposta a esta constatação resultou no desenvolvimento de um novo método para aproximar a fronteira de Pareto baseado em algoritmos evolutivos com pesquisa local, capaz de lidar com um qualquer problema de partição de um território com dois critérios. O algoritmo concebido utiliza uma representação das soluções e operadores de cruzamento/mutação originais, sendo composto por elementos suficientemente genéricos de modo a permitir uma fácil adaptação a realidades distintas e que possibilite a sua integração num sistema interactivo de apoio à decisão. Este permite resolver instâncias de grande dimensão num tempo de CPU aceitável e gerar soluções de boa qualidade. O algoritmo foi testado num ambiente de uma aplicação real com os dados que resultaram de um estudo para a reforma do sistema de tarifação dos transportes públicos da região metropolitana de Paris.
Currently, districting problems have a bigger attention from the scientific community, as the decision maker’s. A careful districting map can represent an improvement of efficiency of an activity, a bigger work load balance or a lesser distance covered, depending on the problem context. In this work we analyzed the different districting problems that have been studied until now, in view of classifying them, according to its very nature and in the used methodology to solve them. From this analysis we tried to fill some gaps, enriching the set of modelling theoretical tools, establishing a taxonomy of the criteria and designing a platform of comparison between different districts maps, through the definition of measures of similarity that translate the concepts which we associated the terms compatibility, inclusion, and distance. Each one of these concepts was tested through the implementation of a compatible measure with what it is intended to evaluate. The problem of the enumeration of all the efficient solutions is known as being NP-hard, when it is considered more than one criterion. This fact implies the abandonment of exacts methods to solve a large-size instances. Our reply to this evidence resulted in the development of a new method to approach the Pareto front, based on evolutionary algorithms with local search, capable to deal with any districting problems with two criteria. The developed algorithm uses a new solution representation and crossover/ mutation operators, composed of generic elements in order to allow an easy adaptation the distinct realities and that it makes possible its integration in an interactive decision support system. Our algorithm solved large-size instances in an acceptable CPU time and generated solutions of good quality. The algorithm was tested with data of a real-world problem, that resulted from a study to reform the pricing system of public transports in metropolitan Paris region.
Description: Tese de doutoramento em Organização e Gestão de Empresas, especialização em Investigação Operacional pela Faculdade de Economia da Universidade de Coimbra
URI: http://hdl.handle.net/10316/2497
Rights: openAccess
Appears in Collections:FEUC- Teses de Doutoramento

Files in This Item:
File Description SizeFormat 
tese.pdf1.54 MBAdobe PDFView/Open
Show full item record
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.