Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Ochi, Luiz Satoru | - |
Autor(es): dc.contributor | CPF:31609080822 | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/9171815778534257 | - |
Autor(es): dc.contributor | Martinhon, Carlos Alberto de Jesus | - |
Autor(es): dc.contributor | CPF:31790806422 | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/2822582595834942 | - |
Autor(es): dc.contributor | Lavor, Carlile Campos | - |
Autor(es): dc.contributor | CPF:31870800722 | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/2019624495480547 | - |
Autor(es): dc.contributor | Barboza, Eduardo Uchoa | - |
Autor(es): dc.contributor | CPF:85462487922 | - |
Autor(es): dc.contributor | http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4721785E2 | - |
Autor(es): dc.contributor | Arroyo, José Elias Claudio | - |
Autor(es): dc.contributor | CPF:32009945122 | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/6685448343335507 | - |
Autor(es): dc.creator | Maciel, André Cordeiro Macedo | - |
Data de aceite: dc.date.accessioned | 2024-07-11T17:29:20Z | - |
Data de disponibilização: dc.date.available | 2024-07-11T17:29:20Z | - |
Data de envio: dc.date.issued | 2021-03-10 | - |
Data de envio: dc.date.issued | 2008-03-04 | - |
Data de envio: dc.date.issued | 2021-03-10 | - |
Data de envio: dc.date.issued | 2005-08-26 | - |
Fonte completa do material: dc.identifier | https://app.uff.br/riuff/handle/1/17815 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/751333 | - |
Descrição: dc.description | This work describes a generalization of the Traveling Salesman Problem - TSP called Black and White Traveling Salesman Problem - BWTSP. The BWTSP is defined in a graph G (oriented or not), in a such way that the associated vertex set is partitioned into black and white vertices. The objective is to find a shortest hamiltonian tour subject to Cardinality and Length constraints. These constraints are related to the number of white vertices (cardinality) and the total distance (length) between two consecutive black vertices in a feasible solution. The main applications of this problem are found in the telecomunication area and the scheduling of airline operations that incorporate maintenance conections. In this work we introduce mathematical formulations for asymmetrical and symmetrical BWTSP, we propose news construction and local search algorithms that are used in the metaheuristics GRASP, V NS and V ND. Computational results show the viability of the proposed methods. | - |
Descrição: dc.description | Este trabalho aborda uma extensão do Problema do Caixeiro Viajante - PCV denominado Problema do Caixeiro Viajante Branco e Preto-PCVBP. O PCV BP é definido sobre um grafo G (orientado ou não), de maneira que o conjunto de vértices associado está particionado em vértices brancos e pretos. O objetivo é encontrar um caminho hamiltoniano de custo mínimo sujeito a restrições adicionais de Cardinalidade e Comprimento. Estas restrições estão relacionadas respectivamente, ao número de vértices brancos (cardinalidade) e a distância total percorrida (comprimento) entre dois vértices pretos consecutivos em uma solução viável. As principais aplicações deste problema estão nas áreas de telecomunicação e escalonamento de operações aéreas que necessitam de manutenção de conexões. Neste trabalho introduzimos formulações matemáticas para o PCV BP assimétrico e simétrico, propomos novas heurísticas de construção e busca local que são utilizadas junto as metaheurísticas GRASP, V NS e V ND. Resultados computacionais comprovam a viabilidade dos métodos propostos. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Publicador: dc.publisher | Programa de Pós-Graduação em Computação | - |
Publicador: dc.publisher | Computação | - |
Direitos: dc.rights | Acesso Aberto | - |
Direitos: dc.rights | CC-BY-SA | - |
Palavras-chave: dc.subject | Metaheurística GRASP | - |
Palavras-chave: dc.subject | Heurística | - |
Palavras-chave: dc.subject | Caixeiro-viajante | - |
Palavras-chave: dc.subject | GRASP | - |
Palavras-chave: dc.subject | Regras de Redução | - |
Palavras-chave: dc.subject | V ND | - |
Palavras-chave: dc.subject | V NS | - |
Palavras-chave: dc.subject | Heuristics | - |
Palavras-chave: dc.subject | Metaheuristics | - |
Palavras-chave: dc.subject | The traveling salesman problem | - |
Palavras-chave: dc.subject | Reduction rules | - |
Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO | - |
Título: dc.title | Heurísticas para o problema do caixeiro viajante branco e preto | - |
Tipo de arquivo: dc.type | Dissertação | - |
Aparece nas coleções: | Repositório Institucional da Universidade Federal Fluminense - RiUFF |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: