Problema de orientação clusterizado com subgrupos
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Clustered orientation problem with subgroups
Primeiro orientador
Membros da banca
Cristiano Arbex Valle
Thiago Ferreira de Noronha
Thiago Ferreira de Noronha
Resumo
O planejamento de rotas é fundamental para otimizar processos logísticos e aumentar a eficiência no deslocamento de pessoas, mercadorias e robôs móveis. Em cenários onde não é possível visitar todos os destinos, torna-se necessário priorizar atendimentos com base na relação custo-benefício. O Orienteering Problem (OP) é um modelo clássico que busca maximizar a recompensa obtida dentro de um limite de tempo ou distância. A evolução das aplicações práticas desse problema deu origem a variantes como o Clustered Orienteering Problem (COP), no qual todos os pontos de um agrupamento devem ser visitados para se obter a recompensa, e o Set Orienteering Problem (SOP), que permite visitar no máximo um ponto por grupo. No entanto, essas formulações não representam adequadamente cenários que envolvem alternativas de visita com diferentes níveis de esforço e recompensa dentro de uma mesma região. Para lidar com essa limitação, esta dissertação propõe o Clustered Orienteering Problem with Subgroups (COPS), uma nova variante que generaliza o COP e o SOP ao introduzir subgrupos hierárquicos dentro dos grupos clusters. Nesse modelo, cada subgrupo oferece uma recompensa condicional à visita de todos os seus pontos, sendo permitido selecionar no máximo um subgrupo por grupo. O objetivo é determinar a rota que maximize a recompensa total, respeitando as restrições de orçamento. A proposta tem aplicações em logística, inspeção, monitoramento ambiental e, especialmente, no planejamento de rotas para robôs móveis. Para resolver o COPS, foram desenvolvidas duas abordagens: uma formulação exata em Programação Linear Inteira (ILP), adequada para instâncias menores, e uma heurística baseada em Busca Tabu, eficiente para instâncias de maior escala. Os resultados experimentais demonstram que a formulação ILP é viável apenas para instâncias pequenas e médias, reforçando a necessidade de métodos aproximativos em cenários mais complexos. O COPS-TABU apresentou desempenho competitivo em termos de qualidade das recompensas obtidas, superando ou igualando benchmarks adaptados do COP e do SOP. Além disso, os experimentos confirmam a aplicabilidade do modelo em cenários com clusterização complexa, rotas não circulares, múltiplos destinos e ambientes tridimensionais.
Abstract
Route planning plays a crucial role in optimizing logistics processes and enhancing the efficiency of the movement of people, goods, and mobile robots. In scenarios where visiting all destinations is not feasible, it becomes necessary to prioritize visits based on a cost–benefit trade-off. The Orienteering Problem (OP) is a classical optimization model that seeks to maximize the total collected reward within a given time or distance constraint. The evolution of practical applications has led to variants such as the Clustered Orienteering Problem (COP), in which all points within a cluster must be visited to obtain its reward, and the Set Orienteering Problem (SOP), which allows visiting at most one point per group. However, these formulations fail to adequately represent scenarios involving alternative options with varying levels of effort and reward within the same region. To address this limitation, this dissertation introduces the Clustered Orienteering Problem with Subgroups (COPS), a novel variant that generalizes both COP and SOP by incorporating hierarchical subgroups within clusters. In this formulation, each subgroup provides a conditional reward that is granted upon visiting all its points, while at most one subgroup can be selected per cluster. The objective is to determine the route that maximizes the total collected reward subject to a budget constraint. The proposed model has potential applications in logistics, inspection, environmental monitoring, and particularly in route planning for mobile robots. To solve COPS, two complementary approaches were developed: an exact Integer Linear Programming (ILP)
formulation suitable for small instances, and a Tabu Search-based heuristic designed for larger-scale problems. Experimental results show that the ILP approach is computationally feasible only for small and medium-sized instances, highlighting the need for heuristic or metaheuristic techniques for larger problems. The COPS-TABU method demonstrated competitive performance in terms of reward quality compared to adapted COP and SOP benchmarks, while also validating the applicability of the proposed model to complex clustering configurations, non-circular routes, multi-destination scenarios, and three-dimensional environments.
Assunto
Computação – Teses, Robótica- Teses, Otimização combinatória - Teses, Problema de otimização clusterizado – Teses, Problema de roteamento de veículos - Teses, Programação linear – Teses
Palavras-chave
Planejamento de rota, Problema de orientação, Problema de orientação agrupado, Problema de orientação por conjuntos, Problema de orientação agrupado com subgrupos, Busca tabu, Programação linear inteira