Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O objetivo central deste projeto é precisar matematicamente certos objetos combinatórios que servem como ponto de partida nas apresentações usuais da Análise Combinatória e são comumente apresentados de maneira informal e intuitiva. Estabelecido este referencial teórico preciso, pretendemos, a partir dele, reapresentar os conceitos de Análise Combinatória de modo mais rigoroso privilegiando sempre a apresentação mais natural possível. Mais precisamente, estaremos interessados em reapresentar os resultados referentes ao capítulo dois do livro do professor Augusto C. Morgado a partir de uma versão matematicamente mais precisa dos Princípios Aditivo e Multiplicativo. Além disso, pretendemos que os argumentos usados em nossas deduções usem predominantemente indução ou construção de bijeções, o que é um dos grandes objetos de estudo da combinatória moderna

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Agronomia e Medicina Veterinária, Programa de Pós-Graduação em Agronegócios, 2014. / Submitted by Ana Cristina Barbosa da Silva (annabds@hotmail.com) on 2014-10-10T19:53:39Z No. of bitstreams: 1 2014_DianaCarolinaCastroMur.pdf: 2851931 bytes, checksum: 0ec139d96a1a3b2d67fc1a83225133a6 (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2014-10-13T13:18:08Z (GMT) No. of bitstreams: 1 2014_DianaCarolinaCastroMur.pdf: 2851931 bytes, checksum: 0ec139d96a1a3b2d67fc1a83225133a6 (MD5) / Made available in DSpace on 2014-10-13T13:18:08Z (GMT). No. of bitstreams: 1 2014_DianaCarolinaCastroMur.pdf: 2851931 bytes, checksum: 0ec139d96a1a3b2d67fc1a83225133a6 (MD5) / Este trabalho visou contribuir com o estudo da localização otimizada de unidades de armazenamento de grãos, no estado de Goiás, zerando o seu déficit na sua capacidade estática de armazenamento. Para isso, desenvolveu-se, um modelo matemático de otimização, derivado do modelo de fluxo de custo mínimo, que foi implementado computacionalmente utilizando o software LINGO (Versão 9.00, Extended). O modelo proposto minimiza os custos de movimentação dos grãos entre os municípios, considerando a localização de unidades de armazenamento existentes e aquelas que devem ser construídas de modo a zerar o déficit de armazenagem na região considerada. Neste modelo usaram-se como variáveis a produção de grãos no estado de Goiás, a capacidade estática de armazenamento, e, o custo de transporte entre os municípios das regiões que foram analisadas. O modelo determinou os municípios nos quais devem ser instaladas unidades armazenadoras, especificando sua capacidade estática de armazenamento, além do fluxo de produto entre as unidades e entre os demais municípios para minimizar o déficit, os custos de transporte e suprimento das necessidades de armazenamento de cada município. Em termos numéricos, com o modelo logrou-se zerar o déficit de armazenamento para os 156 municípios que foram analisados (que apresentam o 63% do déficit total do estado), e propõem-se instalar 40 unidades armazenadoras com uma capacidade total de 7.124.272 toneladas. ______________________________________________________________________________ ABSTRACT / This study intends to contribute to analyze of optimal location of grain storage units in the state of Goiás by resetting its deficit in its static storage capacity. For that, it was developed into a mathematical optimization model, derived from the minimum cost flow model, which was implemented computationally using the LINGO software (Version 9:00, Extended). The proposed model minimizes the costs of moving grain between municipalities, considering the location of existing storage units and those that must be constructed so as to reset the storage deficit in the region considered. In this model was used such as variables, grain production in the state of Goiás, the static storage capacity, and the cost of transportation between the municipalities regions that were analyzed. The model determined the municipalities in which storage units must be installed by specifying a static storage capacity, in addition to the product flow between units and among other municipalities to minimize the deficit, the costs of transportation and supply storage needs of each municipality. Numerically, the model has been achieved to reset-the deficit storage for the 156 municipalities that were analyzed (presenting the 63% of the total deficit of the state), and propose to install 40 storage units with a total capacity of 7,124. 272 tons.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, 2014 / Submitted by Ana Cristina Barbosa da Silva (annabds@hotmail.com) on 2014-11-12T19:50:56Z No. of bitstreams: 1 2014_WaldizarBorgesdeAraújoFrança.pdf: 919884 bytes, checksum: 93f30558375630e5d98a21a9d7f5b9fd (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2014-11-13T14:19:45Z (GMT) No. of bitstreams: 1 2014_WaldizarBorgesdeAraújoFrança.pdf: 919884 bytes, checksum: 93f30558375630e5d98a21a9d7f5b9fd (MD5) / Made available in DSpace on 2014-11-13T14:19:45Z (GMT). No. of bitstreams: 1 2014_WaldizarBorgesdeAraújoFrança.pdf: 919884 bytes, checksum: 93f30558375630e5d98a21a9d7f5b9fd (MD5) / Neste trabalho estuda-se os principais conceitos da criptografia e mostra-se a sua evolução ao longo da história, fornecendo dados para que o professor de matemática possa introduzir esse assunto no Ensino Médio. No último capítulo deste trabalho, são propostas atividades, fundamentadas em resolução de problemas, que abordam os conceitos de Funções Afins, Funções Quadráticas, Funções Exponenciais, Funções Logarítmicas, Matrizes e Análise Combinatória. Estas atividades têm como agente motivador a criptografia para codificar e decodificar mensagens. _______________________________________________________________________________________ ABSTRACT / In this work, we study the main concepts of cryptography and show its evolutionthroughout history, providing data for the mathematics teacher can introduce this subjectin high school. In the last chapter of this work are proposed activities based onproblem solving, addressing the concepts of Affine, Quadratic Functions, Exponential Functions, Logarithmic Functions, Arrays and Combinatorial Analysis, having asmotivator encryption to encode and decode messages.

O empacotamento irregular de fita é um grupo de problemas na área de corte e empacotamento, cuja aplicação é observada nas indústrias têxtil, moveleira e construção naval. O problema consiste em definir uma configuração de itens irregulares de modo que o comprimento do contêiner retangular que contém o leiaute seja minimizado. A solução deve ser válida, isto é, não deve haver sobreposição entre os itens, que não devem extrapolar as paredes do contêiner. Devido a aspectos práticos, são admitidas até quatro orientações para o item. O volume de material desperdiçado está diretamente relacionado à qualidade do leiaute obtido e, por este motivo, uma solução eficiente pressupõe uma vantagem econômica e resulta em um menor impacto ambiental. O objetivo deste trabalho consiste na geração automática de leiautes de modo a obter níveis de compactação e tempo de processamento compatíveis com outras soluções na literatura. A fim de atingir este objetivo, são realizadas duas propostas de solução. A primeira consiste no posicionamento sequencial dos itens de modo a maximizar a ocorrência de posições de encaixe, que estão relacionadas à restrição de movimento de um item no leiaute. Em linhas gerais, várias sequências de posicionamentos são exploradas com o objetivo de encontrar a solução mais compacta. Na segunda abordagem, que consiste na principal proposta deste trabalho, métodos rasterizados são aplicados para movimentar itens de acordo com uma grade de posicionamento, admitindo sobreposição. O método é baseado na estratégia de minimização de sobreposição, cujo objetivo é a eliminação da sobreposição em um contêiner fechado. Ambos os algoritmos foram testados utilizando o mesmo conjunto de problemas de referência da literatura. Foi verificado que a primeira estratégia não foi capaz de obter soluções satisfatórias, apesar de fornecer informações importantes sobre as propriedades das posições de encaixe. Por outro lado, a segunda abordagem obteve resultados competitivos. O desempenho do algoritmo também foi compatível com outras soluções, inclusive em casos nos quais o volume de dados era alto. Ademais, como trabalho futuro, o algoritmo pode ser estendido de modo a possibilitar a entrada de itens de geometria genérica, o que pode se tornar o grande diferencial da proposta. / Irregular nesting belongs to the area of cutting and packing problems and are employed in the textile, wood and shipbuilding industries. The problem consists in determining a configuration for a set of irregular items which minimizes the length of the rectangular container in which the layout is located. The solution must be feasible, i.e., items must not overlap nor protrude the container walls. Due to practical reasons, up to four orientations are allowed for an item. The volume of wasted material is directly affected by the quality (density) of the layout. Thus, an efficient solution produces a positive economic and environmental impact. In this work, the objective is to automatically obtain layouts such that their density and the performance of the algorithm are competitive with other solutions in literature. So as to achieve this goal, two approaches are proposed. The first method uses a special sequential placement heuristic such that the algorithm maximizes exact placements, which consist of constrained positions for items. In general terms, a search is performed in the placement sequence in order to obtain a compact layout. In the second approach, which is the main subject of this work, raster methods are employed to guide the translation of items, which are free to move within the layout, and may overlap other items. The method is based on overlap minimization techniques, in which the objective is to eliminate the overlap in a fixed dimensions container. Both algorithms were tested using benchmark problems from the literature. The first strategy yielded unsatisfactory results, though it provided important information about the properties of exactly fitting placements. On the other hand, the main approach was able to produce competitive solutions. The performance was also compatible with other solutions, even in cases which the data volume was high. Moreover, as a future work, an extension for the algorithm can be developed such that items with generic geometry can be considered, which would be an important advance in research terms.

Submitted by Danielle Karla Martins Silva (danielle.martins@ufpe.br) on 2015-03-13T16:53:14Z No. of bitstreams: 2 DISSERTAÇÃO Adryanne Maria Rodrigues Barreto de Assis.pdf: 3198017 bytes, checksum: 484bc059537625e750c4b7167ac04f1e (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-13T16:53:14Z (GMT). No. of bitstreams: 2 DISSERTAÇÃO Adryanne Maria Rodrigues Barreto de Assis.pdf: 3198017 bytes, checksum: 484bc059537625e750c4b7167ac04f1e (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2014 / Este estudo se propôs a analisar o efeito de um processo de formação continuada sobre Combinatória, baseado na Teoria dos Campos Conceituais de Vergnaud (1986), a qual constitui o tripé que forma o conceito: situações1, invariantes e representações simbólicas dos problemas combinatórios. O processo foi realizado com um grupo de professoras de uma escola, contudo, a pesquisa traz as inferências realizadas a partir das reflexões e práticas de uma professora. A pesquisa se constituiu em entrevista inicial individual com a professora, seis encontros para formação, nos quais também se incluem duas observações de aula ministrada pela professora, e uma entrevista final, também individual, com a professora participante. Foi solicitado também ao longo da pesquisa que a docente elaborasse alguns planejamentos de aulas, sendo um na entrevista inicial, dois durante o processo de formação (quarto e sexto encontro), que seriam aplicados em sala de aula, e outro na entrevista final. As entrevistas inicial e final realizadas na pesquisa são baseadas nas entrevistas realizadas por Rocha (2011). Buscamos verificar o efeito dessa formação nos conhecimentos da docente pesquisada, a partir das contribuições de Shulman (2005) e Ball e seus colaboradores (2008), especificamente, no conhecimento especializado do conteúdo e no conhecimento didático deste conteúdo, no caso, da Combinatória. Os resultados apontam para uma dificuldade no reconhecimento e trabalho da Combinatória, na entrevista inicial. No entanto, durante e após as intervenções, há o reconhecimento, pela professora, mais detalhado das diferentes situações e seus respectivos invariantes, assim como, das representações simbólicas e do desenvolvimento do raciocínio combinatório de alunos. Verificou-se também que a docente reconhece o material manipulável como uma forma válida de representação para auxiliar no processo de ensino e aprendizagem e, ao longo do processo de formação, faz uso desses ao ministrar aulas sobre Combinatória, sendo estas bastante dinâmicas e de acordo com o que estava sendo solicitado. Sendo assim, constatamos que há uma ressignificação da docente participante quanto a seus conhecimentos, especificamente, o conhecimento especializado da Combinatória e o conhecimento didático da Combinatória. Percebe-se, então, que a formação continuada em Combinatória pode se constituir em uma ação importante, levando os docentes a ressignificarem seus conhecimentos e refletirem sobre esse conteúdo que pode ser trabalhado desde os anos iniciais do Ensino Fundamental.

Submitted by Danielle Karla Martins Silva (danielle.martins@ufpe.br) on 2015-03-13T17:42:19Z No. of bitstreams: 2 DISSERTAÇÃO Danielle Avanço Vega.pdf: 2676183 bytes, checksum: 9b2128d439b0d97225e476c2411ad128 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-13T17:42:19Z (GMT). No. of bitstreams: 2 DISSERTAÇÃO Danielle Avanço Vega.pdf: 2676183 bytes, checksum: 9b2128d439b0d97225e476c2411ad128 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2014 / Com o objetivo de analisar a influência do número de etapas de escolha na resolução dos diversos tipos de problemas combinatórios, (produto cartesiano, arranjo, combinação e permutação), a presente pesquisa se fundamentou na Teoria dos Campos Conceituais de Vergnaud (1986), que defende a existência de três dimensões fundamentais de conceitos: situações que dão significado, invariantes e representações simbólicas. A pesquisa também se fundamentou em outros autores, entre eles, Pessoa e Borba (2009), que abordam os diversos significados presentes na Combinatória e Borba (2010), que trata do raciocínio combinatório. A presente dissertação entende por etapa de escolha, as variáveis presentes em uma situação combinatória e defende que o número de etapas de escolha pode influenciar na resolução de problemas combinatórios. Participaram da pesquisa 128 alunos do 6º ano do Ensino Fundamental os quais responderam a um teste de sondagem. Foram seis tipos de testes, os cinco primeiros compararam os desempenhos em dois tipos de problemas cada e o último teste comparou as etapas de escolha dentro do mesmo problema. Em todos os testes eram comparados problemas com duas, três e quatro etapas de escolha. No teste Tipo 6 se observaram as etapas de escolha dentro do mesmo problema. O resultado dos testes revelou que os Tipo 2 e 5 foram os que obtiveram uma média de acertos mais baixas, podendo esta dificuldade estar associada ao total de possibilidades presente nos problemas de arranjo com quatro etapas, visto que era o tipo de problema que apresentava maior grandeza numérica. Quando se comparou cada etapa de escolha, verificou-se haver diferença estatisticamente significativa entre os desempenhos nos problemas de produto cartesiano com quatro etapas de escolha em comparação aos mesmos problemas com duas e três etapas de escolha, evidenciando a influencia das etapas de escolha no desempenho dos alunos. Ao comparar o problema de produto cartesiano que, segundo pesquisas anteriores (PESSOA e BORBA, 2009, 2010; CORREIA e OLIVEIRA, 2011, e AZEVEDO e BORBA, 2012), era tido como o problema de mais fácil resolução para os alunos, com os problemas de permutação, percebeu-se uma inversão do que havia sido constatado anteriormente, na qual a permutação passou a ser mais fácil que o produto cartesiano quando se controlou o número de etapas de escolha. Quando se observou as estratégias de resolução, não se verificou relação entre a representação simbólica e estratégias utilizadas e os tipos de problemas, nem com as etapas de escolha, indicando que a utilização das estratégias pode estar relacionada a escolhas pessoais. Conclui-se que no trabalho com variados tipos de situações combinatórias é preciso considerar diferentes etapas de escolha em cada tipo de problema desde o Ensino Fundamental. Almeja-se, assim, com essa pesquisa, contribuir para a reflexão sobre aspectos a serem considerados de ensino da Combinatória.

Made available in DSpace on 2014-06-12T15:59:34Z (GMT). No. of bitstreams: 2 arquivo5182_1.pdf: 7099391 bytes, checksum: 9ae548e6659db775935f03eac2fa2f35 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2006 / Um dos principais objetivos da biologia molecular é descobrir o funcionamento de redes complexas de interação entre elementos celulares. Nas últimas décadas um grande volume de dados biológicos vem sendo produzido assim como modelos computacionais que fazem uso destes dados. Os métodos computacionais para Reconstrução de Redes de Genes apresentam-se como uma ferramenta importante para auxiliar no estudo e entendimento desta complexidade. Este trabalho apresenta uma proposta para Reconstrução de Redes de Genes que utiliza-se de diferentes fontes de dados e incorpora conhecimento biológico com o objetivo de melhorar a qualidade da inferência. Comparou-se a abordagem proposta com um trabalho anterior. Foram realizados experimentos com dados artificiais e dados reais de S. cerevisiae. O modelo proposto apresentou melhores resultados que o anterior em todos os critérios de avaliação para experimentos com dados artificiais. Na avaliação com dados reais a nova abordagem apresentou uma pequena melhora em apenas uma das configurações testadas

Made available in DSpace on 2014-06-12T17:16:31Z (GMT). No. of bitstreams: 2 arquivo2888_1.pdf: 4515065 bytes, checksum: 37f35d4e8df933b6e333f6d782c4ca95 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2011 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Experiências de prática docente têm evidenciado que problemas de Combinatória despertam nos alunos curiosidades e grande participação em sala de aula. No entanto, mesmo com essas características, o número de erros cometidos na resolução de situações de Combinatória ainda é muito grande, o que indica dificuldades no ensino e/ou na aprendizagem desse conteúdo. Nesse sentido, a presente pesquisa busca analisar os conhecimentos que professores do Ensino Fundamental e Médio têm sobre a Combinatória e seu ensino. O quadro teórico foi constituído pelos trabalhos de Shulman e seus colaboradores na compreensão dos conhecimentos do conteúdo e dos conhecimentos didáticos do conteúdo dos professores em exercício, bem como pelos trabalhos de Ball e seus colaboradores, os quais propõem um modelo de caracterização dos conhecimentos associado aos professores que ensinam Matemática. Para entender as escolhas docentes na construção do raciocínio combinatório em alunos, utilizamos a ideia da construção dos conceitos definida pela Teoria dos Campos Conceituais de Vergnaud, além da classificação dos tipos de problemas combinatórios (produto cartesiano, permutação, arranjo e combinação) fundamentada nas pesquisas desenvolvidas no Grupo de Estudos em Raciocínio Combinatório do Centro de Educação (Geração- UFPE) sob a orientação de Borba. Utilizamos como procedimento metodológico a entrevista semi-estruturada, realizada com seis professores (dois dos anos iniciais, dois dos anos finais do Ensino Fundamental e dois do Ensino Médio) na qual responderam questões referentes aos tipos de problemas combinatórios, aos procedimentos de resolução utilizados por alunos e às formas de ensino para a superação de dificuldades. A pesquisa revelou que, apesar das diferentes formações, quase todos os professores apresentaram dificuldades na diferenciação de problemas de arranjo e combinação, tanto na leitura do enunciado do problema quanto na correção de estratégia do aluno, denotando desconhecimento de situações nas quais o invariante do conceito de ordenação implica ou não, em possibilidades distintas. Constatou-se, também, que os professores dos anos iniciais na análise dos tipos de problemas elegeram a forma do enunciado como diferenciador, enquanto que professores de formação em Matemática apontaram aspectos de suas estruturas. No que diz respeito às estratégias priorizadas pelos professores para a resolução de problemas combinatórios por alunos dos diferentes níveis, há indícios de que estas são determinadas em função do nível de dificuldades do problema por eles concebidas e das suas expectativas em relação aos alunos inseridos nos diferentes anos de escolaridade. Dessa forma, as respostas dos professores indicam uma articulação entre suas experiências de formação e de prática docente. Conclui-se que para a condução de um trabalho que permita maior desenvolvimento do raciocínio combinatório pelos alunos, é necessário, por parte dos professores, um mais aprofundado nível de conhecimento das estruturas combinatórias, do conhecimento dos alunos e de suas estratégias de resolução, ressaltando-se a necessidade de mais trabalhos científicos que busquem auxiliar professores em seus conhecimentos de conteúdo e pedagógico referentes à Combinatória

Neste trabalho desenvolve-se uma proposta de ensino para aprimorar o raciocínio combinatório, através da utilização de jogos no planejamento, na aplicação e avaliação de uma sequência didática inspirada nas orientações de Zabala, para subsidiar a prática docente no ensino de Análise Combinatória. A dissertação relata uma pesquisa que teve o intuito de explorar conceitos combinatórios por meio de atividades diversificadas, envolvendo recursos digitais, jogos e estudos orientados, a fim de fortalecer e diversificar o ensino e a aprendizagem deste conteúdo, procurando tornar as aulas mais atrativas e dinâmicas. Alguns dos jogos utilizados para a criação da sequência didática não são originais, outros já foram aplicados por pesquisadores ou professores, porém, aqui, foram reorganizados, ajustados ou adaptados de modo a adequar e potencializar a sua utilização, no contexto da prática elaborada. As várias atividades, promovidas para a realização dos jogos ou as de etapa posterior, foram planejadas de modo a explorar o raciocínio combinatório. A pesquisa é fundamentada na visão construtivista do fazer e compreender, de Piaget, e resultou como produto deste trabalho uma sequência didática denominada Dinâmica Combinatória, que integra as atividades dinamizadas numa sequência de ensino que envolve ações, direcionadas para a compreensão dos conceitos combinatórios. Juntamente com este processo de compreensão, construiu-se um espaço para os alunos explorarem, com orientação do professor, toda a simbologia que contempla o conteúdo de Análise Combinatória, a fim de que conhecessem as fórmulas que integram as técnicas de contagem. Por fim, faz-se uma avaliação da aprendizagem, com a utilização do Jogo Trilha Combinatória, criado especialmente para a aplicação dos conhecimentos construídos, por meio das ações que constituem as jogadas, verificando se ocorreu aprendizagem. A análise dos dados obtidos com a pesquisa foi qualitativa, e avaliou formulários, diários de anotações, registros fotográficos, entre outros e revelou aprendizagens e envolvimento dos estudantes para além das expectativas do pesquisador. Conclui-se que a Dinâmica Combinatória tornou-se um recurso didático potencial para a aprendizagem e o desenvolvimento do raciocínio combinatório, propiciando um processo de ensino e aprendizagem de Análise Combinatória dinâmico e atrativo. / In this paper, a teaching proposal is developed to improve the combinatorial reasoning through the use of games in the planning, application and assessment of a didactic sequence, inspired by Zabala guidelines, to subsidize the teaching practice in Combinatorial Analysis teaching. The dissertation reports a research that aims to explore combinatorial concepts through diversified activities, involving digital resources, games and guided studies, in order to strengthen and diversify the teaching- learning process of this content, trying to make classes more attractive and dynamic. Some of the games used to create the didactic sequence are not original and some of them have already been applied by other researchers or teachers, but in this paper they have been reorganized, adapted and tailored to make them suitable and enhance their use in the practice context. The several activities, promoted for the accomplishment of the games or those of a later stage, were planned aiming to explore the combinatorial reasoning. The research is based on Piaget 's constructivist view of ” the doing and the understanding “ and resulted in a didactic sequence called Combinatorial Dynamics, which integrates the energized activities in a teaching sequence involving actions directed towards the understanding of the combinatorial concepts. Together with this process of comprehension, a space was built for students to explore, with the teacher's guidance, all the symbology that contemplates the content of Combinatorial Analysis, getting them to know the formulas which integrate the counting techniques. Finally, an evaluation of learning is made, using the Combination Track Game, created specially for the application of the constructed knowledge through games, verifying if the learning process was achieved. The research results are from a qualitative analysis that evaluated forms, journals, photographic records, among others and revealed students' learning and involvement beyond the researcher's expectations. It is concluded that Combinatorial Dynamics has become a potential didactic resource for the learning process and for the development of combinatorial reasoning, providing a dynamic and attractive Combinatorial Analysis Teaching and Learning process.

Submitted by MARCOS LEANDRO TEIXEIRA DE OLIVEIRA (marcosteixeira@ufv.br) on 2018-09-04T13:38:28Z No. of bitstreams: 1 texto completo.pdf: 1118685 bytes, checksum: 94e01364e7abc576bdbab9d4b54cd7cf (MD5) / Made available in DSpace on 2018-09-04T13:38:28Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1118685 bytes, checksum: 94e01364e7abc576bdbab9d4b54cd7cf (MD5) Previous issue date: 2018-01-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o Problema de Roteamento de Veículos para Coleta de Lixo com Janelas de Tempo (WCVRPTW), cujo objetivo é encontrar as rotas para os veículos coletores de lixo de modo que todos os clientes sejam plenamente atendidos e a distância total percorrida pelos veículos seja a menor possível, minimizando assim os custos de transporte. Para alcançar este objetivo é necessário que algumas restrições sejam atendidas: os clientes devem ser atendidos dentro de um período de tempo; existe horário de saída e retorno dos veículos ao depósito; os veículos possuem restrições de capacidade; as rotas possuem restrições de volume de carregamento e número de clientes atendidos; os veículos devem sair e retornar vazios ao depósito, e, quando cheios, devem ir para o aterro sanitário mais próximo para descarga do lixo. Além disso, os motoristas dos veículos devem realizar uma parada de almoço. O WCVRPTW é um problema real que pertence à classe NP-difícil. Para resolvê-lo, são desenvolvidos quatro algoritmos heurísticos: Simulated Annealing (SA), Tabu Search (TS), e dois algoritmos híbridos baseados nas metaheurísticas Iterated Local Search (ILS) e Variable Neighborhood Descent (VND), denominados ILS-VND e ILS-RVND. Os desempenhos dos algoritmos propostos são analisados em instâncias de pequeno e médio porte geradas para este trabalho, e também em instâncias de grande porte disponíveis na literatura. Os experimentos computacionais mostram que os algoritmos propostos são eficientes, competitivos e rápidos. / In this work we address The Waste Collection Vehicle Routing Problem with Time Windows (WCVRPTW), whose objective is to find the routes for garbage collection vehicles so that all customers are fully served and the total distance traveled by the vehicles is the smallest possible, thus minimizing transportation costs. In order to achieve this objective, some constraints must be satisfied: customers must be ser- ved within a period of time; there are departing and return times of the vehicles to the warehouse; vehicles have capacity constraints; the routes have loading volume constraints and number of customers served; the vehicles should leave and return empty to the depot, and when full should go to the nearest landfill for garbage disposal. In addition, drivers of the vehicles must have a lunch break. WCVRPTW is a real problem that belongs to the NP-hard class. In this work, to solve it, four heuristic algorithms are developed: Simulated Annealing (SA), Tabu Search (TS), and two hybrid methods based on the Iterated Local Search (ILS) and Varia- ble Neighborhood Descent (VND) metaheuristics, called ILS-VND and ILS-RVND. The performances of the proposed methods are analyzed in small and medium-sized instances generated in this work, and also in large instances available in the lite- rature. Computational experiments show that the proposed methods are efficient, competitive and fast.