Problema do caixeiro viajante negociante

In this paper, the Traveling Tradesman Problem (TTP) is proposed, a variant of the Traveling Purchaser Problem previously not described in the literature. In this problem there are a set of vertices, which act as markets, where the tradesman can buy or sell goods. Thus, he seeks to buy a certain...

ver descrição completa

Na minha lista:
Detalhes bibliográficos
Autor principal: Souza, Quézia Emanuelly de Oliveira
Outros Autores: Goldbarg, Marco Cesar
Formato: Dissertação
Idioma:pt_BR
Publicado em: Universidade Federal do Rio Grande do Norte
Assuntos:
Computação
Otimização
Metaheurísticas
Problema do caixeiro negociante
Endereço do item:https://repositorio.ufrn.br/handle/123456789/47519
Tags: Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
id ri-123456789-47519
record_format dspace
spelling ri-123456789-475192022-06-03T00:18:44Z Problema do caixeiro viajante negociante Souza, Quézia Emanuelly de Oliveira Goldbarg, Marco Cesar http://lattes.cnpq.br/9570841124785452 http://lattes.cnpq.br/1371199678541174 Menezes, Matheus da Silva Goldbarg, Elizabeth Ferreira Gouvea http://lattes.cnpq.br/2888641121265608 Maia, Silvia Maria Diniz Monteiro Computação Otimização Metaheurísticas Problema do caixeiro negociante In this paper, the Traveling Tradesman Problem (TTP) is proposed, a variant of the Traveling Purchaser Problem previously not described in the literature. In this problem there are a set of vertices, which act as markets, where the tradesman can buy or sell goods. Thus, he seeks to buy a certain product in one city and sell it in another, so that this operation provides profit. The purpose of the problem is to determine a Hamiltonian cycle that visits all the vertices of a subset just once, carrying out purchase and sale operations, in order to maximize the profit obtained. It is proposed a detailed description of the problem, the development of instances for it, in addition to two metaheuristics solution in order to obtain competitive results, one GRASP and one Transgenetic algorithm, which were tested in instances ranging from 50 to 350 vertices. Finally, From the results obtained, it was possible to conclude that the transgenetic approach was able to find better results than GRASP, although it required a higher processing time. Neste trabalho é proposto o Problema do Caixeiro Viajante Negociante (PCV-N), uma variante do Problema do Caixeiro Comprador até então não descrita na literatura. Neste problema existe um conjunto de vértices, que atuam como mercados, onde o caixeiro pode comprar ou vender mercadorias. Assim, ele busca comprar um determinado produto em uma cidade e vender em uma outra, de forma que essa operação possa fornecer lucro. O objetivo geral do problema é determinar um ciclo hamiltoniano que visite todos os vértices de um subconjunto uma única vez, realizando operações de compra e venda, de modo a maximizar o lucro obtido. É proposta a descrição detalhada do problema, o desenvolvimento das instâncias para o mesmo, além de duas metaheurísticas de solução visando a obtenção de resultados competitivos, sendo um GRASP e um algorotimo Transgenético, os quais foram testadas em instâncias que vão de 50 até 350 vértices. Por fim, a partir dos resultados obtidos, foi possível concluir que a abordagem transgenética conseguiu encontrar resultados melhores do que o GRASP, embora tenha exigido um tempo de processamento superior. 2022-06-03T00:18:11Z 2022-06-03T00:18:11Z 2022-02-14 masterThesis SOUZA, Quézia Emanuelly de Oliveira. Problema do caixeiro viajante negociante. 2022. 58f. Dissertação (Mestrado em Sistemas e Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2022. https://repositorio.ufrn.br/handle/123456789/47519 pt_BR Acesso Aberto application/pdf Universidade Federal do Rio Grande do Norte Brasil UFRN PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO
institution Repositório Institucional
collection RI - UFRN
language pt_BR
topic Computação
Otimização
Metaheurísticas
Problema do caixeiro negociante
spellingShingle Computação
Otimização
Metaheurísticas
Problema do caixeiro negociante
Souza, Quézia Emanuelly de Oliveira
Problema do caixeiro viajante negociante
description In this paper, the Traveling Tradesman Problem (TTP) is proposed, a variant of the Traveling Purchaser Problem previously not described in the literature. In this problem there are a set of vertices, which act as markets, where the tradesman can buy or sell goods. Thus, he seeks to buy a certain product in one city and sell it in another, so that this operation provides profit. The purpose of the problem is to determine a Hamiltonian cycle that visits all the vertices of a subset just once, carrying out purchase and sale operations, in order to maximize the profit obtained. It is proposed a detailed description of the problem, the development of instances for it, in addition to two metaheuristics solution in order to obtain competitive results, one GRASP and one Transgenetic algorithm, which were tested in instances ranging from 50 to 350 vertices. Finally, From the results obtained, it was possible to conclude that the transgenetic approach was able to find better results than GRASP, although it required a higher processing time.
author2 Goldbarg, Marco Cesar
author_facet Goldbarg, Marco Cesar
Souza, Quézia Emanuelly de Oliveira
format masterThesis
author Souza, Quézia Emanuelly de Oliveira
author_sort Souza, Quézia Emanuelly de Oliveira
title Problema do caixeiro viajante negociante
title_short Problema do caixeiro viajante negociante
title_full Problema do caixeiro viajante negociante
title_fullStr Problema do caixeiro viajante negociante
title_full_unstemmed Problema do caixeiro viajante negociante
title_sort problema do caixeiro viajante negociante
publisher Universidade Federal do Rio Grande do Norte
publishDate 2022
url https://repositorio.ufrn.br/handle/123456789/47519
work_keys_str_mv AT souzaqueziaemanuellydeoliveira problemadocaixeiroviajantenegociante
_version_ 1773958753699233792

Registros relacionados