Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/33972| Tipo: | Tese |
| Título: | Algoritmos exatos e heurísticos para variações de problemas de roteamento, empacotamento e corte guilhotinado |
| Autor(es): | Eduardo Theodoro Bogue |
| Primeiro Orientador: | Thiago Ferreira de Noronha |
| Primeiro membro da banca : | Marcone Jamilson Freitas Souza |
| Segundo membro da banca: | Sebastián Alberto Urrutia |
| Resumo: | Problemas de otimização combinatória ocorrem em diversas situações práticas do dia a dia, como por exemplo em áreas de logística de transporte e distribuição, alocação de recursos, entre outras. Problemas de corte, empacotamento, e de roteamento de veículos são exemplos de problemas clássicos e muito bem estudados em otimização combinatória. Novas variantes destes problemas surgem à medida que aplicações exigem restrições adicionais ou relaxam algumas restrições do problema. Em particular, nesta tese estamos interessados em três variantes de problemas clássicos da literatura: o Problema do Roteamento de Veículos com Múltiplas Janelas de Tempo (VRPMTW), o Problema da Configuração de Produtos (PCP), e o Problema do Corte Guilhotinado Bidimensional em Três Estágios com Restrições de Precedência em Lote (2DCSP-BC). Para o VRPMTW, um algoritmo de Geração de Colunas (CG) e uma heurística pós-otimização baseada em uma heurística \textit{Variable Neighborhood Search} (VNS) são propostos para fornecer limites inferiores e superiores ao custo da solução ótima. Os resultados mostraram que CG foi capaz de produzir limites inferiores para 66,7\% das instâncias. Além disso, a heurística de pós-otimização foi capaz de melhorar a solução fornecida pela heurística VNS em 28,9\%, de modo que para as instâncias onde limites inferiores são conhecidos, o \textit{gap} de otimalidade foi de 6,0\% em média. Para o PCP, uma formulação de programação linear inteira e um algoritmo exato de programação dinâmica de tempo pseudo-polinomial foram propostos.Experimentos computacionais mostraram que ambos os algoritmos foram capazes de encontrar soluções ótimas para todas as instâncias avaliadas com até 10.000 componentes. Por fim, três heurísticas foram desenvolvidas para o 2DCSP-BC, sendo duas heurísticas estendidas da literatura, e uma heurística baseada em um algoritmo de programação dinâmica. Os resultados mostraram que a heurística baseada em programação dinâmica obteve resultados superiores aos das heurísticas estendidas da literatura. |
| Abstract: | Combinatorial optimization problems occur in mny practical everyday situations, such as transportation and distribution logistics, resource allocation, among others. Cutting, packaging, and vehicle routing problems are examples of classic and well-studied combinatorial optimization problems. New variants of these problems emerge as applications require additional constraints or relax some constraints of the problem. In this thesis we are interested in three variants of classic problems in literature: the Vehicle Routing Problem with Multiple Time Windows (VRPMTW), the Product Configuration Problem (PCP), and the 2-Dimensional Cutting Stock Problem Batch Constraints (2DCSP-BC). For the Vehicle Routing Problem with Multiple Time Windows, we propose , a Column Generation (CG) algorithm and a post-optimization heuristic based on a Variable Neighborhood Search (VNS) to provide both lower and upper bounds for the cost optimal solution VRMTW. The results showed that CG was able to produce lower bounds within one hour of running time for l 66.7 \% of the instances.Besides, the post-optimization heuristic was able to improve the solution provided by the VNS heuristic in 28.9 %, finding interger optimal solutions for 39,9% of instances where lower bounds are known, the average optimality gap was 6, 0 \% on average. In the Product Configuration Problems, an entire linear programming formulation and an exact pseudo-polynomial time dynamic programming algorithm were proposed. Computational experiments showed that both algorithms were able to find optimal solutions for all instances evaluated with up to 10,000 components. Finally, three heuristics were developed for the 2-Dimensional Cutting Stock Problem Batch Constraints 2DCSP-BC, where two heuristics are based on heuristics from the literature, and one heuristics is based dynamic programming algorithm. Computational experiments performed on the realistic instances showed that the dynamic programming heuristics obtained the best er results tamog the constructive heuristics. |
| Assunto: | Computação – Teses Programação dinâmica Programação linear inteira. Problema de roteamento de veículos |
| Idioma: | por |
| País: | Brasil |
| Editor: | Universidade Federal de Minas Gerais |
| Sigla da Instituição: | UFMG |
| Curso: | Programa de Pós-Graduação em Ciência da Computação |
| Tipo de Acesso: | Acesso Aberto |
| metadata.dc.rights.uri: | http://creativecommons.org/licenses/by/3.0/pt/ |
| URI: | http://hdl.handle.net/1843/33972 |
| Data do documento: | 23-Jul-2020 |
| Aparece nas coleções: | Teses de Doutorado |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| tese.pdf | 21.84 MB | Adobe PDF | Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
