Made available in DSpace on 2014-12-17T15:48:11Z (GMT). No. of bitstreams: 1
LigiaBB.pdf: 1036516 bytes, checksum: 36260a287f3ddf0bc38abbb0ec32b82f (MD5)
Previous issue date: 2007-02-09 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The Traveling Purchaser Problem is a variant of the Traveling Salesman Problem, where there is a set of markets and a set of products. Each product is available on a subset of markets and its unit cost depends on the market where it is available. The objective is to buy all the products, departing and returning to a domicile, at the least possible cost defined as the summation of the weights of the edges in the tour and the cost paid to acquire the products. A Transgenetic Algorithm, an evolutionary algorithm with basis on endosymbiosis, is applied to the Capacited and Uncapacited versions of this problem. Evolution in Transgenetic Algorithms is simulated with the interaction and information sharing between populations of individuals from distinct species. The computational results show that this is a very effective approach for the TPP regarding solution quality and runtime. Seventeen and nine new best results are presented for instances of the capacited and uncapacited versions, respectively / O Problema do Caixeiro Comprador ? uma variante do Problema do Caixeiro Viajante, onde existe um conjunto de mercados e um conjunto de produtos. Cada produto est? dispon?vel em um subconjunto de mercados e o pre?o da unidade varia de acordo com o mercado. O objetivo ? comprar todos os produtos, partindo e retornando para o dep?sito, de maneira que a soma do custo da rota e dos produtos seja m?nimo. Um Algoritmo Transgen?tico, algoritmo evolucion?rio com base na endosimbiose, ? utilizado para resolver a vers?o Capacitada e N?o Capacitada desse problema. A evolu??o no algoritmo transgen?tico ? simulada com a intera??o e troca de informa??es entre popula??o de indiv?duos de diferentes esp?cies. Os resultados computacionais mostram que a abordagem ? satisfat?ria para o PCC , tanto na qualidade da solu??o, quanto no tempo de execu??o. Dezessete e nove novas melhores solu??es s?o encontradas para o PCC Capacitado e para o PCC N?o Capacitado, respectivamente
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/18112 |
| Date | 09 February 2007 |
| Creators | Bagi, Ligia Bariani |
| Contributors | CPF:25841025953, http://lattes.cnpq.br/1371199678541174, Volpi, Neida Maria Patias, CPF:20203535987, http://lattes.cnpq.br/4210080039913734, Gouv?a, Elizabeth Ferreira, Goldbarg, Marco C?sar |
| Publisher | Universidade Federal do Rio Grande do Norte, Programa de P?s-Gradua??o em Sistemas e Computa??o, UFRN, BR, Ci?ncia da Computa??o |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0014 seconds