dc.contributor | Geraldo Robson Mateus | |
dc.contributor | http://lattes.cnpq.br/6289602045034353 | |
dc.contributor | Sebastián Alberto Urrutia | |
dc.contributor | Haroldo Gambini Santos | |
dc.contributor | Rafael Augusto de Melo | |
dc.contributor | Rosiane de Freitas Rodrigues | |
dc.contributor | Gabriel de Morais Coutinho | |
dc.creator | Armando Honorio Pereira | |
dc.date.accessioned | 2021-09-20T00:24:03Z | |
dc.date.accessioned | 2022-10-03T23:40:11Z | |
dc.date.available | 2021-09-20T00:24:03Z | |
dc.date.available | 2022-10-03T23:40:11Z | |
dc.date.created | 2021-09-20T00:24:03Z | |
dc.date.issued | 2021-05-18 | |
dc.identifier | http://hdl.handle.net/1843/38088 | |
dc.identifier.uri | http://repositorioslatinoamericanos.uchile.cl/handle/2250/3826281 | |
dc.description.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. | |
dc.publisher | Universidade Federal de Minas Gerais | |
dc.publisher | Brasil | |
dc.publisher | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO | |
dc.publisher | Programa de Pós-Graduação em Ciência da Computação | |
dc.publisher | UFMG | |
dc.rights | Acesso Restrito | |
dc.subject | Integer programming | |
dc.subject | Branch-and-cut | |
dc.subject | Arborescence | |
dc.subject | Wireless sensor | |
dc.subject | Networks | |
dc.subject | Traveling salesman | |
dc.subject | Loading constraints | |
dc.subject | Pickup and delivery | |
dc.title | Exact approaches for network topology and routing problems | |
dc.type | Tese | |