Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/38088
Type: | Tese |
Title: | Exact approaches for network topology and routing problems |
Other Titles: | Abordagens exatas para problemas de topologia de rede e roteamento |
Authors: | Armando Honorio Pereira |
First Advisor: | Geraldo Robson Mateus |
First Co-advisor: | Sebastián Alberto Urrutia |
First Referee: | Haroldo Gambini Santos |
Second Referee: | Rafael Augusto de Melo |
Third Referee: | Rosiane de Freitas Rodrigues |
metadata.dc.contributor.referee4: | Gabriel de Morais Coutinho |
Abstract: | In this thesis, we investigate exact solution approaches for the p-arborescence star problem (p-ASP) and the pickup and delivery traveling salesman problem with multiple stacks (PDTSPMS). These two combinatorial optimization problems have applications in the design of wireless networks and the planning of vehicle routes under loading constraints, respectively. For the p-ASP, we develop branch-and-cut algorithms based on each one of our two proposed formulations and improve an earlier branch-and-cut algorithm for the problem with an exact separation method. Also, we prove that finding a feasible solution for an arbitrary p-ASP instance is NP-hard and introduce preprocessing procedures. For small and medium-sized benchmark instances, our proposed algorithms provide the best results. For large instances, our best algorithm shows to be competitive with the improved version of the existing approach. Both algorithms perform similarly for these hard instances and solve one instance that the other does not. Regarding the PDTSPMS, we propose a new formulation along with new valid inequalities. The new valid inequalities are lifted versions of inequalities used successfully in exact algorithms for the problem and its variants. Then, we implement a branch-and-cut algorithm based on the proposed formulation which incorporates the valid inequalities. Moreover, we also present several acceleration strategies for our method. The algorithm is compared with all exact approaches for the PDTSPMS found in the literature. Our implemented algorithm outperforms all other algorithms for the benchmark instances. Besides drastically reducing the time needed to solve most of the instances, the proposed algorithm solved more instances in total than the other methods. |
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. |
Subject: | Computação – Teses. Otimização combinatória - Teses. Programação inteira - Teses. Redes de sensores sem fio – Teses. Problema do caixeiro viajante – Teses. |
language: | eng |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Ciência da Computação |
Rights: | Acesso Restrito |
URI: | http://hdl.handle.net/1843/38088 |
Issue Date: | 18-May-2021 |
metadata.dc.description.embargo: | 18-May-2022 |
Appears in Collections: | Teses de Doutorado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Thesis.pdf | 1.35 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.