• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 45
  • 2
  • 2
  • 2
  • 2
  • 2
  • Tagged with
  • 46
  • 46
  • 46
  • 24
  • 22
  • 21
  • 20
  • 17
  • 12
  • 11
  • 10
  • 9
  • 8
  • 8
  • 8
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Problema do caixeiro viajante

Rodrigues, Marco Antonio Pereira January 2000 (has links)
Dissertação (Mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. / Made available in DSpace on 2012-10-17T14:43:31Z (GMT). No. of bitstreams: 1 161353.pdf: 735044 bytes, checksum: 30d3067872988cb97789f43f7b58dbf9 (MD5) / Neste trabalho é proposto um algoritmo para a resolução do Problema do Caixeiro Viajante (PCV), baseado em estratégia de particionamento, que atua em conjunto com a recém a apresentada metaheurística Busca Local Dirigida (BLD). Testes são realizados para avaliar a qualidade desse algoritmo, frente a um outro procedimento, também baseado em estratégia de particionamento, sobre problemas da biblioteca TSPLIB de Reinelt. Verificou-se que o algoritmo proposto é capaz de gerar bons resultados, em tempo relativamente curto. Algumas sugestões e considerações são apresentadas para o desenvolvimento de futuros trabalhos.
2

Solução heurística para o problema do caixeiro viajante

Braz, Eugênio Rubens Cardoso January 1980 (has links)
Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção. / Made available in DSpace on 2012-10-16T21:09:38Z (GMT). No. of bitstreams: 0Bitstream added on 2013-07-16T16:49:56Z : No. of bitstreams: 1 261880.pdf: 1108413 bytes, checksum: 4ff4ea65b7eb1cedec345a9b83c9f273 (MD5)
3

Estudo das estrategias de partição no problema do caixeiro viajante

Oliveira, Antonio Costa de 02 October 1987 (has links)
Orientador : Clovis Perin Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-15T13:14:58Z (GMT). No. of bitstreams: 1 Oliveira_AntonioCostade_M.pdf: 2077929 bytes, checksum: c7812ef3301b21c76d3b46f3491fe42f (MD5) Previous issue date: 1987 / Resumo: Não informado / Abstract: Not informed / Mestrado / Mestre em Matemática Aplicada
4

Modelagem e otimização do problema do caixeiro viajante com restrições de tempo, distância e confiabilidade via algoritmos genéticos

BRAGA, Edgar Augusto Silva January 2007 (has links)
Made available in DSpace on 2014-06-12T17:41:04Z (GMT). No. of bitstreams: 2 arquivo7291_1.pdf: 580173 bytes, checksum: bd3d8db14bddcd9da6a6fb0b872d8ef7 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2007 / Neste trabalho, propõe-se uma metodologia de modelagem para problemas de roteirização de veículos baseada no Problema do Caixeiro Viajante. Mais especificadamente, busca-se tornar o Problema do Caixeiro Viajante com Coletas de Prêmios mais coerente com a realidade do contexto logístico, levando em conta a capacidade operacional da organização e restrições mercadológicas. Para tal, são introduzidos novos elementos como a confiabilidade do caixeiro e restrições de tempo para realizar o roteiro. O modelo consiste, então, em maximizar o lucro obtido através da coleta de prêmios e do custo associado ao roteiro, sujeito a restrições de tempo máximo e confiabilidade mínima aceita ao final do percurso. Esta nova abordagem é modelada e resolvida via Algoritmos Genéticos e é ilustrada através de um estudo de caso
5

Abordagens adaptativas de metaheuristicas tabu

Pureza, Vitoria M. M 17 December 1996 (has links)
Orientador: Paulo Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-22T22:52:02Z (GMT). No. of bitstreams: 1 Pureza_VitoriaM.M_D.pdf: 9869285 bytes, checksum: 3d30f5f94e19c47fb41416cb14190a97 (MD5) Previous issue date: 1996 / Resumo: A Busca Tabu é um procedimento heurístico de orientação da busca com vistas à obtenção de boas soluções em problemas de dificil tratamento. Fundamentalmente, ela é caracterizada por mecanismos que promovem a superação da otimalidade local. Esses mecanismos geralmente tomam a forma de parâmetros que impõem restrições à seleção de movimentos. Como a calibragem desses elementos restritivos tem um impacto fundamental no desempenho do algoritmo, algumas implementações utilizam estratégias que provocam alterações sistemáticas nos valores de determinados parâmetros. Estas estratégias procuram intensificar a exploração de regiões promissoras e o abandono de regiões onde possibilidades de melhoria parecem mínimas. As alterações nos valores dos parâmetros são normalmente acionadas por fases de busca caracterizadas pela ausência de movimentos de atualização da solução incumbente. O objetivo principal deste trabalho é o de propor uma nova abordagem adaptativa de metaheurísticas Tabu. A abordagem HTA, aqui considerada, propõe que a alteração de parâmetros seja determinada a partir da identificação de padrões da trajetória de busca recentemente traçada. Estes padrões fornecem indicações, ainda que limitadas, acerca da topologia do espaço de soluções. Para cada padrão, são aplicadas perturbações nos valores de parâmetros tabu selecionados, como forma de adaptar a busca às diferentes condições encontradas. A abordagem HTA foi desenvolvida a partir de extensos experimentos com o Problema do Caixeiro Viajante Simétrico e Euclideano (PCV). Testes envolveram 12 instâncias clássicas e verificaram ganhos significativos em relação à versão não-adaptativa, mesmo sob condições operacionais estressantes impostas por parâmetros mantidos fora de controle. A seguir, a mesma abordagem foi aplicada ao Problema de Roteamento de Veículos (PRV). Neste trabalho, apresentamos os resultados obtidos com 14 instâncias clássicas caracterizadas por diferentes restrições. Os resultados foram comparados com os de três algoritmos altamente competitivos e indicaram que HTA produz soluções de qualidade comparável aos demais. São também apresentados os resultados obtidos com uma implementação adaptativa HTA para o Problema de Agrupamento Capacitado (PAC). Os resultados, mais uma vez, sugerem que a introdução de mecanismos adaptativos baseados em padrões da trajetória da busca é uma estratégia robusta e promissora / Abstract: Tabu Search (TS) is a general heuristic procedure for guiding search to obtain good solutions in complex solution spaces. Fundamentally, it is characterized by mechanisms that allow the exploration of the solution space beyond local optimality. These mechanisms are generally implemented by means of parameters which impose restrictions to move selection. Since the calibration of such restrictive elements has a major impact on the algorithm's performance, some implementations use strategies for altering the values of these parameters whenever non-improving search phases are verified. Essentially, these strategies seek to intensify the exploration of promising regions of the solution space, and to abandon the search in regions where improvement possibilities seem to be minimal. The main purpose ofthis work is to propose a new adaptive Tabu metaheuristic approach. The HTA approach, considered here, assumes that the alteration of the parameters values should be defined first by identifying specific pattems in the search trajectory recently described. These pattems provide indications of the solution space topology. For each pattem, perturbation on the values of selected tabu parameters is applied, as means to adapt the search to the different conditions found. The HTA approach was developed from extensive experiments with the Symmetric and Euclidean Traveling Salesman Problem (TSP). Tests involved 12 benchmark instances and verified improvements with respect to a non-adaptive implementation, even under stressing operational conditions provided by free-Junning parameters. HTA was also applied to the Vehicle Routing Problem (VRP). We present the results obtained for 14 benchmark instances characterized by different restrictions. Our adaptive implementation is compared to three highly competitive algorithms. The results indicate that HTA is able to provide solution quality levels comparable to the other algorithms. We also present the results provided by an HTA implementation for the Capacitated Clustering Problem (CCP). They also suggest that introducing adaptive mechanisms based on the pattems of search trajectories is a robust and promising strategy / Doutorado / Doutor em Engenharia Elétrica
6

Relax and cut: limitantes duais para o problema do caixeiro viajante

Kawashima, Makswell Seyiti [UNESP] 30 May 2014 (has links) (PDF)
Made available in DSpace on 2014-11-10T11:09:53Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-05-30Bitstream added on 2014-11-10T11:57:47Z : No. of bitstreams: 1 000790195.pdf: 918459 bytes, checksum: 01e8141c5483f5a04a86fdd9a1917ef1 (MD5) / O Problema do Caixeiro Viajante (PCV) é um problema clássico de Otimização Combinatória. Dado um conjunto de cidades e os custos de viagem entre cada par delas, o objetivo é encontrar um roteiro que passa em todas as cidades apenas uma vez e retorna à cidade de origem de menor custo total. O enunciado simples e resolução não trivial encantaram muitas pessoas ao longo dos anos. Na literatura são apresentadas diversas formulações matemáticas para o Problema do Caixeiro Viajante, além de comparações entre a qualidade da relaxação linear de tais formulações. A formulação clássica para o PCV é forte, porém possui um número exponencial de restrições, e é equivalente à formulação de multiproduto (multi-commodity), de ordem polinomial. O custo computacional para resolver a relaxação linear da formulação multiproduto é alto, incentivando a busca de novas formas de obter limitantes duais. Na literatura são propostos procedimentos para obtenção de limitantes duais para o PCV utilizando-se do método relax and cut, a partir do problema da designação (PD), dualizando inequações válidas que são violadas pela solução ótima do PD. Neste trabalho, propomos a aplicação do método relax and cut para a formulação do PCV com restrições de multiproduto. Os resultados obtidos no estudo computacional são encorajadores, com a implementação de um algoritmo que gera bons limitantes duais com baixo tempo computacional / The Traveling Salesman Problem (TSP) is a classical Combinatorial Optimization problem. Given a set of cities and travel costs between each pair of them, the objective is to find a tour through all the cities, visiting each city once, and returning to the city of origin with minimum total cost. The simple enunciate and non-trivial resolution enchanted many people through the years. In the literature various formulations for the Traveling Salesman Problem are presented, and the quality of the linear relaxation of such formulations is compared. The classical TSP formulation is strong, but have an exponencial number of constraints, and is equivalent to the multi-commodity formulation, of polinomial order. The computational cost to solve the linear relaxation of the multi-commodity formulation is high, stimulating the search of new ways of obtaining dual bounds. In the literature, procedures to obtain dual bounds to the TSP using the relax and cut technique are proposed, starting from the assignment problem (AP) and dualizing violated valid inequalities by the AP’s optimal solution. In this work, we propose an application of the relax and cut technique to the multi-commodity formulation for the TSP. The results obtained by the computational study are encouraging, with the implementation of an algorithm that generates good dual bounds in low running time
7

Relax and cut : limitantes duais para o problema do caixeiro viajante /

Kawashima, Makswell Seyiti. January 2014 (has links)
Orientador: Maria do Socorro Nogueira Rangel / Banca: Maristela Oliveira dos Santos / Banca: Valeriano Antunes de Oliveira / Resumo: O Problema do Caixeiro Viajante (PCV) é um problema clássico de Otimização Combinatória. Dado um conjunto de cidades e os custos de viagem entre cada par delas, o objetivo é encontrar um roteiro que passa em todas as cidades apenas uma vez e retorna à cidade de origem de menor custo total. O enunciado simples e resolução não trivial encantaram muitas pessoas ao longo dos anos. Na literatura são apresentadas diversas formulações matemáticas para o Problema do Caixeiro Viajante, além de comparações entre a qualidade da relaxação linear de tais formulações. A formulação clássica para o PCV é forte, porém possui um número exponencial de restrições, e é equivalente à formulação de multiproduto (multi-commodity), de ordem polinomial. O custo computacional para resolver a relaxação linear da formulação multiproduto é alto, incentivando a busca de novas formas de obter limitantes duais. Na literatura são propostos procedimentos para obtenção de limitantes duais para o PCV utilizando-se do método relax and cut, a partir do problema da designação (PD), dualizando inequações válidas que são violadas pela solução ótima do PD. Neste trabalho, propomos a aplicação do método relax and cut para a formulação do PCV com restrições de multiproduto. Os resultados obtidos no estudo computacional são encorajadores, com a implementação de um algoritmo que gera bons limitantes duais com baixo tempo computacional / Abstract: The Traveling Salesman Problem (TSP) is a classical Combinatorial Optimization problem. Given a set of cities and travel costs between each pair of them, the objective is to find a tour through all the cities, visiting each city once, and returning to the city of origin with minimum total cost. The simple enunciate and non-trivial resolution enchanted many people through the years. In the literature various formulations for the Traveling Salesman Problem are presented, and the quality of the linear relaxation of such formulations is compared. The classical TSP formulation is strong, but have an exponencial number of constraints, and is equivalent to the multi-commodity formulation, of polinomial order. The computational cost to solve the linear relaxation of the multi-commodity formulation is high, stimulating the search of new ways of obtaining dual bounds. In the literature, procedures to obtain dual bounds to the TSP using the relax and cut technique are proposed, starting from the assignment problem (AP) and dualizing violated valid inequalities by the AP's optimal solution. In this work, we propose an application of the relax and cut technique to the multi-commodity formulation for the TSP. The results obtained by the computational study are encouraging, with the implementation of an algorithm that generates good dual bounds in low running time / Mestre
8

Um algoritmo de otimização por nuvem de partículas para resolução de problemas combinatórios

Rosendo, Matheus 26 November 2010 (has links)
Resumo: O Particle Swarm Optimization (PSO) pertence a uma classe de algoritmos inspirados em comportamentos sociais naturais inteligentes, chamada Swarm Intelligence (SI). O algoritmo PSO tem sido aplicado com sucesso na resolução de problemas de otimização contínua, no entanto, o seu potencial em problemas discretos não foi suficientemente explorado. Trabalhos recentes têm proposto a implementação de PSO usando algoritmos de busca local e Path relinking com resultados promissores. Este trabalho tem como objetivo apresentar um algoritmo PSO como um meta-modelo que utiliza internamente busca local e Path relinking, mas diferentemente das abordagens anteriores, o algoritmo proposto mantém o conceito principal de PSO para a atualização da velocidade da partícula. O trabalho descreve o algoritmo proposto como uma plataforma geral para problemas combinatórios. Tal proposta é validada em duas implementações: uma aplicada ao Problema do Caixeiro Viajante e outra ao Problema da Mochila. As peculiaridades e uma série de experimentos de calibragem de ambos os algoritmos são relatados. Finalmente, a qualidade do algoritmo proposto é testada na comparação com outros PSO discretos da literatura recente e também com outro conhecido algoritmo de metaheurística: o Ant Colony Optimization (ACO). Os resultados são encorajadores e reforçam a idéia de que o algoritmo PSO também pode ser competitivo em espaço de busca discreto, assim como levam a crer que a utilização de métodos dependentes do problema pode ser uma excelente alternativa na aplicação de PSO a este tipo de problema.
9

Algoritmo Simulated Annealing

Araujo, Haroldo Alexandre de January 2001 (has links)
Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. / Made available in DSpace on 2012-10-18T13:35:55Z (GMT). No. of bitstreams: 1 225675.pdf: 796704 bytes, checksum: 892abc8468e4e7c6715b6c3f2de50e51 (MD5) / A busca por soluções de problemas por meio do computador é o tema central da ciência da computação, relevante para grande parte da ciência e de suas aplicações tecnológicas. Essa busca, certamente, vai na direção de algoritmos eficientes e exatos mas que nem sempre boas soluções podem ser encontradas para muitos problemas de ordem prática, principalmente, no que diz respeito a tempo de execução. Existem problemas, dentre estes, os de otimização combinatorial que apresentam uma peculiaridade com relação aos outros, que é a grande dificuldade de se obter soluções exatas num tempo computacional aceitável. Atualmente, as novas técnicas, especialmente as metaheurísticas, tais como: Tabu Search, Simulated Annealing, Algoritmos Genéticos e Redes Neurais, vêm conseguindo sucesso na solução de problemas de otimização combinatorial, que mesmo não apresentando soluções exatas têm mostrado bastante eficiência com suas soluções aproximadas. Este trabalho propõe um novo método baseado no algoritmo Simulated Annealing (SA) através de mudanças bruscas nos valores da temperatura que são retiradas de múltiplas faixas, ao contrário do SA básico, onde esses valores são obtidos de uma faixa única, ou seja, num SA básico, os valores assumidos pela temperatura saem de um intervalo, partindo de um valor inicial, e vão diminuindo até um valor final. Tais mudanças bruscas acontecem exatamente no momento da mudança de faixa, pois o valor da temperatura que no final de uma faixa é pequeno, assume um valor correspondente a temperatura inicial da faixa seguinte, normalmente, bem maior. Posto a prova, com instâncias euclidianas do Problema Caixeiro Viajante, que é um problema de otimização combinatorial de difícil solução, o método apresenta resultados bastante satisfatórios quando comparado com o SA básico.
10

Uma abordagem híbrida para solucionar problemas de otimização através dos algoritmos

Raulino, Rangel Gustavo January 2002 (has links)
Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. / Made available in DSpace on 2012-10-20T01:56:40Z (GMT). No. of bitstreams: 0Bitstream added on 2014-09-26T01:34:48Z : No. of bitstreams: 1 184222.pdf: 2267157 bytes, checksum: b39836151adad0ce7ab117995de5a116 (MD5) / Este trabalho tem como objetivo principal o desenvolvimento de uma abordagem híbrida para a solução de problemas de otimização, em especial os combinatórios. Esta nova abordagem tem como base dois dos mais importantes modelos computacionais inteligentes utilizados na otimização de problemas, os algoritmos: genético e simulated annealing. O primeiro baseia-se na evolução natural e cromossômica das espécies vivas e o segundo no recozimento (annealing) de sólidos. Ambos são algoritmos de otimização (algoritmos que buscam por uma solução aceitável, o que não garante que a mesma seja a melhor). Nesta abordagem, o algoritmo genético é utilizado como algoritmo principal e o algoritmo simulated annealing é introduzido no processo do algoritmo genético como sendo um operador genético. Para avaliar o desempenho desta nova abordagem, foram realizados testes utilizando um dos mais conhecidos benchmarks na área de otimização, o problema do caixeiro viajante, e os resultados obtidos estão demonstrados neste trabalho.

Page generated in 0.1223 seconds