Orientador: João Carlos Setubal / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-26T12:21:55Z (GMT). No. of bitstreams: 1 AbreuJunior_LidioNunesde_M.pdf: 9384178 bytes, checksum: ab1f02d1d27d732c311ae88caa13f5d9 (MD5) Previous issue date: 2000 / Resumo: O assunto principal desta tese é o problema da designação: dado um grafo bipartido com custos nas arestas, obter um emparelhamento perfeito de custo mínimo. Na primeira parte do trabalho apresentamos uma revisão detalhada dos conceitos e principais resultados da literatura sobre esse problema. Na segunda parte, discutimos uma variante paramétrica, na qual cada aresta e tem seu custo dado por uma expressão do tipo ce° + ?ce?, onde ce° e ce? são constantes e ? é o parâmetro, cujo valor é real e varia. Nesta variante o objetivo é obter todas as soluções do problema para um intervalo de valores de A no menor tempo possível. Nesta parte inicialmente fazemos uma revisão de resultados da literatura que apresentam técnicas gerais para a resolução de problemas paramétricos em Otimização Combinatória. Em seguida apresentamos uma abordagem, também da literatura, específica para o problema do fluxo de custo mínimo, do qual o problema da designação é um caso especial. Esta abordagem se baseia em propriedades do algoritmo simplex de rede. Em seguida apresentamos uma nova abordagem, baseada numa relação entre o problema do fluxo de custo mínimo e o problema do ciclo de razão mínima. A complexidade desta nova abordagem é insatisfatória quando se quer resolver uma instância do problema da designação paramétrico, pois a complexidade conhecida do problema do ciclo de razão mínima é maior do que a complexidade conhecida do problema da designação. Esta nova abordagem entretanto é satisfatória do ponto de vista teórico quando aplicada ao problema do fluxo de custo mínimo paramétrico. O trabalho finaliza apresentando uma comparação experimental entre as abordagens "simplex de rede" e "ciclo de razão mínima" para o problema do fluxo mínimo paramétrico, mostrando que a primeira é muito superior à segunda. / Abstract: This dissertation is about the Assignment Problem: given an edge-weighted bipartite graph, find a perfect matching of minimum weight. In the first part of this work we present a detailed survey of the literature on this problem, including basic concepts and main results. In the second part, we discuss a parametric variant of this problem. In this variant, the weight of each edge e is given tipo ce° + ?ce?, where ce° e ce? are constants and ? is the parameter, that is, a real value that can vary. For a given range of A values we want to find all solutions to the corresponding assignment problems in the least possible time. In this part of the work we initially present a survey of techniques for solving general Combinatorial Optimization parametric problems. We then present a technique, also from the literature, for solving the parametric minimum cost flow problem, of which the assignment problem is a special case. This technique is based on the network simplex algorithm. We then present a new technique, also for solving the parametric minumum cost flow problem, based on a reduction to the minimum cost-to-time ratio cycle problem. This technique is not satisfactory for solving parametric assignment problems, because the best known algorithm for the minimum cost-to-time ratio cycle problem has worst running time than the best algorithm known for the assignment problem. It is however satisfactory from a theoretical point of view when applied to parametric minimum cost flow problems, because its running time is better than the best known running time for a certain class of inputs. We made an experimental comparison between the "network simplex" approach and the "minimum ratio cycle approach", but found that in all cases the "network simplex" approach has faster running times. / Mestrado / Mestre em Ciência da Computação

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-28T16:47:57Z (GMT). No. of bitstreams: 1 Pereira_RicardoScachetti_M.pdf: 6018166 bytes, checksum: 5c2b8981fcc29db690171dfbebf048ec (MD5) Previous issue date: 1999 / Resumo: Neste trabalho são estudados dois problemas combinatórios que ocorrem ao utilizar uma abordagem hierárquica para definir a estratégia a ser adotada na logística de distribuição de revistas. Tipicamente, a primeira fase da logística envolve a definição da região geográfica que será alocada a cada entregador. O problema de definir estas regiões é denominado problema do distritamento (PD). Na segunda fase da logística, para cada região de entrega, é preciso encontrar uma rota que minimize a distância percorrida pelo entregador. Esta rota deve satisfazer tanto a restrição de capacidade de carga do entregador quanto as restrições de fluxo de revistas, considerando-se as demandas dos pontos de entrega e o estoque nos depósitos. O problema combinatório referente a esta fase é denominado o problema da entrega de revistas (PE). Neste trabalho propõe-se algoritmos heurísticos para ambos os problemas acima, que são modelados por meio de grafos. Para o problema da entrega de revistas é proposto ainda um algoritmo exato do tipo branck-and-cut. Este algoritmo está baseado em uma formulação de Programação Linear Inteira e em desigualdades válidas fortes adaptadas dos problemas de roteamento de veículos e de fluxo em redes com custos fixos. Além disso, propõe-se um Sistema Espacial de Apoio à Decisão (SEAD) baseado em um Sistema de Informação Geográfica (SIG) para a Logística de Distribuição de revistas que pressupõe a integração das soluções dos problemas do distritamento e da entrega. Todos algoritmos propostos são implementados e testados para um amplo conjunto de instâncias. Um protótipo do SEAD proposto é implementado através da integração das heurísticas ao SIG ArcView / Abstract: In this work we study two combinatorial problems that arise when a hierarchical approach is used to define the strategy to be adopted in the logistics of magazine distribution. Typically, the first phase of the logistics involves the definition of the geographical region to be assigned to each deliverman. The problem of defining such regions is called the district determination problem. In the second phase of the logistics, to each deliver region, we have to find a route that minimizes the distance traversed by the deliverman. This route must satisfy both the deliverman capacity and the magazine flow constraints, given the demands in the delivery points and the stocks in the depots. The combinatorial problem related to this phase is called the magazine delivery problem. In this work we propose heuristic algorithms for both problems above, which are modeled with graphs. For the the magazine delivery problem we also propose an exact branch-and-cut algorithm. This algorithm is based on an Integer Programming formulation and on strong valid inequalities adapted from the vehicle routing and fixed-charge network problems. Besides, we propose a Spatial Decision Support System (SDSS) based on a Geographical Information System (GIS) for the logistics of magazine distribution that assumes the integration of the solutions of the district determination and magazine delivery problems. All the algorithms proposed are implemented and tested over a wide set of instances. A prototype of the proposed SDSS is implemented via the integration of the heuristics to the GIS ArcView / Mestrado / Mestre em Ciência da Computação

Orientadores: Carlos Magnus Carlson Filho, Raul Vinhas Ribeiro / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-25T03:01:30Z (GMT). No. of bitstreams: 1 Sousa_MarcosAntoniode_M.pdf: 7406644 bytes, checksum: 11c6a42328bae68010cead9c0ed378eb (MD5) Previous issue date: 1999 / Resumo: Novas tecnologias, aliadas ao processo de desregulamentação e competição de mercado, vêm impondo mudanças substanciais, a um ritmo muito rápido, ao tradicional sistema de telecomunicações, e em particular à rede de acesso, segmento responsável pela comunicação entre o usuário (denominado assinante) e a sua estação telefônica. A busca de uma plataforma capaz de disponibilizar serviços diversificados e lucrativos é uma tendência a ser seguida pelas empresas operadoras do setor. A variedade de cenários possíveis e os valores fmanceiros envolvidos exigem que os planejadores disponham de ferramentas ao mesmo tempo abrangentes e flexíveis. Diante desta atual conjuntura, propõe-se neste trabalho uma metodologia de planejamento orientada à maximização de receita, descrevendo-se os procedimentos necessários a serem realizados pelo planejador para efetuar os estudos de evolução da rede para um ambiente multi-serviço. Para este fIm, modelos matemáticos de otimização que tratam da etapa de dimensionamento de equipamentos também são propostos. Especificamente, são apresentados modelos de programação linear inteira mista que tratam a expansão da rede como um problema de otimização de fluxo em rede com restrições adicionais e variáveis binárias. Como característica marcante, a metodologia permite um alto grau de interação com o planejador, flexibilidade que possibilita analisar variados aspectos do compromisso entre serviço e tecnologia, receita e custo. Resultados numéricos, fundamentados em dados reais, são apresentados e discutidos...Observação: O resumo, na íntegra, poderá ser visualizado no texto completo da tese digital / Abstract: New technologies, besides the market deregulation and competitiveness, are changing Telecommunications in a fast-paced way. The Access Network, which connects users (subscribers) to their Central Oíflces, is one of the most affected parts of the system. Operating companies now look for a network structure which is able to provide several profItable services. The diversity of evolution settings and the large fmancial amount impose the need of flexible, comprehensive decision-support tools. This work proposes a revenue-oriented planning methodology and describes ways of studying the Access Network growth in a multi-service environment. Optimization mathematical models for equipment allocation and sizing are also presented for some technologies. The mixed linear-type models deal with the planning problem as a network flow problem with additional constraints and binary decision variables. As a remarkable feature, the interactiveness of the methodology allows analyses of services, technologies, and costj revenue tradeofIs. An application to an actual network is reported...Note: The complete abstract is available with the full electronic digital thesis or dissertations / Mestrado / Mestre em Engenharia Elétrica

Orientador : Clovis Perin Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-15T00:29:53Z (GMT). No. of bitstreams: 1 Lombardo_DeniseHelena_M.pdf: 1993606 bytes, checksum: ed3e7afb38488684a314e43b42a8e549 (MD5) Previous issue date: 1986 / Resumo: Esta dissertação envolve o estudo de dois problemas de otimização combinatória: O Problema do Caixeiro Viajante (PCV) e o Problema do Carteiro Chinês (PCC). Dada uma rede (ou grafo), primeiro problema consiste em determinar uma rota circular mínima que passa em cada nó e o segundo em determinar uma rota circular mínima que passa em cada linha da rede. Embora ambos problemas sejam da classe NP-"árduo" (NP- hard ), o problema do Carteiro Chinês é apresentado na literatura como um problema menos "difícil" de ser resolvido. O interesse em estudar o PCV e o PCC partiu do grande numero de publicações em revistas e livros técnicos de Pesquisa Operacional a respeito destes problemas. Além disto, estes problemas são de importância no estudo da determinação de rotas de veículos onde se procura obter rotas que devem ser utilizadas por uma frota de veículos para satisfazer determinadas demandas (ou restrições) tanto nos nós quanto nas linhas; por exemplo, coleta de lixo de n cidades / Abstract: Not informed / Mestrado / Mestre em Matemática Aplicada

Orientador: Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-21T02:04:11Z (GMT). No. of bitstreams: 1 Bussamra_NeusaMaria_M.pdf: 7956815 bytes, checksum: 30f982df17de113ac832a5c2c381886d (MD5) Previous issue date: 1995 / Resumo: Nos países onde os sistemas de eleição de representantes seguem o modelo distrital, a topografia dos distritos políticos eleitorais é de fundamental importância pois a sua manipulação pode vir a favorecer alguns partidos políticos em detrimento de outros. Na tentativa de combater esta prática, estes países delegam a tarefa de estabelecer distritos eleitorais a comissões neutras, multipartidárias, que desde os anos 60 vêm envolvendo especialistas em pesquisa operacional em seus trabalhos. Esta tese revisa os principais métodos encontrados na literatura para a resolução do problema do distritamento eleitoral que é, do ponto de vista matemático, um problema complexo de otimização combinatórial. É apresentada uma nova metodologia de solução do problema baseada em técnicas heurísticas, bem como os resultados de sua aplicação à cidade de Campinas / Abstract: This thesis revises the most important methods proposed to solve the political districting problem, a hard combinatorial optimization problem and proposes a new methodology based on heuristic techniques. The method combines the solution of a p-median problem in order to generate an initial feasible solution and an improvement procedure that makes use of a ?-interchange mechanism. Computational results on many instances are provided / Mestrado / Mestre em Engenharia Elétrica

Orientador: Reginaldo Guirardello / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Quimica / Made available in DSpace on 2018-07-27T15:25:01Z (GMT). No. of bitstreams: 1 Franceira_SergioNorival_M.pdf: 3731488 bytes, checksum: d7857c421064b5382fefae40ea456256 (MD5) Previous issue date: 2001 / Resumo / Abstract / Mestrado / Desenvolvimento de Processos Químicos / Mestre em Engenharia Química

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T18:54:27Z (GMT). No. of bitstreams: 1 Ducati_ElianeAparecida_M.pdf: 781743 bytes, checksum: bd3f3b9a4b012da900301a69c6bc44d6 (MD5) Previous issue date: 2003 / Mestrado

Orientador: Hermano de Medeiros F. Tavares / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia de Campinas / Made available in DSpace on 2018-07-14T23:26:04Z (GMT). No. of bitstreams: 1 Milani_BasilioErnestodeAlmeida_D.pdf: 4602190 bytes, checksum: 12cc8a5797d886b36fc660711c7aad80 (MD5) Previous issue date: 1980 / Resumo: A síntese via otimização de parâmetros de reguladores L-Q e L-Q-G com restrições de estrutura é introduzida como uma solução de compromisso entre a subotimalidade do desempenho do sistema de controle e a viabilidade de sua implementação prática. E feita uma abordagem unificada com um tratamento detalhado e em profundidade do cálculo em forma fechada do índice de desempenho, vetor gradiente e matriz hessiana. É proposto um novo método Quasi-Newton especializado para solução do problema de otimização de parâmetros. O novo método é baseado em uma aproximação definida positiva da matriz hessiana e explora a fraqueza das restrições de estrutura para obter uma melhor razão de convergência. Comparado com outros métodos otimização, o método Quasi-Newton especializado se mostrou melhor adaptado para tratar problemas de otimização de grande porte e também capaz de apresentar um desempenho computacional muitas vezes superior. No final são discutidas possibilidades de extensão e melhoria dos resultados obtidos. / Abstract: Not informed. / Doutorado / Doutor em Engenharia Elétrica

Made available in DSpace on 2019-03-30T00:01:15Z (GMT). No. of bitstreams: 0 Previous issue date: 2018-12-28 / This thesis investigates resource dispatch policies for emergency calls in large metropolis. A multi-agent environment implements a simulator of emergency calls and dispatch of resources, serving as an instrument to initially develop a comparative analysis of static policies, in which the order of attendance follows pre-established criteria. From these analyzes, it is concluded that such policies end up favoring only a quality criterion (e.g. the overall waiting time of the caller). This is a weakness as resource dispatch centers must take multiple quality criteria into account, such as reducing response time, cost of moving vehicles, increasing the number of calls served, and answering priority calls. In order to define dynamic policies that can lead to the optimization of multiple objectives, the Pareto set concept is used to model the different criteria to be optimized. Instead of attempting to identify manually or previously define the best dispatch strategy, a multi-objective evolutionary algorithm, coupled with the emergency call simulator and resource dispatch, automatically discovers the best approximation of the Pareto Optimum Set that would be responsible for indicating the order of call attending. The evolutionary algorithm uses the concept of quantitative dominance that calculates how much an individual dominates another, which allows greater efficiency in the discovery of the best order of resources. The validation scenario is a great metropolis in Brazil using a year of real data calls to the 911. Comparative analysis with static policies and with traditional variations of the multi-objective evolutionary algorithm without the use of quantitative dominance confirms the performance of the approach proposed in the thesis. Keywords: Agent-based simulation; evolutionary algorithms; multiobjective optimization; dispatch center / Essa tese investiga políticas de despacho de recursos para atendimento a chamadas de emergência em grandes cidades. Um ambiente multiagente implementa um simulador de chamadas de emergências e despacho de recursos, servindo de instrumento para, inicialmente, se desenvolver uma análise comparativa de políticas estáticas, nas quais a ordem de atendimento segue a critérios pré-estabelecidos. A partir dessas análises, conclui-se que tais políticas acabam por privilegiar somente um critério de qualidade (e.g. o tempo global de espera do chamador). Isso se mostra uma deficiência, pois centros de despacho de recursos devem levar em conta critérios de qualidade múltiplos como reduzir o tempo de resposta, o custo de deslocamento de veículos, aumentar o número de chamadas atendidas e o atendimento de chamadas prioritárias. Visando definir políticas dinâmicas que possam levar a otimização de objetivos múltiplos, usa-se o conceito de conjunto de Pareto para modelar os diferentes critérios a serem otimizados. Em vez de tentar identificar manualmente ou definir previamente a melhor estratégia de despacho, um Algoritmo Evolutivo Multiobjetivo, acoplado ao simulador de chamada de emergência e de despacho de recursos, descobre automaticamente a melhor aproximação do Conjunto ótimo de Pareto que seria o responsável por indicar a ordem de atendimento das chamadas. O algoritmo evolutivo usa o conceito dominância quantitativa que calcula o quanto um indivíduo domina outro, o que permite maior eficiência na descoberta da melhor ordem de recursos. O cenário de validação é uma grande metrópole no Brasil usando um ano de dados reais de chamadas para o 190. Análises comparativas com políticas estáticas e com variações tradicionais do algoritmo evolutivo multiobjectivo sem o uso de dominância quantitativa confirma a performance do enfoque proposto na tese. Palavras-chave: Simulação baseada em agentes; algoritmos evolutivos; otimização multiobjetivo; centro de despacho.

Made available in DSpace on 2019-03-29T23:33:16Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-07-27 / Hyper-heuristics are an emerging theme in the optimization area which try to address computationally hard problems at a new level of abstraction. Instead of having a single algorithm that is optimized to perform well on a certain class of problems, hyper-heuristics try to balance the advantages and disadvantages of a set of problem specific heuristic algorithms, named low-level heuristics. By combining and parameterizing these heuristics or heuristic components in different ways, hyper-heuristics seek a satisfactory result in a larger set of problem instances. The objectives of this work are to propose a new hyper-heuristic approach inspired by particle swarms and to analyze empirically the utilization and the effectiveness of low-level heuristics during the execution of the proposed hyper-heuristic and of a set of hyper-heuristics proposed by other authors. The novel hyper-heuristic simultaneously explores the heuristic space as well as the solution space by maintaining both a population of heuristics and another of candidate solutions. Computational experiments and statistical tests were used to compare the effectiveness of the hyper-heuristics investigated here, demonstrating that the proposed hyper-heuristic obtained a more satisfactory performance in accordance with the evaluation metrics used. The empirical analysis allowed us to observe the different patterns of usage by the contestant hyper-heuristics of the low-level heuristics available for each problem domain. Keywords: Hyper-heuristics, Metaheuristics, Combinatorial Optimization, Particle Swarm Optimization. / Hiper-heurísticas são um tema emergente na área de otimização e se propõem a resolver problemas computacionalmente difíceis com um novo nível de abstração. Em vez de se ter um único algoritmo otimizado para tratar bem uma certa classe de problemas, elas tentam balancear as vantagens e desvantagens de um conjunto de heurísticas específicas para um domínio de problema, denominadas heurísticas de baixo nível. Combinando e parametrizando essas heurísticas, ou componentes de heurísticas, se busca um resultado satisfatório em um conjunto maior de instâncias de problemas. Os objetivos deste trabalho são propor uma nova abordagem hiper-heurística inspirada em enxame de partículas e analisar empiricamente o uso e a eficácia das heurísticas de baixo nível utilizadas durante a execução da hiper-heurística proposta, bem como de um conjunto de hiper-heurísticas concebidas por outros autores. A hiper-heurística proposta explora concorrentemente o espaço de busca heurístico e o espaço de busca de soluções, lançando mão de uma população de heurísticas e outra de soluções-candidatas. Experimentos computacionais e testes estatísticos foram utilizados para comparar a eficácia das hiper-heurísticas investigadas, demonstrando que a hiper-heurística proposta obteve um desempenho mais satisfatório de acordo com as métricas de avaliação utilizadas. Por outro lado, a análise empírica possibilitou o entendimento dos diferentes padrões de uso, por parte das hiper-heurísticas investigadas, das heurísticas de baixo nível disponíveis para cada domínio de problema. Palavras-Chave: Hiper-heurísticas, Meta-heurísticas, Otimização Combinatória, Otimização por Enxame de Partículas.