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 | Barboza, Eduardo Uchoa | - |
Autor(es): dc.contributor | Roboredo, Marcos Costa | - |
Autor(es): dc.contributor | Simonetti, Luidi Galabert | - |
Autor(es): dc.contributor | Pinto, Rafael Martinelli | - |
Autor(es): dc.contributor | Frota, Yuri Abtbol de Menezes | - |
Autor(es): dc.creator | Barbosa, Luiz Henrique Sant’anna | - |
Data de aceite: dc.date.accessioned | 2024-07-11T18:04:53Z | - |
Data de disponibilização: dc.date.available | 2024-07-11T18:04:53Z | - |
Data de envio: dc.date.issued | 2018-09-21 | - |
Data de envio: dc.date.issued | 2018-09-21 | - |
Data de envio: dc.date.issued | 2018 | - |
Fonte completa do material: dc.identifier | https://app.uff.br/riuff/handle/1/7606 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/763138 | - |
Descrição: dc.description | O Problema do Caixeiro Viajante com Seleção de Hotéis é uma extensão do problema clássico do caixeiro viajante apresentado recentemente na literatura onde há um limite diário de tempo de forma que podem ser necessárias múltiplas viagens para visitar todos os clientes e há um conjunto de hotéis disponíveis para que o caixeiro possa pernoitar. Além de ser um problema interessante do ponto de vista da Otimização Combinatória, o PCVSH possui também relevância em aplicações reais. As abordagens apresentadas na literatura até o momento são baseadas principalmente em algoritmos heurísticos. A ausência de um algoritmo exato robusto para este problema dificulta o aprofundamento de seu estudo. Esta tese apresenta uma formulação de programação inteira de particionamento de conjuntos e propõe algoritmo Branch-Cut-and-Price utilizando um algoritmo de labeling para a resolução do problema de pricing. Restrições de eliminação de subciclo, 2-Path e Subset Row Cuts são separados. Diversas instâncias da literatura de até 225 clientes são resolvidas e um novo conjunto de 240 instâncias também é apresentado onde resultados ótimos são obtidos para instâncias de até 100 clientes | - |
Descrição: dc.description | The Traveling Salesperson Problem with Hotel Selection (TSPHS) is an extension of the classic Traveling Salesperson Problem that has only recently been introduced in the literature, where there is a daily travel limit such that several trips might be necessary to visit all clients and there is a set of available hotels for the salesperson to stay in between trips. The TSPHS not only presents an interesting optimization challenge, but also has a strong relevance in real world applications. Current approaches focus mainly in meta-heuristic techniques. The lack of a robust exact algorithm limits the extent to which this problem can be studied. This thesis presents a set partitioning Integer Programing formulation and proposes a branch-cut-and-price algorithm, where the pricing subproblem is solved through a labeling algorithm. Subtour elimination constraints, 2-Path and Subset Row Cuts are separated. Several instances of the literature of up to 225 clients are solved to optimality and a new set of 240 benchmark instances is presented where optimal solutions are obtained for instances of up to 100 clients | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Direitos: dc.rights | openAccess | - |
Direitos: dc.rights | CC-BY-SA | - |
Palavras-chave: dc.subject | Geração de colunas | - |
Palavras-chave: dc.subject | Branch-cut-and-price | - |
Palavras-chave: dc.subject | Problema do caixeiro viajante com seleção de hotéis | - |
Palavras-chave: dc.subject | Pesquisa operacional | - |
Palavras-chave: dc.subject | Otimização combinatória | - |
Palavras-chave: dc.subject | Programação inteira | - |
Palavras-chave: dc.subject | Programação dinâmica | - |
Palavras-chave: dc.subject | Column generation | - |
Palavras-chave: dc.subject | Traveling salesperson problem with hotel selection | - |
Título: dc.title | A branch-cut-and-price algorithm for the traveling salesperson problem with hotel selection | - |
Tipo de arquivo: dc.type | Tese | - |
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: