UMA GENERALIZAÇÃO DO PROBLEMA DO CAIXEIRO VIAJANTE COM COBERTURA

Vol 53, 2021 - 139581
Trabalho completo (oral)
Favorite this paper
How to cite this paper?
Abstract

O problema do caixeiro viajante (travelling salesman problem - TSP) tem por objetivo encontrar um ciclo hamiltoniano de custo mínimo em um grafo não-direcionado completo G = (V, E). Uma variação do TSP, o problema do caixeiro viajante com cobertura (Covering Salesman Problem - CSP), visa obter um ciclo de custo mínimo que cobre todos os nós do grafo G, onde a cada vértice v é associado um conjunto de cobertura. Este trabalho apresenta uma generalização do CSP, o problema das p-medianas com cobertura (Covering Hamiltonian p-Medians Problem - CHpMP), cujo objetivo é encontrar em G um subgrafo de custo mínimo composto por p ciclos hamiltonianos disjuntos que cubram todos os nós de G. Uma formulação para este novo problema é apresentada, assim como ensaios computacionais para avaliar a solução exata do CHpMP.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Institutions
  • 1 Universidade Estadual de Campinas
Track
  • 14 - CO - ​​Combinatorial Optimization
Keywords
Otimização Combinatória
Problema do Caixeiro Viajante (PCV)
Programação linear inteira