• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 47
  • 2
  • 2
  • 2
  • 2
  • 2
  • Tagged with
  • 48
  • 48
  • 48
  • 24
  • 24
  • 23
  • 21
  • 19
  • 12
  • 11
  • 10
  • 9
  • 9
  • 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.
11

Implementação e análise do problema caixeiro viajante usando uma nova abordagem através dos algoritmos genético e simulated annealing

Ramos, José Márcio Benite 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-18T06:08:41Z (GMT). No. of bitstreams: 1 250657.pdf: 450883 bytes, checksum: 0da3746d8dd41bb89849d2e66115f5fa (MD5) / Atualmente observa-se uma forte tendência em se utilizar métodos aproximados na resolução de problemas de otimização combinatorial. Esses métodos, que muitas vezes vêm em substituição a métodos exatos, nem sempre garantem uma solução ótima para um problema, porém, normalmente são capazes de oferecer solução aproximada de boa qualidade, em um tempo de processamento aceitável. Neste trabalho é apresentada e investigada uma nova proposta de um método de aproximação baseado na combinação dos algoritmos Genético (AG) e Simulated Annealing (SA). Na observação do seu comportamento foi utilizado o notório problema de otimização combinatorial, de complexidade NP-completo, conhecido como o Problema do Caixeiro Viajante (PCV).
12

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.
13

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
14

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.
15

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
16

Times assincronos para resolução de problemas de otimização combinatoria com multiplas funções objetivo

Rodrigues, Rosiane de Freitas 05 July 1996 (has links)
Orientador: Pedro Sergio de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-21T13:12:10Z (GMT). No. of bitstreams: 1 Rodrigues_RosianedeFreitas_M.pdf: 9358851 bytes, checksum: aa44aaf61d515209c1ff85e92e7915a9 (MD5) Previous issue date: 1996 / Resumo: Times Assíncronos (do inglês Asynchronous Teams ou A-Teams) constituem uma abordagem multi-algorítmica para a resolução aproximada de problemas, cujo princípio básico é a cooperação sinérgica entre um conjunto de algoritmos, que se comunicam assincronamente através de memórias compartilhadas, propiciando soluções de melhor qualidade do que as geradas pelos mesmos algoritmos quando executados isoladamente. Este método tem sido aplicado com sucesso em problemas combinatórios com uma única função objetivo. O presente trabalho apresenta Times Assíncronos como sendo adequado à resolução de problemas de otimização combinatória com múltiplas funções objetivo. Diferentes estratégias para a manipulação de soluções multidimensionais foram desenvolvidas, tornando possível a rápida obtenção de soluções próximas ou mesmo pertencentes ao Pareto Ótimo do problema. Em especial, foi desenvolvida uma estrutura de manipulação de soluções multidimensionais que possibilita a consideração simultânea de todos os objetivos envolvidos para a geração de soluções. É proposto um novo problema NP-dificil como uma generalização do clássico Problema do Caixeiro Viajante (do inglês Traveling Salesman Problema ou TSP), onde ao invés de apenas uma matriz de distância existem múltiplas matrizes, sendo intitulado Problema do Caixeiro Viajante com Múltiplas Distâncias (do inglês Multi-Distance Traveling Salesman Problem ou MDTSP) e ao qual foi aplicado o método de Times Assíncronos. Os testes computacionais foram realizados de forma concorrente e paralela, obtendo-se conjuntos de soluções não-dominadas bem distribuídas dentro de uma ampla faixa de valores fornecidos pelas funções objetivo envolvidas, para todas as instâncias, mesmo envolvendo várias dimensões. Isto demonstra que os melhores conjuntos de soluções não-dominadas gerados pelos AT eams foram numerosos e contiveram soluções significativamente distintas entre s~ abrangendo todo o espectro desejado. Para as menores instâncias foi possível constatar que o melhor conjunto de soluções não-dominadas obtido fora o próprio Pareto Otimo. Ainda, foram desenvolvidos algoritmos para o novo problema que incorporam conceitos adequados a problemas multiobjetivos / Abstract: Asynchronous Teams or A-Teams constitute a mu1ti-algorithm approach for approximated problem solving, whose basic principle is the sinergic cooperation among a set of algorithms that communicate asynchronously through shared memories, providing solutions of better quality than those generated by the same algorithms when executed separately. This method has been successfully applied to Combinatorial Optimization Problems with a single objective function. This work presents Asynchronous Teams as an adequated method to solving Combinatorial Optimization Problems with multiple objective junctions. Different strategies to the manipulation of multi-dimensional solutions were developed, allowing it possible to obtain near-optimal or Pareto Optimal solutions quickly. In special, was developed a structure for multidimensional solution manipulation that allowing it possible the simultanea consideration of all objectives involved to the solution generation. It is proposed a new NP-hard problem as a generalization of classic Traveling Salesman Problem or TSP, which, instead of only one distance matrix, has various matrices. It has been entitled of Multi-Distance Traveling Salesman Problem or MDTSP and to which was applied the Asynchronous Teams method. The implementation tests were accomplished in a concurrent and parallel way, obtaining set of non-dominated solutions well-distributed on a wide range of values provided by the objective functions involved, over the tested instances. This demonstrates that the best sets of non-dominated solutions obtained are numerous and contain solutions significantly distinct among them. To the small instances was possible to show that the best set of non-dominated solutions generated was the Pareto Optimal. Algorithms have been developed for the new problem with the incorporation of compromisse decision and dominance concepts. Still, were developed algorithms to the new problem that incorpore adequated concepts to multiobjective problems / Mestrado / Mestre em Ciência da Computação
17

Algoritmos memeticos paralelos aplicados a problemas de otimização combinatoria

Garcia, Vinicius Jacques 01 August 2018 (has links)
Orientador : Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-01T22:11:51Z (GMT). No. of bitstreams: 1 Garcia_ViniciusJacques_M.pdf: 1139020 bytes, checksum: 17565f60e3c310bc25176ac8734a07b6 (MD5) Previous issue date: 2002 / Mestrado
18

Reformulações para o problema integrado de dimensionamento e sequenciamento da produção

Maldonado, Michelli [UNESP] 14 August 2015 (has links) (PDF)
Made available in DSpace on 2016-05-17T16:51:22Z (GMT). No. of bitstreams: 0 Previous issue date: 2015-08-14. Added 1 bitstream(s) on 2016-05-17T16:54:57Z : No. of bitstreams: 1 000863325_20170814.pdf: 1379523 bytes, checksum: db1556043273e4889e27702a2bf223ce (MD5) Bitstreams deleted on 2017-08-18T12:37:07Z: 000863325_20170814.pdf,. Added 1 bitstream(s) on 2017-08-18T12:37:52Z : No. of bitstreams: 1 000863325.pdf: 2314226 bytes, checksum: 152290accc1d5181a771e05181b739cf (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / A Pesquisa Operacional se tornou uma aliada de diversos problemas reais, principalmente de problemas da indústria, cujo objetivo é minimizar seus custos. Um dos problemas de muitos gestores é determinar quanto produzir, quando produzir e em que ordem produzir. Para responder essas três perguntas simultaneamente é têm-se que resolver o problema integrado de dimensionamento de lotes e sequenciamento da produção. O presente trabalho vem trazer modelos matemáticos que podem ser adaptados em diversos estudos de casos para responder a questão tríplice: quanto, quando e em que ordem, tudo isso, minimizando os custos de estoque, atraso e troca. A tese responde a seguinte pergunta, até então uma lacuna na literatura, entre os modelos que integram dimensionamento e sequenciamento da produção, qual é o melhor? Cinco modelos foram propostos e estudados do ponto de vista teórico e computacional para então descobrir o melhor. A construção dos modelos foi baseada no artigo de Oncam et al. (2009) que apresenta resultados teóricos e computacionais para mostrar qual o melhor modelo para o problema do caixeiro viajante. Esperava-se que os resultados fossem similares. Porém, o melhor modelo para o problema integrado de dimensionamento de lotes e sequenciamento da produção é diferente do melhor modelo para o problema do caixeiro viajante / Operational Research has become an ally of several real problems, especially problems of industry, whose objective is to minimize their costs. One of the problems of many managers is to determine how much to produce, when to produce and in what order produce. To answer these three questions simultaneously simply solve the integrated problem of lot sizing and sequencing of production. This work presents mathematical models that can be adapted in several case studies to answer the threefold question: how much, when and in what order, all while minimizing inventory costs, delay and return. This thesis is interested on the question, What is the best model for the integrate lot sizing and scheduling problem?. ItWere proposed five models and theys were studied in the theoretical and computational viewpoint. All models was based in the travelling salesman problem (TSP). And the results show that the integrate lot sizing and scheduling problem based in the TSP isn't the same model for the TSP / FAPESP: 2010/19006-0
19

Reformulações para o problema integrado de dimensionamento e sequenciamento da produção /

Maldonado, Michelli. January 2015 (has links)
Orientador: Maria do Socorro Nogueira Rangel / Banca: Horácio Hideki Yanasse / Banca: Maristela Oliveira dos Santos / Banca: Hélio Yochihiro Fuchigami / Banca: Valeriano Antunes de Oliveira / Resumo: A Pesquisa Operacional se tornou uma aliada de diversos problemas reais, principalmente de problemas da indústria, cujo objetivo é minimizar seus custos. Um dos problemas de muitos gestores é determinar quanto produzir, quando produzir e em que ordem produzir. Para responder essas três perguntas simultaneamente é têm-se que resolver o problema integrado de dimensionamento de lotes e sequenciamento da produção. O presente trabalho vem trazer modelos matemáticos que podem ser adaptados em diversos estudos de casos para responder a questão tríplice: quanto, quando e em que ordem, tudo isso, minimizando os custos de estoque, atraso e troca. A tese responde a seguinte pergunta, até então uma lacuna na literatura, entre os modelos que integram dimensionamento e sequenciamento da produção, qual é o melhor? Cinco modelos foram propostos e estudados do ponto de vista teórico e computacional para então descobrir o melhor. A construção dos modelos foi baseada no artigo de Oncam et al. (2009) que apresenta resultados teóricos e computacionais para mostrar qual o melhor modelo para o problema do caixeiro viajante. Esperava-se que os resultados fossem similares. Porém, o melhor modelo para o problema integrado de dimensionamento de lotes e sequenciamento da produção é diferente do melhor modelo para o problema do caixeiro viajante / Abstract: Operational Research has become an ally of several real problems, especially problems of industry, whose objective is to minimize their costs. One of the problems of many managers is to determine how much to produce, when to produce and in what order produce. To answer these three questions simultaneously simply solve the integrated problem of lot sizing and sequencing of production. This work presents mathematical models that can be adapted in several case studies to answer the threefold question: how much, when and in what order, all while minimizing inventory costs, delay and return. This thesis is interested on the question, "What is the best model for the integrate lot sizing and scheduling problem?". ItWere proposed five models and theys were studied in the theoretical and computational viewpoint. All models was based in the travelling salesman problem (TSP). And the results show that the integrate lot sizing and scheduling problem based in the TSP isn't the same model for the TSP / Doutor
20

An?lise experimental de varia??es da heur?stica de Lin e Kernighan para o problema do caixeiro viajante multiobjetivo / Experimental analisy of variants of the Lin and Kernighan?s heuristic for the multi-objective traveling salesman problem

Carvalho, Emerson Bezerra de 24 July 2017 (has links)
Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-11-01T21:17:49Z No. of bitstreams: 1 EmersonBezerraDeCarvalho_DISSERT.pdf: 1150853 bytes, checksum: f0f5998d8f74eb082da1133fbcf4b27a (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-11-07T21:35:18Z (GMT) No. of bitstreams: 1 EmersonBezerraDeCarvalho_DISSERT.pdf: 1150853 bytes, checksum: f0f5998d8f74eb082da1133fbcf4b27a (MD5) / Made available in DSpace on 2017-11-07T21:35:18Z (GMT). No. of bitstreams: 1 EmersonBezerraDeCarvalho_DISSERT.pdf: 1150853 bytes, checksum: f0f5998d8f74eb082da1133fbcf4b27a (MD5) Previous issue date: 2017-07-24 / A heur?stica de Lin e Kernighan (LK) ? um dos m?todos mais eficientes para o Problema do Caixeiro Viajante (PCV). Devido a este fato, diferentes implementa??es para a LK foram propostas na literatura e esta heur?stica ? tamb?m usada como parte de diversos algoritmos meta-heur?sticos. A heur?stica LK tem sido utilizada no contexto do PCV multiobjetivo (PCVM) conforme proposta originalmente por seus autores, isto ?, com o foco mono-objetivo. Este trabalho investiga a extens?o da heur?stica LK no contexto multiobjetivo. ? investigado o potencial de extens?es da LK combinadas com outras t?cnicas meta-heur?sticas. Resultados de um experimento computacional para inst?ncias do PCVM com 2, 3 e 4 objetivos s?o reportados. / The Lin and Kernighan?s heuristic (LK) is one of the most effective methods for the Traveling Salesman Problem (TSP). Due to this fact, different implementations for the LK were proposed in literature and this heuristic is also used as part of various meta-heuristic algorithms. LK has been used in the context of the multi-objective TSP (MTSP) as originally proposed by its authors, i.e., with a single objective focus. This study investigates variants of the LK heuristic in the multi-objective context. We investigate the potential of LK extensions combined with other metaheuristic techniques. Results of a computational experimental are reported for MTSP instances with 2, 3 and 4 objectives.

Page generated in 0.1201 seconds