Das Montanhas de Minas ao Oceano: Os Caminhos da Ciência para um Futuro Sustentável
20 a 25 de outubro de 2025
Trabalho 20364
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Dimensões Econômicas: ODS9 |
| Setor | Departamento de Informática |
| Bolsa | FAPEMIG |
| Conclusão de bolsa | Sim |
| Apoio financeiro | FAPEMIG |
| Primeiro autor | Cecília Cassab Prieto |
| Orientador | ANDRE GUSTAVO DOS SANTOS |
| Outros membros | Samuel Raimundo Lopes Pinto |
| Título | Otimização Combinatória Aplicada em Problemas de Programação da Produção e Transporte: Variações do TSP |
| Resumo | Neste trabalho, foram estudados dois problemas relacionados ao Problema do Caixeiro Viajante (Travelling Salesman Problem, TSP). No TSP, um caixeiro deseja encontrar uma rota de custo mínimo que visita uma vez cada cidade de um dado conjunto de cidades. É um problema de otimização combinatória amplamente estudado na literatura, classificado como NP-Difícil, para o qual não existe algoritmo exato eficiente. As variações aqui estudadas são um Problema de Planejamento de Viagens (Trip Planning Problem, TPP) e o Planejamento de Trilhas Recreativas (Planning of Recreational Trails, PRT) em áreas protegidas. No TPP, deve-se otimizar a rota de um turista, encontrando a sequência ideal de visita e estadia em um conjunto de cidades, atendendo requisitos de estadia mínima e máxima desejada pelo turista e de estar em cidades específicas em determinados dias. Deve-se otimizar o custo total da viagem. É mais geral que o TSP, pois envolve custos de estadia nas cidades, além dos custos de transporte. Para este problema, foi proposto um modelo de programação dinâmica combinado com uma busca exaustiva e um método ϵ-restrito que ajusta iterativamente o tempo máximo em deslocamentos. Com dados reais coletados de estadias e passagens aéreas de sete cidades europeias (Atenas, Berlim, Lisboa, Londres, Madri, Paris e Roma), foram geradas instâncias de teste que variam de 1 a 6 cidades em um período de 30 dias. No PRT, devem-se otimizar as trilhas em uma área protegida, como um parque estadual ou reservas florestais. Foram propostos modelos de programação linear inteira para uma versão TSP, em que todos os pontos de interesse devem ser visitados em um tempo mínimo e uma versão de orientação (Orienteering Problem, OP), em que se deseja visitar o melhor conjunto de pontos de interesse em um tempo limite. O primeiro caso é útil para um guarda-florestal, que precisa visitar diária ou semanalmente um conjunto específico de locais e o segundo caso é útil para um turista, visitante do parque, que tem um tempo limite e locais de preferência. Em ambos os casos foram usados dados públicos de Modelo Digital de Elevação (MDE) e o tempo de caminhada foi calculado por um algoritmo A* levando-se em conta o ângulo de inclinação em aclives e declives. Trata-se de um estudo inicial para geração de trilhas personalizadas. |
| Palavras-chave | otimização combinatória, tsp, roteamento. |
| Forma de apresentação..... | Painel |
| Link para apresentação | Painel |
|---|