A branch-cut-and-price algorithm for the traveling salesperson problem with hotel selection

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorBarboza, Eduardo Uchoa-
Autor(es): dc.contributorRoboredo, Marcos Costa-
Autor(es): dc.contributorSimonetti, Luidi Galabert-
Autor(es): dc.contributorPinto, Rafael Martinelli-
Autor(es): dc.contributorFrota, Yuri Abtbol de Menezes-
Autor(es): dc.creatorBarbosa, Luiz Henrique Sant’anna-
Data de aceite: dc.date.accessioned2024-07-11T18:04:53Z-
Data de disponibilização: dc.date.available2024-07-11T18:04:53Z-
Data de envio: dc.date.issued2018-09-21-
Data de envio: dc.date.issued2018-09-21-
Data de envio: dc.date.issued2018-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/7606-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/763138-
Descrição: dc.descriptionO 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.descriptionThe 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.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsopenAccess-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectGeração de colunas-
Palavras-chave: dc.subjectBranch-cut-and-price-
Palavras-chave: dc.subjectProblema do caixeiro viajante com seleção de hotéis-
Palavras-chave: dc.subjectPesquisa operacional-
Palavras-chave: dc.subjectOtimização combinatória-
Palavras-chave: dc.subjectProgramação inteira-
Palavras-chave: dc.subjectProgramação dinâmica-
Palavras-chave: dc.subjectColumn generation-
Palavras-chave: dc.subjectTraveling salesperson problem with hotel selection-
Título: dc.titleA branch-cut-and-price algorithm for the traveling salesperson problem with hotel selection-
Tipo de arquivo: dc.typeTese-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.