Exact approaches for network topology and routing problems

Abstract

Nesta tese, investigamos abordagens de solução exata para o p-arborescence star problem (p-ASP) e o pickup and delivery traveling salesman problem with multiple stacks (PDTSPMS). Esses dois problemas de otimização combinatória possuem aplicações no projeto de redes de sensores sem fio e no planejamento de rotas veiculares sob restrições de carregamento, respectivamente. Para o p-ASP, nós desenvolvemos algoritmos branch-and-cut baseados em cada uma das nossas duas formulações propostas e melhoramos um algoritmo branch-and-cut anterior para o problema com um método de separação exata. Além disso, provamos que encontrar uma solução viável para uma instância arbitrária do p-ASP é NP-difícil e introduzimos procedimentos de pré-processamento. Para instâncias do benchmark de tamanho pequeno e médio, nossos algoritmos propostos obtém os melhores resultados. Para as instâncias maiores, nosso melhor algoritmo mostra-se competitivo com a versão melhorada da abordagem existente. Ambos os algoritmos têm desempenho similar para essas instâncias difíceis e resolvem uma instância que o outro não é capaz. Com relação ao PDTSPMS, propomos uma nova formulação junto com novas desigualdades válidas. As novas desigualdades válidas são versões fortalecidas de desigualdades usadas com sucesso em algoritmos para o problema e suas variantes. Em seguida, implementamos um algoritmo branch-and-cut baseado na formulação proposta que incorpora as desigualdades válidas. Além disso, também apresentamos várias estratégias de aceleração para nosso método. O algoritmo é comparado com todas as abordagens exatas para o PDTSPMS encontradas na literatura. Nosso algoritmo implementado supera todos os algoritmos para as instâncias de benchmark. Além de reduzir drasticamente o tempo necessário para resolver a maioria das instâncias, o algoritmo proposto resolve mais instâncias no total do que os outros métodos.