Optimization algorithms for the Steiner team orienteering problem

Abstract

O Team Orienteering Problem (TOP) é um problema NP-difícil de roteamento em que uma frota homogênea de veículos tem por objetivo coletar prêmios disponíveis em um determinado número de localidades, enquanto respeitando restrições de tempo de percurso. No TOP, cada localidade pode ser visitada por, no máximo, um veículo, e o objetivo é maximizar o montante de prêmios coletados pelos veículos dentro de um limite de tempo pré-estabelecido. Na nossa pesquisa, propomos uma generalização do TOP, denominada Steiner Team Orienteering Problem (STOP). No STOP, é dado, adicionalmente, um subconjunto de localidades obrigatórias. Assim, o STOP também tem por objetivo maximizar o total de prêmios coletados dentro de um limite de tempo, mas, agora, cada localidade obrigatória deve ser visitada.

Como uma primeira contribuição, propomos para o STOP uma nova formulação baseada em produto e a usamos dentro de um esquema de planos de cortes. O algoritmo beneficia-se da compacidade e da força da formulação proposta e funciona separando cinco famílias de desigualdades válidas, a saber: restrições de conectividade, clássicas lifted cover inequalities baseadas em limites duais, uma classe de desigualdades denominadas arc-vertex inference cuts e duas classes de cortes baseados em vértices conflitantes. Até onde sabemos, as últimas três classes de desigualdades são também inéditas na literatura, sendo aqui introduzidas junto às suas respectivas provas de validade. Um algoritmo branch-and-cut que é estado-da-arte na literatura do TOP foi adaptado ao STOP e usado como baseline para avaliar a performance do algoritmo de planos de cortes proposto. Extensivos experimentos computacionais mostram a competitividade do novo algoritmo na resolução de instâncias do STOP e do TOP. Em particular, o algoritmo é capaz de resolver, no total, 14 instâncias do TOP a mais do que qualquer outro algoritmo exato na literatura, além de encontrar nove novos certificados de otimalidade. Com relação às novas instâncias do STOP introduzidas neste trabalho, nosso algoritmo resolve 31 instâncias a mais do que o baseline.

Neste trabalho, também provamos que encontrar uma solução viável para o STOP é NP-difícil e propomos uma heurística Large Neighborhood Search (LNS) para o problema. A heurística é inicializada com soluções obtidas pela matheurística conhecida pelo nome de Feasibility Pump, a qual, em nossa implementação, tem por base a formulação compacta que propomos para o STOP. A heurística LNS em si combina buscas locais clássicas da literatura de problemas de roteamento com um componente de memória de longo-prazo baseado em Path Relinking. Experimentos computacionais mostram a eficiência e eficácia da heurística proposta quando resolvendo um conjunto de 387 instâncias do STOP. No geral, as soluções heurísticas obtidas implicam um gap percentual de apenas 0.54% em relação aos melhores limites conhecidos para as instâncias. Em particular, a heurística atinge os melhores limites já sabidos em 382 das 387 instâncias utilizadas. Ademais, em 21 desses casos, nossa heurística é ainda capaz de melhorar esses limites.

Por fim, o algoritmo híbrido obtido ao inicializar o algoritmo de planos de cortes com as soluções providas pela heurística LNS é capaz de resolver na otimalidade quatro instâncias do TOP e sete instâncias do STOP a mais do que o algoritmo de planos de cortes sozinho. Além disso, o algoritmo híbrido obtém novos certificados de otimalidade para cinco instâncias do TOP ainda não resolvidas por nenhum outro algoritmo da literatura (incluindo nosso algoritmo de planos de cortes sem a ajuda da heurística).