Orientador: Eduardo Candido Xavier / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:15:42Z (GMT). No. of bitstreams: 1
Silveira_JeffersonLuizMoisesda_D.pdf: 2236708 bytes, checksum: 8e569408c2f068347058e36031689c3a (MD5)
Previous issue date: 2013 / Resumo: Neste trabalho estamos interessados em problemas de empacotamento e roteamento. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes para resolver tais problemas. Além de algoritmos exatos, duas das abordagens para resolver tais problemas são Algoritmos Aproximados e Heurísticas. Nesta tese mostramos algoritmos baseados nestas três abordagens para ambos os problemas, de empacotamento e roteamento. Os dois primeiros problemas atacados foram generalizações de problemas clássicos de empacotamento: O problema da mochila bidimensional e o problema de empacotamento em faixas. Estes foram generalizados adicionando restrições na forma de carregamento e descarregamento dos itens no recipiente (restrições estas, que aparecem no contexto de problemas de roteamento). O terceiro problema é uma combinação de problemas de empacotamento e roteamento. Neste caso, atacamos uma generalização do clássico Pickup and Delivery Problem. Propomos os primeiros resultados de aproximação para algumas versões dos problemas de empacotamento supracitados. Além disto, apresentamos algumas abordagens práticas para o terceiro problema. As heurísticas foram avaliadas através de experimentos computacionais comparando os seus resultados com algoritmos exatos / Abstract: In this work we are interested in packing and routing problems. Assuming P ? NP, we have that there are no efficient algorithms to deal with such problems. Besides exact algorithms, two approaches to solve such problems are Approximation Algorithms and Heuristics. In this thesis we show algorithms using these three approaches for both packing and routing problems. The first two addressed problems are generalizations of classical packing problems: The Two Dimensional Knapsack problem and the Strip Packing problem. These problems were generalized by adding constraints on the way the items can be inserted/removed into/from the bin (These constraints appear in the context of routing problems). The third problem is combination of packing and routing problems. It is a generalization of the classical Pickup and Delivery problem. We propose the first approximation results for some packing problems. Besides that, we present some practical algorithms for the third problem. The heuristics were assessed through computational experiments by comparing their results with exact algorithms / Doutorado / Ciência da Computação / Doutor em Ciência da Computação
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/275605 |
| Date | 10 February 2013 |
| Creators | Silveira, Jefferson Luiz Moisés da, 1986- |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Xavier, Eduardo Candido, 1979-, Souza, Cid Carvalho de, Cavalcante, Victor Fernandes, Neto, Reinaldo Morabito, Yanasse, Horacio Hideki |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Computação, Programa de Pós-Graduação em Ciência da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Multilíngua |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | 97 p. : il., application/octet-stream |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0024 seconds