Tese
Exact approaches for network topology and routing problems
Fecha
2021-05-18Autor
Armando Honorio Pereira
Institución
Resumen
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.