An algorithmic study of the Steiner Multicycle Problem

Abstract

No Problema de Multiciclo de Steiner (SMCP), temos um grafo G, uma função de custo c : E(G) → R≥ e uma coleção de conjuntos de terminais {T1, . . . , Tk}, onde para cada a em [k] Ta é um subconjunto de V (G) e esses conjuntos de terminais são disjuntos. O problema consiste em encontrar um conjunto de custo mínimo de ciclos disjuntos em vértices tal que, para cada a em [k], todos os vértices de Ta pertençam a um mesmo ciclo. Existem aplicações relacionadas a problemas de roteamento que podem ser traduzidas em instâncias do SMCP. Mais precisamente, o SMCP modela um cenário de transporte de cargas pequenas, onde diversas empresas devem visitar periodicamente os locais de coleta e entrega. Para reduzir seus custos individuais, essas empresas podem colaborar para criar rotas compartilhadas que visitem vários locais de coleta e entrega, de forma a reduzir os custos totais de transporte. Claramente, o SMCP é uma generalização do Problema do Caixeiro Viajante e, portanto, não admite um esquema de aproximação em tempo polinomial (PTAS), mesmo no caso métrico. Um ponto positivo é que a literatura para o SMCP descreve um PTAS para instâncias euclidianas. Nesse trabalho, generalizamos este resultado mostrando um PTAS para SMCP em grafos de largura de árvore limitada e, a partir deste, derivamos um PTAS para grafos de genus limitado. O algoritmo proposto é essencialmente uma adaptação do PTAS para o Problema da Floresta de Steiner em grafos de genus limitado. Além disso, implementamos o algoritmo 3-aproximado para SMCP proposto por Fernandes et al. [2024] em grafos métricos completos e executamos experimentos computacionais. Os custos das soluções produzidas por este algoritmo são em média 34% piores do que as soluções ótimas correspondentes, o que é consideravelmente melhor do que a garantia teórica. Por outro lado, o tempo de execução da implementação é em geral pior do que as outras heurísticas apresentadas na literatura.